個人項目作業
前言
| 項目 | 内容 |
|---|---|
| 這個作業屬于哪個課程 | 北航2020春軟工 |
| 這個作業的要求在哪裡 | |
| 我在這個課程的目标是 | 學習并實踐軟體開發，提高團隊合作的能力 |
| 這個作業在哪個具體方面幫助我實作目标 | 個人開發實踐 |
| 我的教學班級 | 005 |
| 項目位址 | https://github.com/zhyixuan/intersect |
PSP表格
| PSP2.1 | Personal Software Process Stages | 預估耗時（分鐘） | 實際耗時（分鐘） |
| Planning | 計劃 | ||
| · Estimate | · 估計這個任務需要多少時間 | 10 | |
| Development | 開發 | ||
| · Analysis | · 需求分析 (包括學習新技術) | 180 | 240 |
| · Design Spec | · 生成設計文檔 | 30 | |
| · Design Review | · 設計複審 (和同僚稽核設計文檔) | 20 | |
| · Coding Standard | · 代碼規範 (為目前的開發制定合适的規範) | ||
| · Design | · 具體設計 | 40 | |
| · Coding | · 具體編碼 | 120 | 150 |
| · Code Review | · 代碼複審 | ||
| · Test | · 測試（自我測試，修改代碼，送出修改） | ||
| Reporting | 報告 | ||
| · Test Report | · 測試報告 | ||
| · Size Measurement | · 計算工作量 | ||
| · Postmortem & Process Improvement Plan | · 事後總結, 并提出過程改進計劃 | ||
| 合計 | 620 | 560 |
問題：測試與改進工作沒有完全完成，對C++不熟悉，學習新技術占了一定的時間。
解題思路描述
- 沒有想到其他辦法，是以采用了暴力求解。複雜度O(N2)。
- 題目保證有限個交點，是以不會出現兩直線重合
- 平行線間無交點。不平行的兩條直線必定相交于一點
-
如何描述直線
一般式都可以表達，是以選擇了一般式
-
根據給定的兩點求直線
先寫成兩點式：
$\frac{y - y_2}{y_1- y_2} = \frac{x - x_2}{x_1- x_2} $。
再化成一般式 $(y_1 - y_2)x + (x_2 -x_1)y + (x_1y_2 -x_2y_1) = 0$
是以
$$
A = y_1 - y_2,B = x_2 -x_1,C =x_1y_2 -x_2y_1
-
-
交點坐标公式
首先判斷是否平行，平行則無交點
- 平行的條件$A2B1-A1B2 =0$
-
交點坐标
x=\frac{C1B2-C2B1}{A1B2-A2B1},y =\frac{C1A2-C2A1}{A2B1-A1B2}
- 如何保證精度
- 使用double存儲，當兩個浮點數之差小于1e_15時，認為相等。
設計實作過程。設計包括代碼如何組織，比如會有幾個類，幾個函數，他們之間關系如何，關鍵函數是否需要畫出流程圖？單元測試是怎麼設計的？
- 類
- 點類
- x，y坐标
- 兩點重合：x,y分别相等（浮點數的相等）
- 直線類 A、B、C三個參數
- 點類
- 函數及其之間的關系
- 主函數
- 資料結構：vector來存儲直線。因為要求交點的個數，是以采用unordered_set來存儲交點。便于去重。
-
流程。比較簡單，不再畫出流程圖，下面簡述流程。
首先讀取指令行參數，打開輸入檔案依次讀取每一條直線并求解直線的A、B、C參數，将直線放入容器Vector中。
周遊每兩條直線，如果二者不平行，則計算兩者交點，并加入set中。
-
求直線交點
周遊所有直線，求交點。将交點放入set中。當兩條直線已經不再比較的時候，放入
- 重載unordered_set的相等方法，以判斷兩個交點是否為同一個。
- 主函數
代碼說明。展示出項目關鍵代碼，并解釋思路與注釋說明。
關鍵代碼：
Point類
class Point//一個點有x,y兩個坐标值
{
public:
Point();
Point(double x0, double y0);
double x;
double y;
};
直線類
class Line//直線的一般式為Ax+By+C=0.是以确定一條直線需要以下參數
{
public:
Line(long long x1, long long y1, long long x2, long long y2);
long long A;
long long B;
long long C;
};
求直線的三個參數
//根據數學公式直接得出
A = y1 - y2;
B = x2 - x1;
C = x1 * y2 - x2 * y1;
計算兩直線的交點
//根據數學公式直接得出
x = (c1 * b2 - c2 * b1) / (a2 * b1 - a1 * b2);
y = (c1 * a2 - c2 * a1) / (a1 * b2 - a2 * b1);
判斷坐标點相等
const double EPS = 1e-15;
bool double_equal(double a, double b) {
if (fabs(a - b) < EPS) {
return true;
}
return false;
}
思路說明
一條直線（一般式）應該具有3個參數(A,B,C)，平面坐标系上的坐标點應該有兩個參數(x,y)。是以先構造兩個類用于存儲直線和點。
使用vector儲存多條直線。在主函數中，每讀取到一條直線，就按照上面的方法計算出其參數A、B、C，并将這條直線放入vector數組中。
在讀取完所有的直線後，周遊每兩條直線，當二者不平行時，用上述代碼求解交點，并将求出的交點放入存儲交點的一個unorder_set的集合中。（開始用的set，但是發現自己寫的重載operator不太對，是以換成了用unorder_set）
最後将存儲交點的集合的大小輸出到output.txt即可。