【軟工】個人項目作業——個人軟體流程(PSP)

項目	内容
班級：北航2020春軟體工程 006班（羅傑、任健 周五）	部落格園班級部落格
作業：設計程式求幾何對象的交點集合	個人項目作業
個人課程目标	系統學習軟體工程，訓練軟體開發能力
這個作業在哪個具體方面幫助我實作目标	實踐個人軟體開發流程（PSP）
項目位址	GitHub: clone/http

個人軟體流程（PSP）

PSP2.1	預估耗時（分鐘）	實際耗時（分鐘）
Planning	20
· Estimate
Development	310	530
· Analysis	30	90
· Design Spec	10
· Design Review
· Coding Standard
· Design	40
· Coding	120
· Code Review
· Test	60	150
Reporting	50
· Test Report
· Size Measurement
· Postmortem & Process Improvement Plan
In Total	380	600

最終完成整個項目的時間遠遠超出了我的預計，其中與預期嚴重不符的項包括：分析需求、設計和測試。其中，分析需求和設計逾時的原因是對題目要求功能的本質思考不清晰，思路和設計經過了以下的反複疊代和更改：

• 首先對參數在\((-10^5,10^5)\)範圍時的交點取值範圍進行了數學上的分析，認為線-線交點可能坐标高達\(4\times10^{10}\)，精度要求可能高于\(10^{-5}\)。
• 于是認為使用

  double

  維護點坐标精度不夠，于是決定自行構造一個有理數類\(\frac{P}{Q}\)，分子分母均為

  long long

  型
• 後來發現附加題裡涉及到圓，線-圓交點的形式為\(\frac{A+B\sqrt{C}}{D}\)，于是決定擴充有理數類到支援帶系數的根式。再思考如何标準化該式以進行兩坐标之間的比較（哈希和判等），涉及到了質因數分解等。
• 再仔細分析，認為線-線交點範圍可能達到\(4\times 10^{10}\)，再由于double類型的有效數字僅為15位左右，即小數點後5位左右，是以認為應當使用有理數類存儲線線交點以避免精度問題。然而對線-圓交點和圓-圓交點而言，交點範圍必在\(\pm 2\times 10^{5}\)以内，是以使用double存儲可到小數點後近10位，是以涉及到圓的交點可以使用double，精度足夠。在比較時認為有理數≠double小數。
• 又發現線線交點可能和圓交點重合，于是必須檢查涉及到圓的交點坐标是否為有理數。是有理數則使用有理數類，否則使用double。這要求将坐标的公式寫出，檢查根号内的整數是否為完全平方數。若是完全平方數則可以化為有理數類，否則直接求值。

可以看出，如果一開始就較為清晰地将各個需求羅列出來，再一一分析，分析之後再進行統一設計，可能很快就可以想出有理數/無理數的分類，而不是将所謂設計的有理數類反複拓展以支援新需求。

如果是一邊像這樣設計一邊寫代碼，浪費的時間就更是災難性的，代碼将會反複修改，思路也會頻繁被打斷。

是以PSP看似麻煩複雜的流程不是沒有道理的，以後應當記住這個教訓。

解題思路

此題使用哈希表的暴力解法時間複雜度為\(O(n^2)\)。容易考慮到有兩種優化條件，分别為 “平行線” 和 “多線共點”。對于前者可以按斜率進行等價類劃分，在類間進行兩兩求交；對于後者需要額外計算判斷是否共點，也會帶來常數的提升。

是以筆者仍然選擇暴力解法，枚舉每pair的幾何對象組合，計算交點，使用哈希集合維護去重。

點的維護

三種交點有着三種不同的公式。首先将它們的通式推導出來。具體的推導和公式可以參照：

• 線-線交點: Wikipedia
• 線-圓交點: Wolfram MathWorld
• 圓-圓交點: Stack Overflow

其中，線線交點可以寫成如下形式：

\[(x,y)=(\frac{x_1}{x_2},\frac{y_1}{y_2})

\]

其中\(x_1,x_2,y_1,y_2\)均為整數表達式的運算結果。于是，設計一個有理數類存儲線-線交點的坐标（不使用

double

的理由見上節）以便于哈希和比較。

然而，線-圓交點和圓-圓交點的形式為：

\[(x,y)=(\frac{x_1+x_2\sqrt{\Delta}}{x_3},\frac{y_1+y_2\sqrt{\Delta}}{y_3})

其中\(x_\bullet,y_\bullet, \Delta\)均為整數表達式的運算結果。當\(\Delta\)為完全平方數時，該式化簡為有理數形式；否則，該式為無理數。

考慮到有理數不可能等于無理數，是以首先檢查\(\Delta\)是否能開根，若可以則使用有理數類，否則直接求值使用

double

存儲（此處可以使用

double

的理由見上節）。

求交點：四種二進制關系

假設有類

Line

和類

Circle

存儲兩類幾何對象。然而求交點需要

(Line, Line), (Line, Circle), (Circle, Line), (Circle, Circle)

四種組合。

一開始，我傾向于使用父類和子類維護不同的幾何對象，但發現即使使用重載和重寫，代碼效率和可讀性并沒有明顯的提高。

後來通過查找資料，我在 這篇問答文章 中找到了最佳的解決方案：使用

std::variant

和

std::visit

來優美地實作“多态二進制函數”。

std::variant

相當于一種更新版的union類型，可以安全地存儲不同類型的對象，可以通過

index()

方法取得某對象的類型，也可以通過

std::get<type>(x)

取得

variant

對象

x

的值。不僅如此，它還支援使用

std::visit(visitor, vars)

去自動處理各種類型為參數的函數調用（可以參考cppReference.com），正好和該問題的需求相比對！其中，

visitor

是一個封裝了callable函數的結構體，能支援每個參數的每種類型組合，

vars

是待傳入的

variant

參數清單。

具體實作請見“代碼說明”。

交點集合的維護（去重）

C++中的

set

基于BST實作，在此我們并不需要對點進行排序和有序組織，是以考慮使用

unordered_set

來維護點，相當于Java中的HashSet。要使用

unordered_set

，必須提供哈希函數和判等函數。

對于點來說，有x和y兩個坐标，在哈希時隻需将兩個坐标擷取哈希值再進行組合即可，在判等時需要注意先驗條件“有理數不等于無理數”以保證正确性！

而坐标有整數數對（有理數）和浮點數（double）兩種形式，在判等時應當注意判斷等号兩端坐标分别點類型。

注意到在哈希和判等前，坐标必須進行化簡（\(\frac{8}{6}=\frac{4}{3}\)）和标準化（\(\frac{-0}{8}=\frac{0}{1}\)），是以使用輾轉相除法求最大公約數，再消去該因子。

由于這裡分子和分母有可能較大，是以普通的輾轉相除法可能效率較低。一個優化的輾轉相除法可以參照《程式設計之美》2.7節《最大公約數問題》。該算法檢查兩數的奇偶性，當至少有一個數為偶數的情況下，數值的規模将會直接減半。當兩個數為奇數時，算法避免了較慢的除法和取模運算，而是使用輾轉相減，使得再次出現偶數。是以，該算法的最壞時間複雜度為\(O(\log_2(\max(x,y))\)，十分理想。

設計

類與資料結構

如上文所說，基礎的資料結構是坐标，支援兩種形式的數，構造時化簡和标準化。支援hashCode。

class Coordinate {
    // Case 1: Rational Number = A / B (long-long / long-long)
    // Case 2: Float Number = C (double)
private:
    void simplifyRational();
    void simplifySqrt(ll add, ll coeff, ll insqrt, ll btm);

public:
    bool isRational, isNan;
    ll top, bottom;
    double value;

    Coordinate(ll tp, ll btm);  // tp / btm
    Coordinate(ll a, ll b, ll c, ll btm);  //  ( a + b * sqrt(c) ) / btm  ----->  (1) A / B   or   (2) double value
    std::size_t hashCode() const ;
};
           

坐标組成點，點可以求哈希值和判等：

class Point {
public:
    Coordinate x, y;
    Point(Coordinate xx, Coordinate yy);
};

struct hashCode_Point {
    std::size_t operator()(const Point &point) const ;
};

struct equals_Point {
    bool operator()(const Point &lhs, const Point &rhs) const ;
};
           

幾何對象有直線和點，它們之間支援兩兩求交點：

class Line {
public:
    Line(int x1, int y1, int x2, int y2);
    int p1_x, p1_y;
    int p2_x, p2_y;
};

class Circle {
public:
    Circle(int x, int y, int r);
    int center_x, center_y;
    int radius;
};

std::vector<Point> intersection(Line x, Circle y);
std::vector<Point> intersection(Circle x, Line y);
std::vector<Point> intersection(Line x, Line y);
std::vector<Point> intersection(Circle x, Circle y);
           

最後使用基于哈希的

unordered_map

維護點集：

std::unordered_set<Point, hashCode_Point, equals_Point> container;
           

代碼說明

坐标與交點

優化的最大公約數算法，為化簡作準備：

ll fastGcd(ll x, ll y) {
    if (x < y)
        return fastGcd(y, x);
    if (!y)
        return x;
    // 使用位運算以避免較慢的除法和取模
    if ((x >> 1u) << 1u == x) {
        // 兩個偶數 或 一奇一偶
        if ((y >> 1u) << 1u == y) return (fastGcd(x >> 1u, y >> 1u) << 1u);
        else return fastGcd(x >> 1u, y);
    } else {
        // 一奇一偶 或 兩個奇數
        if ((y >> 1u) << 1u == y) return fastGcd(x, y >> 1u);
        else return fastGcd(y, x - y);
    }
}
           

标準化有理數，檢查是否能開根号将“無理數”化為有理數：

void Coordinate::simplifyRational() {
    // 化簡成分母為正數、分子符号不定的最簡分數
    assert(isRational);

    // now bottom != 0
    // 6 / -4 --> -3 / 2
    if (bottom < 0) {
        top = -top;
        bottom = -bottom;
    }

    // now bottom > 0 ---> gcd != 0
    ll gcd = fastGcd(abs(bottom), abs(top));
    top /= gcd;
    bottom /= gcd;
}

void Coordinate::simplifySqrt(ll add, ll coeff, ll insqrt, ll btm) {
    // 檢查是否可開根号成有理數
    ll tryRoot = sqrt(insqrt);
    if (tryRoot * tryRoot == insqrt) {  // actually a RATIONAL !
        isRational = true;
        top = add + coeff * tryRoot;
        bottom = btm;
        simplifyRational();
    }
}
           

坐标數值的哈希函數與點的哈希函數：

std::size_t Coordinate::hashCode() const {
    if (isRational) {
        std::size_t h1 = std::hash<long long>{}(top);
        std::size_t h2 = std::hash<long long>{}(bottom);
        // 參考标準庫的寫法，将兩子成員的哈希值合并
        return ((h1 ^ (h2 << 1u)) << 1u) | 1u;
    } else {
        std::size_t h = std::hash<double>{}(value);
        // 有先驗知識：有理數≠無理數
        // 有理數的哈希值末尾為1，無理數的哈希值末尾為0
        return (h << 1u) | 0u;
    }
}

struct hashCode_Point {
    std::size_t operator()(const Point &point) const {
        std::size_t h1 = point.x.hashCode();
        std::size_t h2 = point.y.hashCode();
        // 參考标準庫的寫法，将兩子成員的哈希值合并
        return h1 ^ (h2 << 1u);
    }
};
           

點的判等函數：

struct equals_Point {
    bool operator()(const Point &lhs, const Point &rhs) const {
        // 按成員比較。注意有先驗知識：有理數≠無理數
        bool x_eq = false, y_eq = false;
        if (lhs.x.isRational) {
            x_eq = (rhs.x.isRational & (lhs.x.top == rhs.x.top) & (lhs.x.bottom == rhs.x.bottom));
        } else {
            // 無理數取小數點八位進行比較
            x_eq = ((!rhs.x.isRational) & ((long long)(lhs.x.value * 1e8) == (long long)(rhs.x.value * 1e8)));
        }
        if (lhs.y.isRational) {
            y_eq = (rhs.y.isRational & (lhs.y.top == rhs.y.top) & (lhs.y.bottom == rhs.y.bottom));
        } else {
            y_eq = ((!rhs.y.isRational) & ((long long)(lhs.y.value * 1e8) == (long long)(rhs.y.value * 1e8)));
        }
        return x_eq & y_eq;
    }
};
           

直線與圓求交點

兩兩求交點，共四種組合的自動比對：

// 使用 std::variant 和 std::visit 來實作“多态二進制函數” !

// 重載四種組合
std::vector<Point> intersection(Line x, Circle y);
std::vector<Point> intersection(Circle x, Line y);
std::vector<Point> intersection(Line x, Line y);
std::vector<Point> intersection(Circle x, Circle y);

// 類型的定義，相當于 union
using Geometry = std::variant<Line, Circle>;

// 重載()運算符以實作類型比對
struct interset_visitor {
    template<typename Shape1, typename Shape2>
    std::vector<Point> operator()(const Shape1 &lhs, const Shape2 &rhs) const {
        return intersection(lhs, rhs);
    }
};



// 定義hashSet，傳入哈希函數和判等函數
std::unordered_set<Point, hashCode_Point, equals_Point> container;

for (int i = 0; i < objCount; ++i) {
    for (int j = i + 1; j < objCount; ++j) {
        // 使用 std::visit 重定向四種重載的參數組合
        std::vector<Point> intersections = std::visit(interset_visitor{}, (*objs)[i], (*objs)[j]);
        for (Point p: intersections)
            container.insert(p);
    }
}
           

單元測試

為使程式跨平台且具有較好的可拓展性，筆者沒有采用VS自帶的單元測試架構，而是使用了其支援的 GoogleTest。

筆者針對坐标&點、幾何&求交這兩個主要功能和資料單元進行了數十項單元測試，測試點主要功能點如下所示：

• 坐标和點的構造與化簡 GoogleTest Code
  • 有理數的構造
  • 無理數的構造和求浮點值
  • 有理數的化簡
  • 複雜式化簡成有理數
  • 複雜式無法化簡成有理數
  • 分子分母各個位置上的負數、0、正數、極小值、極大值
  • 非法坐标（交點在無窮遠）
  • 随機參數對象
• 兩個幾何對象求交點 GoogleTest Code
  • 平行于坐标軸的直線
  • 非平凡的直線
  • 交點為有理數的直線
  • 交點為有理數的線-圓和圓-圓
  • 交點為無理數的線-圓和圓-圓
  • 線-圓相交、相切、相離
  • 圓-圓相交、内外切、内外離

運作結果為：

筆者使用Wolfram Alpha來輔助調試和擷取正确答案：

性能改進

筆者使用VS 2019 Community進行了效能分析測試，第一次測試結果如下：

可以看到，

operator <<

占了很多的時間，導緻判等函數占用很多時間，同時程式運作逾時。

這是因為為了簡單起見，在哈希表的判等中，筆者使用單元測試時驗證過的輸出函數将對象轉換成字元串，再進行字元串的比較。這樣時間主要浪費在了構造字元流、構造字元串和比較字元串上。

是以，筆者對其進行了改進，将使用輸出到字元串再比較替換成了按邏輯比較成員變量：

struct equals_Point {
    bool operator()(const Point &lhs, const Point &rhs) const {
        /* TIME-COSTING !!!
        std::ostringstream outstream1, outstream2;
        outstream1 << lhs;
        outstream2 << rhs;
        return outstream1.str() == outstream2.str();
        */
        bool x_eq = false, y_eq = false;
        if (lhs.x.isRational)
            x_eq = ...;
        else
            x_eq = ...;
        if (lhs.y.isRational) ...
        return x_eq & y_eq;
    }
};
           

第二次測試的結果如下：

可以看出，現在程式的主要運作時間花費分布十分合理，主要在求交點、構造交點、化簡交點、求最大公約數這一條調用鍊上。程式的運作時間也從100s縮短到了19s。

代碼風格與品質

筆者使用VS 2019 Community進行了代碼品質分析（Microsoft建議的分析），改正代碼後的結果如下：

其中關于freopen和scanf的警告，在此次作業確定調用方式正确、輸入資料正确的情況下，筆者為了效率和性能，沒有将其替換成freopen_s、scanf_s等，也沒有增加相應的代碼處理它們的傳回值。

最後一條警告的對象是下面一條語句：

ll insideSqrt;
...
ll possibleRoot = sqrt(insideSqrt);
           

工具警告我們将double轉成long long可能丢失資料，但我們明确知道

sqrt()

内部的值是long long型的整數，且取值範圍在\(\pm4\times 10^{10}\)内，開根号後取值範圍必定不會變大到與double的取值範圍相當，是以筆者明确知道此處的寫法是安全的且符合程式員本意的，是以有意忽略。