| 項目 | 内容 |
|---|---|
| 這個作業屬于哪個課程 | 2020春季計算機學院軟體工程（羅傑 任建） |
| 這個作業的要求在哪裡 | 個人項目作業 |
| 我在這個課程的目标是 | 學習軟體工程相關知識，培養自己獨立和團隊開發能力 |
| 這個作業在哪個具體方面幫助我實作目标 | 學會使用Visual Studio進行代碼的效能分析，熟悉個人軟體開發流程 |
| 作業正文...... | 見下文 |
| 其他參考 | 見文中“參考資料”的連結 |
| 教學班級 | 005 |
| 項目位址 | https://github.com/yangjiuchun123/SE_personal_homework.git |
PSP2.1表格
| PSP2.1 | Personal Software Process Stages | 預估耗時（分鐘） | 實際耗時（分鐘） |
|---|---|---|---|
| Planning | 計劃 | ||
| · Estimate | · 估計這個任務需要多少時間 | 20 | |
| Development | 開發 | ||
| · Analysis | · 需求分析 (包括學習新技術) | 40 | 80 |
| · Design Spec | · 生成設計文檔 | ||
| · Design Review | · 設計複審 (和同僚稽核設計文檔) | ||
| · Coding Standard | · 代碼規範 (為目前的開發制定合适的規範) | 10 | |
| · Design | · 具體設計 | 30 | |
| · Coding | · 具體編碼 | 100 | |
| · Code Review | · 代碼複審 | ||
| · Test | · 測試（自我測試，修改代碼，送出修改） | 200 | |
| Reporting | 報告 | ||
| · Test Report | · 測試報告 | 60 | |
| · Size Measurement | · 計算工作量 | ||
| · Postmortem & Process Improvement Plan | · 事後總結, 并提出過程改進計劃 | ||
| 合計 | 440 | 595 |
表格中，測試所用的時間比預期的高了很多，主要原因是這其中還包含了寫單元測試以及自動生成測試樣例程式的時間，這些是原來沒有預想到的。此外需求分析的時間也比預估多了一些，這是因為網上查閱的資料中，那些複雜的數學推導要去驗證正确性花了比計劃要多的時間。
解題思路
本題最簡單的思路就是暴力枚舉法：每次選取兩條直線（或一條直線和一個圓，或兩個圓），首先判斷他們是否相交，如果相交就求出它們的交點坐标并存入一個set中，周遊完所有的圖形對之後，set中的元素個數即為交點個數。以下分情況讨論交點的坐标。
（1）兩條直線的交點
兩條直線的交點坐标比較容易求，可以通過簡單的數學推導得到：
首先由于直線是以兩點式$(x1，y1)，(x2，y2)$的形式給出的，我們要先把它轉化為一般式，友善計算，即：
$L: ax+by+c=0$，其中$a=y1-y2，b=x2-x1，c=x1y2-x2y1。$
之後可以求出兩直線$L1: a1x+b1y+c1=0$和$L2: a2x+b2y+c2=0$交點的坐标為：
$x = (b1c2 - b2c1) / d, y = (a2c1 - a1c2) / d$，其中$d=a1b2-a2b1$，$d$為$0$時意味着兩直線平行，沒有交點。
參考資料：求兩直線交點坐标
（2）兩個圓的交點
這個數學推導非常複雜麻煩，直接解方程基本不可能解得出來，上網查閱資料後發現有使用參數方程的解法，但是其中還需要根據結果的三角函數值進行分類讨論以确定正負号的問題，這會使程式測試起來比較困難，是以我沒有采用。後面看到有使用Matlab來解方程，直接求出解析解的方法，我認為這種方法雖然簡單粗暴，但不需分類讨論可以直接得到通解，是個比較好的方法，故我選擇了使用Matlab來進行方程的求解，解出的式子也非常長，就不放在這裡了。需要注意的是，當兩圓沒有交點的時候，Matlab求出來的解是沒有意義的，是以在直接套公式之前需要判斷一下。
求解的Matlab代碼如下：
clear all
syms a1 b1 R1 a2 b2 R2 x y;
[x,y]=solve((x-a1)*(x-a1)+(y-b1)*(y-b1)-R1*R1,(x-a2)*(x-a2)+(y-b2)*(y-b2)-R2*R2);
%simplify(x)
%simplify(y)
參考資料：參數方程的解法
Matlab解法
（3）一條直線和一個圓的交點
這個數學推導也比較複雜，在發現Matlab這個好用的工具之後，這次我直接使用了Matlab聯立兩個方程來求出解析解，解出的式子也非常長，同樣不放在這裡了。需要注意的是直線與圓的交點數量可能有三種情況：沒有交點、有一個交點、有兩個交點。而Matlab解出來的x與y分别有兩個，如果直接使用x與y的公式可能會出現根号下為負的情況（因為原方程在實數域内不一定有解），故我們應該首先判斷直線與圓是否有交點，如果有交點才可以套用公式。此外，Matlab解出的方程在直線的斜率為0時會出現除數為0的情況，是以需要特判一下直線的斜率是否為0。
clear all
syms a1 b1 c1 a b r x y;
[x,y]=solve((x-a)*(x-a)+(y-b)*(y-b)-r*r, a1*x+b1*y+c1);
%simplify(x)
%simplify(y)
實作過程
設計上我最初的想法是3個類：一個shape類，一個line類，一個circle類。line類和circle類均是由shape類繼承而來。顧名思義，line類存儲直線的相關屬性，而circle類存儲圓的相關屬性。shape類裡記錄了該圖形的類型，即是L（line）還是C（circle），line類裡存儲了直線的兩點坐标，circle類裡存了圓心坐标和半徑，兩個類均有一個showStatus函數來輸出它們的所有屬性，以便調試。
不過後來，我在嘗試單元測試的時候發現，單元測試是針對某一個類進行的測試，但我的主要算法并不在某一個類裡，而直接寫成了函數，這樣無法進行單元測試。是以後來我将求解交點個數的過程重新整合為一個Solve類，這樣友善單元測試的進行。單元測試就主要測試這個Solve類的函數，包括getIntersect（求解總的交點個數）、LLintersect（求解兩條直線的交點坐标）、CCintersect（求解兩個圓的交點坐标）、CLintersect（求解圓和直線的交點坐标）。
總體來看函數雖然公式很複雜，但是邏輯上并不複雜，就不需要畫出流程圖了。
性能改進
整個算法使用的是暴力枚舉法，是以時間複雜度為$O(n^2)$。我也曾思考過有沒有什麼更好的方法，并上網查閱了有關的資料，但很多題目都有個前提條件就是“無三線共點”，例如C++ 計算直線的交點數這道題。這和我們的題目要求是有差距的，如果無三線共點可以使用動态規劃解，不需要考慮交點的坐标；而如果沒有這個前提，那麼還需要考慮交點重合的問題，因而必須計算出坐标，用動态規劃解就比較困難了。
是以在性能改進這部分我隻能做一些局部計算上的性能改進，例如減少一些重複的計算過程等，重複計算的情況在用Matlab求出的交點坐标公式中還是比較常見的，是以這部分确實有一些改進的空間。
性能改進這部分花了我大概一個多小時的時間，主要時間都在看網上的類似題目的代碼并思考能不能應用到我們的題目上，可惜并沒有什麼好的思路。最終采用的減少重複計算的改進花了半小時左右，因為公式很長很複雜，需要在整理的時候多加細心一些。
性能分析圖如下：
可以看到，LLintersect這個函數消耗的CPU比較多，這可能與測試資料中直線比較多有關，但這也是我或許可以提升性能的一個點。
代碼說明
1、Solve類的getIntersect函數的代碼：
void Solve::getIntersect(Shape* s1, Shape* s2, set<pair<double, double>>* interSet) { //計算兩條圖形的交點
char t1, t2;
t1 = s1->type;
t2 = s2->type;
if (t1 == 'L' && t2 == 'L') { //求兩直線的交點
LLintersect((Line*)s1, (Line*)s2, interSet);
}
else if (t1 == 'C' && t2 == 'C') { //求兩圓的交點
CCintersect((Circle*)s1, (Circle*)s2, interSet);
}
else { //求直線與圓的交點
if (s1->type == 'L' && s2->type == 'C') {
CLintersect((Circle*)s2, (Line*)s1, interSet);
}
else if (s1->type == 'C' && s2->type == 'L') {
CLintersect((Circle*)s1, (Line*)s2, interSet);
}
else {
cout << "something goes wrong!" << endl;
}
}
}
這個函數主要是判斷現在取出的兩個圖形分别是什麼，并分情況将它們交給其他的分類處理函數處理。由于我采用了一個shape類的指針數組來存儲所有的圖形，并依次取出一對計算交點，是以這裡取出的一對圖形都是shape類的，但下面的分類處理函數需要的參數都是circle或者line，是以需要将shape類進行強制類型轉換才能作為參數傳給下面的函數。
2、Solve類的CCintersect函數的代碼：
void Solve::CCintersect(Circle* c1, Circle* c2, set<pair<double, double>>* interSet) {
double a1 = c1->x;
double b1 = c1->y;
double r1 = c1->r;
double a2 = c2->x;
double b2 = c2->y;
double r2 = c2->r;
if ((pow((a1 - a2), 2) + pow((b1 - b2), 2)) > pow(r1 + r2, 2)) {
return; //兩圓不相交
}
else {
double value1 = a1 * a1 - 2 * a1 * a2 + a2 * a2 + b1 * b1 - 2 * b1 * b2 + b2 * b2;
double value2 = -r1 * r1 * a1 + r1 * r1 * a2 + r2 * r2 * a1 - r2 * r2 * a2 + a1 * a1 * a1 - a1 * a1 * a2 - a1 * a2 * a2 + a1 * b1 * b1 - 2 * a1 * b1 * b2 + a1 * b2 * b2 + a2 * a2 * a2 + a2 * b1 * b1 - 2 * a2 * b1 * b2 + a2 * b2 * b2;
double value3 = -r1 * r1 * b1 + r1 * r1 * b2 + r2 * r2 * b1 - r2 * r2 * b2 + a1 * a1 * b1 + a1 * a1 * b2 - 2 * a1 * a2 * b1 - 2 * a1 * a2 * b2 + a2 * a2 * b1 + a2 * a2 * b2 + b1 * b1 * b1 - b1 * b1 * b2 - b1 * b2 * b2 + b2 * b2 * b2;
double sigma = sqrt((r1 * r1 + 2 * r1 * r2 + r2 * r2 - a1 * a1 + 2 * a1 * a2 - a2 * a2 - b1 * b1 + 2 * b1 * b2 - b2 * b2) * (-r1 * r1 + 2 * r1 * r2 - r2 * r2 + value1));
double p1_x = (value2 - sigma * b1 + sigma * b2) / (2 * value1);
double p2_x = (value2 + sigma * b1 - sigma * b2) / (2 * value1);
double p1_y = (value3 + sigma * a1 - sigma * a2) / (2 * value1);
double p2_y = (value3 - sigma * a1 + sigma * a2) / (2 * value1);
(*interSet).insert(pair<double, double>(p1_x, p1_y));
(*interSet).insert(pair<double, double>(p2_x, p2_y));
return;
}
}
這裡首先需要判斷兩圓是否相交，如果不相交則直接return即可。後面則是通過Matlab解出的公式來計算兩個交點的坐标，注意到在公式中很多的項的組合是重複的，是以可以将這些重複項先算出來，以減少計算量。算出兩個交點的坐标後，把它們作為一個pair加入到set當中，這樣即使是兩個相同的交點也可以自動去重。
消除警告的截圖
