軟工個人項目

項目	内容
所屬課設：北航2020年春軟體工程	班級部落格
作業要求：實作一個能求解簡單幾何形狀之間交點的控制台程式。	作業要求
個人課程目标	學習一個具備一定規模的軟體在生命周期中需要哪些工作，鍛煉自己的團隊協作能力，并使自己具有開發一個“好軟體”的能力
教學班級	006
這個作業在哪個具體方面幫助我實作目标	提升個人的軟體工程能力
項目位址	https://github.com/NSun-S/SoftwareEngineering_PersonalWork

PSP估算

在開始實作程式之前，在下述 PSP 表格記錄下你估計将在程式的各個子產品的開發上耗費的時間。（0.5'）

在你實作完程式之後，在下述 PSP 表格記錄下你在程式的各個子產品上實際花費的時間。（0.5'）

PSP2.1	Personal Software Process Stages	預估耗時（分鐘）	實際耗時（分鐘）
Planning	計劃	20	10
Estimate	估計這個任務需要多少時間
Development	開發	630	510
Analysis	需求分析 (包括學習新技術)	60	30
Design Spec	生成設計文檔	40
Design Review	設計複審 (和同僚稽核設計文檔)
Coding Standard	代碼規範 (為目前的開發制定合适的規範)
Design	具體設計		80
Coding	具體編碼	120	150
Code Review	代碼複審
Test	測試（自我測試，修改代碼，送出修改）
Reporting	報告		50
Test Report	測試報告
Size Measurement	計算工作量
Postmortem & Process Improvement Plan	事後總結, 并提出過程改進計劃
合計	650	520

在任務完成後回顧這個表格，我發現我做得還算不錯，總體時間小于預估，但是debug的時間較長，這也是測試花費大量時間的原因。

思路及設計

在拿到題目之後，我很快定位出這是一道代數幾何題，我們需要用自己學過的平面圖形的相關知識來求解問題，這個問題分為3部分：直線和直線的交點，圓和圓的交點以及圓和直線的交點。

是以，我先是在紙上進行了演算，直線和直線的交點很好推理，圓和圓的可以轉換圓和直線的交點，那麼我們求解的關鍵就是圓和直線的交點，是以我查閱了求解這個問題的相關資料，找到了解決辦法。

設計實作過程

這部分完成的比較輕松，因為有面向對象的基本知識，是以在這到題中，我自然的設計了兩個類，圓和直線。

上圖是直線類的定義，我們可以看出，其中包含了确定直線的兩個點的坐标，以及一個用來求解直線和直線交點的函數。

上圖是圓類的定義，其中包含圓的中心點和半徑，此外，還有計算垂足，計算直線到圓的距離以及求解圓和直線交點以及圓和圓交點的函數，單元測試中我主要測試了各種類型的直線之間交點的例子。

改程序式性能

這個過程經曆了兩個階段：

使用set存放pair作為資料結構，利用set的不重複性來求解。
使用vector存放pair作為資料結構，最後對vector進行去重。

個人項目作業

上面兩張圖是我們階段1分别用随機生成的1000條直線（約50w交點）和3000條直線（約450w交點）測試cpu的截圖，從中我們可以看出，随着交點個數以近$n^2$的比例增長，時間也大幅度的增長。

上圖是3000條指令是對應的時間消耗占比，我們可看出，對set的操作花費了大量的時間。以下是其中消耗時間最長的函數：

bool line::intersect(line line2, set<pair<double, double>>& intersections)
{
	double x3 = line2.x1;
	double x4 = line2.x2;
	double y3 = line2.y1;
	double y4 = line2.y2;
	double Determinant = (y1 - y2) * (x3 - x4) - (y3 - y4) * (x1 - x2);
	if (fabs(Determinant) < 1e-6) return false;
	double intersect_x = (-(x1 - x2) * (y3 * x4 - x3 * y4) + (x3 - x4) * (y1 * x2 - x1 * y2)) / Determinant;
	double intersect_y = (-(y1 - y2) * (y3 * x4 - x3 * y4) + (y3 - y4) * (y1 * x2 - x1 * y2)) / Determinant;
	intersections.insert(make_pair(intersect_x, intersect_y));
	return true;
}

第二個階段我們改用vector之後，用相同3000條資料測試的效果圖見上圖，從中可以看出，我們的cpu時間不僅獲得了僅10s的縮減，瓶頸部分也發生了轉變。

項目關鍵代碼

求解直線和直線交點

bool line::intersect(line line2, vector<pair<double, double>>& intersections)
{
	double x3 = line2.x1;
	double x4 = line2.x2;
	double y3 = line2.y1;
	double y4 = line2.y2;
	double Determinant = (y1 - y2) * (x3 - x4) - (y3 - y4) * (x1 - x2);
	if (fabs(Determinant) < 1e-6) return false;
	double intersect_x = (-(x1 - x2) * (y3 * x4 - x3 * y4) + (x3 - x4) * (y1 * x2 - x1 * y2)) / Determinant;
	double intersect_y = (-(y1 - y2) * (y3 * x4 - x3 * y4) + (y3 - y4) * (y1 * x2 - x1 * y2)) / Determinant;
	intersections.push_back(make_pair(intersect_x, intersect_y));
	return true;
}

這個函數就是我們上一小節中改進後的瓶頸函數，但也是我們程式中最核心的部分。我先是在紙上對兩個點确立的直線方程進行了推導，其實就是将兩個形如$y = kx + b$的方程聯立，直接得到上述代碼中的結果。

求解圓和直線的交點

int circle::intersectLine(line line1, vector<pair<double, double>>& intersections)
{
	double distance = getDistance(line1);
	if (distance > r)
	{
		//cout << "???" << endl;
		return 0;
	}
	pair<double, double> foot = getFoot(line1);
	if (distance == r)
	{
		intersections.push_back(foot);
		return 1;
	}
	double length = sqrt(r*r - distance*distance);
	if (line1.x1 == line1.x2)
	{
		intersections.push_back(make_pair(foot.first, foot.second + length));
		intersections.push_back(make_pair(foot.first, foot.second - length));
	}
	else
	{
		double cof = (line1.y1 - line1.y2) / (line1.x1 - line1.x2);
		double x = 1 / sqrt(cof * cof + 1);
		double y = cof / sqrt(cof * cof + 1);
		intersections.push_back(make_pair(foot.first + x * length, foot.second + y * length));
		intersections.push_back(make_pair(foot.first - x * length, foot.second - y * length));
	}
	return 2;
}

可以看出，我們先是進行了直線和圓心距離的計算，然後根據計算的結果決定兩者之間的關系。其中對一種較為特殊的情況進行了讨論，即直線與y軸平行，這種情況下直線的斜率不存在，無法根據斜率進行計算。

圓與圓求交點

int circle::intersectCircle(circle circle2, vector<pair<double, double>>& intersections)
{
	double distance = sqrt(circle2.r * circle2.r - r * r);
	if (distance > (r + circle2.r) || distance < fabs(r - circle2.r)) return 0;
	double right = circle2.r * circle2.r - r * r + c1 * c1 - circle2.c1 * circle2.c1 
		+ c2 * c2 - circle2.c2 * circle2.c2;
	if (circle2.c1 == c1)
	{
		double y = -right / (2 * circle2.c2 - 2 * c2);
		line line1 = line(1, y, -1, y);
		return intersectLine(line1, intersections);
	}
	else if(circle2.c2 == c2)
	{
		double x = -right / (2 * circle2.c1 - 2 * c1);
		line line1 = line(x, 1, x, -1);
		return intersectLine(line1, intersections);
	}
	else
	{
		line line1 = line(0, -right/(2 * circle2.c2 - 2 * c2), -right / (2 * circle2.c1 - 2 * c1), 0);
		return intersectLine(line1, intersections);
	}
}

這個函數中我們先對圓之間的關系進行了判斷，相離和内含的情況去掉後，隻保留有交點的情況，我們知道圓和圓的方程直接做差就是交點連線的方程，我特判了其中的兩種情況，圓心連線平行和垂直于y軸的情況。然後我們利用推導出來的公式從連線上取兩個特殊的點，就确定了這條直線，然後求解已知圓和直線的交點方程即可。

單元測試和警告消除

單元測試結果圖

個人項目作業

這部分我主要對直線間交點的正确性進行了測量，10個測試樣例覆寫了直線相交的各種情況，一條直線、兩條平行線、兩條相交線、三條平行線、三條直線一個交點、三條直線兩個交點、三條直線兩兩相交、四條直線五個交點、四條直線六個交點等多種多樣直線間可能的互相關系進行了測試，一小見大，通過保證各種數量較少的直線的正确性來保證程式能正确處理多條直線間的情況。

不足之處在于圓圓之間、圓和直線之間的測試并未通過單元測試進行。

編譯運作結果圖

個人項目作業

個人項目作業