結對程式設計

教學班級：006
項目位址：
https://github.com/Pandapan-Buaa/IntersectInPair.git

PSP 表格

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

Information Hiding，Interface Design，Loose Coupling

Information Hiding：對資料進行封裝，讓外部不能随便通路。由于本次作業的計算比較多，為了提高效率，并沒有遵守這個原則，類的成員變量都被設為public。

Loose Coupling：松耦合。每個子產品自身是一個整體，各個子產品之間的依賴盡可能少，這樣修改一個子產品時，就不用修改其他的子產品。我們的核心計算子產品向UI子產品提供了添加和删除圖形的兩個接口，UI子產品不用考慮計算子產品的具體實作，隻需要調用接口函數，UI子產品和計算子產品之間的耦合比較低。

計算子產品接口的設計與實作過程

與上次作業類似，本次作業裡隻有三個類(點/向量、線、圓)及其公共常用函數以及三個求解函數，在類中隻需對應屬性以及提供向量計算的相關函數，并在三個求解函數中對類的交點進行求解。

求解函數的關鍵代碼如下：

其中line.isOnLine()是判斷點是否線上段/射線上的簡單方法，其實作則是根據直線/線段/射線的向量方程 l = u + tv ，u是直線上一點，v是方向向量，t是系數，計算出t則易判斷是否在所給線上。

void lineIntersectLine(const Line& l1, const Line& l2)
{
	if (dcmp(l1.v ^ l2.v) == 0)	return;
	Vector u = l1.p - l2.p;
	double t = (l2.v ^ u) / (l1.v ^ l2.v);

	Point temp = l1.p + l1.v * t;
	if (l1.type != "L" && !l1.isOnLine(temp))	return;
	if (l2.type != "L" && !l2.isOnLine(temp))	return;

	try {
		points.insert(temp);
	}
	catch(exception e){}
}

void lineIntersectCircle(const Line& L, const Circle& C)
{
	double t1, t2;
	double a = L.v.x, b = L.p.x - C.c.x, c = L.v.y, d = L.p.y - C.c.y;
	double e = a * a + c * c, f = 2 * (a * b + c * d), g = b * b + d * d - C.r * C.r;
	double delta = f * f - 4 * e * g;
	if (dcmp(delta) < 0)    return; //線圓相離
	if (dcmp(delta) == 0) {		    //線圓相切
		t1 = t2 = -f / (2 * e);
		if (L.type != "L" && !L.isOnLine(t1))	return;
		try {
			points.insert(L.point(t1));
		}
		catch (exception e) {
		}
		return;
	}
	//線圓相交
	t1 = (-f - sqrt(delta)) / (2 * e);
	t2 = (-f + sqrt(delta)) / (2 * e);
	Point p1 = L.point(t1);
	Point p2 = L.point(t2);
	if (L.type != "L" && !L.isOnLine(p1));
	else {
		try {
			points.insert(p1);
		}
		catch (exception e) {
		}
	}

	if (L.type != "L" && !L.isOnLine(p2));
	else {
		try {
			points.insert(p2);
		}
		catch (exception e) {
		}
	}
	return;
}

void circleIntersectCircle(const Circle& c1, const Circle& c2)
{
	double d = Length(c1.c - c2.c);
	if (dcmp(d) == 0) return; //兩圓重合
	if (dcmp(c1.r + c2.r - d) < 0)    return;
	if (dcmp(fabs(c1.r - c2.r) - d) > 0)    return;
	double a = angle(c2.c - c1.c);
	double da = acos((c1.r * c1.r + d * d - c2.r * c2.r) / (2 * c1.r * d));
	Point p1 = c1.point(a - da), p2 = c1.point(a + da);
	try {
		points.insert(p1);
	}
	catch (exception e) {
	}
	if (p1 == p2)	return;
	try {
		points.insert(p2);
	}
	catch (exception e) {
	}
}

獨到之處在于：用計算幾何的方法，簡潔高效的解決了核心代碼的拓展部分。

計算子產品接口部分的性能改進

性能改進方面依然沒有想出更優複雜度的算法，隻能夠進行一些細節上的優化。由于C++的set是基于紅黑樹實作的，插入操作的複雜度為O（logn），是以考慮了換成基于哈希表實作的unordered_set, 在哈希函數理想的情況下，插入操作的複雜度為O(1)。換了unordered_set之後性能确實有了提升，在1000條直線，400000個交點的情況下，所用時間從9秒左右提升到了6秒左右。

Design by Contract

Design by Contract就是契約式程式設計，在大二的面向對象課程有過了解。這種方法規定了函數的前提條件，後繼條件，不變量條件等，優點是嚴格區分了責任，讓每個人隻用關心自己的代碼正确性。缺點是可能會在函數各種條件的考慮上花費很多時間。

項目中并沒有嚴格地使用契約式程式設計，隻是規定了一些接口的作用，參數，傳回值。

計算子產品部分單元測試展示

在構造測試資料時，兩兩組合，分為L_L，R_R, S_S, L_R, L_S, L_C, R_S, R_C, S_C, C_C十種情況。

首先把能想到的情況進行了測試，比如直線相交，直線平行，射線端點，直線與圓相交，相切，相離等情況，然後根據覆寫率工具顯示的未覆寫的分支，再添加對應的測試資料。

測試覆寫率：

計算子產品部分異常處理說明

隻設計了一個異常類，定義了五種異常類型。

WRONGTYPE: 輸入了L, R, S, C之外的不支援的類型。

WRONGFORMAT: 輸入了不符合規範的格式。

BADPOINT: 輸入的點的坐标不在（-100000，100000）範圍内。

BADLINE: 輸入的直線的兩個端點重合。

BADCIRCLE: 輸入的圓的半徑r小于等于0。

界面子產品的詳細設計過程

首先決定采用基于C++的QT編寫UI，在資料查詢的過程中，我發現了QT的第三方庫QcustomPlot，看完其基本示範後，發現能夠較為簡單的實作類似GeoGebra的界面放縮和繪制功能，是以決定以QT+QcustomPlot完成UI任務。在閱讀完《Qt5.9 c++開發指南》的前四章以及第七章IO處理之後，我認為已有的知識已經足夠了，是以開始查詢QcustomPlot官方文檔以及答疑，同時進行UI代碼編寫。

UI界面如上，共有四個Button（分别負責繪制圖像、交點、添加、删除，其中添加删除格式與輸入格式一緻，例如“L 0 0 1 1”），一條menubar(負責打開文本檔案),一個TextEdit(負責顯示文本檔案以及輸入)，一個結果Lable(顯示交點數目)，以及QcustomPlot區域（繪圖），由于QT是可以可視化拖動子產品并自動對其産生代碼的，是以該部分的設計實作并不是人工的。

接着為了實作上述的功能，需要利用QT中的信号與槽機制，按鈕的信号在其庫中已有定義，需要寫的是按鈕按下後的反應，即按鈕對應的槽，如下：

private slots:
    void on_actOpen_triggered();
    void on_AddBtn_clicked();
    void on_DelBtn_clicked();
    void on_PaintBtn_clicked();
    void on_PointBtn_clicked();

具體代碼過長就不做展示了。這些槽函數定義了按鈕的反應，Add和Del對應的是核心代碼接口，這裡主要講兩個繪制按鈕的槽。

根據QcustomPlot官方文檔可知其對圓，直線，射線，點均有多種不同實作方法，但大體而言分兩類，一類在Graph對象中添加點集，形成圖像；另一類AbstractItem則是直接對圖像進行繪制（這裡的原理并未細究，但其繪制速度是遠超于點繪制的）。是以我編寫了不同的繪制函數，如下：

void paintPoint(QCustomPlot *customPlot,double x,double y);
    void paintLine(QCustomPlot *customPlot,double x1, double y1, double x2, double y2);
    void paintRay(QCustomPlot *customPlot,double x1, double y1, double x2, double y2);
    void paintSegment(QCustomPlot *customPlot,double x1, double y1, double x2, double y2);
    void paintCircle(QCustomPlot *customPlot,double x1, double y1, double x2, double y2);

經測試，在500000數量級的繪制下均可以保持使用流暢（當然，繪制需要時間，該庫還提供了Opengl加速，但我并未實驗）

界面子產品與計算子產品的對接

由于提前設計了接口

void add_diagram(char T, int x1, int y1, int x2, int y2);
void sub_diagram(char T, int a, int b, int c, int d);
void calPoints();
set<pair<double, double>> uiPoints;

是以在對接時隻需要在四個按鈕對應槽中合理調用接口即可。

實作的功能：

支援從檔案導入幾何對象的描述。

左上角File處可以添加檔案，并顯示在下方文本框中。
支援幾何對象的添加、删除。

按下Add,Del按鈕會添加/删除文本框中的集合對象
支援繪制現有幾何對象。

PaintGraph按鈕實作
支援求解現有幾何對象交點并繪制。

PaintPoint按鈕實作
坐标系放縮，平移（數量級10^-5 ~ 10^250）

結對過程

騰訊會議螢幕共享截圖

日常微信交流截圖