天天看點
傳回

第一次軟體工程個人項目作業——algo for intersection

個人項目作業-求圖形交點個數

  • 教學班級：005
  • 項目位址：https://github.com/prime21/IntersectProject.git
項目 内容
本作業屬于北航 2020 年春軟體工程 部落格園班級連接配接
本作業是本課程個人項目作業 作業要求
我在這個課程的目标是 收獲團隊項目開發經驗，提高自己的軟體開發水準
這個作業在哪個具體方面幫助我實作目标 體驗MSCV開發的pipeline

解題思路

根據需求描述，我們不難得到所需軟體的運作流程，總體而言分為三步：

  • 解析指令行參數，擷取輸入檔案與輸出檔案的路徑
  • 從輸入檔案中擷取輸入，并對圖形參數進行解析，存儲于相應的資料結構中
  • 求解圖形之間的交點個數，并輸出
  1. 兩條直線的交點公式，聯立

\[A_1 x + B_1 y + C_1 = 0 \\

A_2 x + B_2 y + C_2 = 0

\]

解得

\[X = \frac{B_1 C_2 - B_2 C_1} {A_1 B_2 - A_2 B_1} \\

Y = \frac{B_1 C_2 - B_2 C_1} {A_1 B_2 - A_2 B_1}

  1. 兩個圓的交點公式\(C_1(O_1,r_1),C_2(O_2,r_2)\)

    不相交的情況$$ |O_1O_2| < |r_1-r_2|$$ 或者 \(|O_1O_2| > r_1+r_2\)

    其餘情況，考察連心線和交點弦的垂直關系，先求交點弦和連心線的交點\(P\)

    \(P = O_1 + \overrightarrow {i_{O_1O_2}} \times a\)

    其中$a = \frac {r_1^2 - r_2^2 + d^2} {2d} $

    然後在垂直方向上得到交點\(P' = P \pm \overrightarrow j \times h\)

    \(\overrightarrow j\)是\(\overrightarrow i\)的法向量，\(h = \sqrt{r_1^2 - a^2}\)

  2. 直線和圓的交點公式，考慮直線為向量式\(u = u_0 + t (u_1-u_0)\)，圓為\(C(O,r)\)

    由\(|uO| = r\)消去得\(|u_0 + t (u_1-u_0) - O| = r\) 為關于\(t\)的一個二次方程，解得兩個\(t\)，得交點

設計

資料結構

基本的向量運算類型

struct inter {
	double x;
	double y;
	inter() { x = 0; y = 0; }
	inter(double x, double y) : x(x), y(y) {}
	inter(poi p) : x(p.first * 1.), y(p.second * 1.) {}
	bool operator == (const inter& rhs) const {
		return dcmp(x - rhs.x) == 0 && dcmp(y - rhs.y) == 0;
	}
	bool operator < (const inter& rhs) const {
		int d = dcmp(x - rhs.x);
		if (d < 0) return true;
		if (d > 0) return false;
		if (dcmp(y - rhs.y) < 0) return true;
		return false;
	}

	friend inter operator + (const inter& lhs, const inter& rhs) {
		return inter(lhs.x + rhs.x, lhs.y + rhs.y);
	}

	friend inter operator - (const inter& lhs, const inter& rhs) {
		return inter(lhs.x - rhs.x, lhs.y - rhs.y);
	}

	friend inter operator / (const inter& lhs, const double& d) {
		return inter(lhs.x / d, lhs.y / d);
	}
	
	friend inter operator * (const inter& lhs, const double& d) {
		return inter(lhs.x * d, lhs.y * d);
	}

	friend double operator * (const inter& lhs, const inter& rhs) {
		return lhs.x * rhs.x + lhs.y * rhs.y;
	}

	double length() {
		return sqrt(x * x + y * y);
	}

	double length2() {
		return x * x + y * y;
	}
};

複雜度分析

考慮到枚舉所有線和圓的交點情況，并對所有交點排序，複雜度是\(O( n ^2 + m \log m)\)其中\(n\)是線和圓的個數，\(m\)是交點個數。

代碼實作

代碼組織

三種交點的函數

void addLineInter(int i, int j) {
	line *lhs = (line *)(pro[i]);
	line *rhs = (line *)(pro[j]);
	
	long long D = (lhs->A * rhs->B) - (rhs->A * lhs->B);

	if (D == 0) return ;
	double xx = (lhs->B * 1. * rhs->C) - (rhs->B * lhs->C);
	double yy = (lhs->A * 1. * rhs->C) - (rhs->A * lhs->C);

	gb_in.push_back(inter(xx / D, yy / D));
}
           
void addCircleInter(int i, int j) {
	circle* lhs = (circle*)(pro[i]);
	circle* rhs = (circle*)(pro[j]);

	long long dis = (lhs->o.first - rhs->o.first) * (lhs->o.first - rhs->o.first) + (lhs->o.second - rhs->o.second) * (lhs->o.second - rhs->o.second);

	if (dis > (lhs->r + rhs->r) * (lhs->r + rhs->r)) return; 
	if (dis < (lhs->r - rhs->r) * (lhs->r - rhs->r)) return;
	
	double alpha = dis + lhs->r * lhs->r - rhs->r * rhs->r;
	alpha /= 2 * sqrt(dis);

	double h = std::sqrt(lhs->r * lhs->r - alpha * alpha);

	inter o1o2 = inter(rhs->o) - inter(lhs->o);
	o1o2 = o1o2 / o1o2.length();
	inter vert = inter(o1o2.y, -o1o2.x);
	inter P = inter(lhs->o) + o1o2 * alpha;
	inter Q = P + vert * h;
	gb_in.push_back(Q);
	Q = P - vert * h;
	gb_in.push_back(Q);
}
           
void addLcInter(int i, int j) {
	line* lhs = (line*)(pro[i]);
	circle* rhs = (circle*)(pro[j]);

	inter li = inter(lhs->b) - inter(lhs->a);
	inter lc = inter(lhs->a) - inter(rhs->o);

	double A = li.length2();
	double B = (lc * li) * 2;
	double C = lc.length2() - (rhs->r) * (rhs->r);

	double delta = B * B - 4 * A * C;
	if (delta >= 0) {

		delta = sqrt(delta);

		double x1 = (delta - B) / (2 * A);
		double x2 = (-delta - B) / (2 * A);

		inter t1 = inter(lhs->a) + li * x1;
		inter t2 = inter(lhs->a) + li * x2;
		gb_in.push_back(t1);
		gb_in.push_back(t2);
	}
}

不同情況下的傳回值處理

測試

使用了OpenCPPCoverage

第一次軟體工程個人項目作業——algo for intersection

代碼品質分析

Reshaper C++

性能改進

  1. 掃描線做法，可以觀察交點前後的關系如下：
第一次軟體工程個人項目作業——algo for intersection

注意到直線相交之後兩條直線在y軸方向的大小關系發生了一次改變

第一次軟體工程個人項目作業——algo for intersection

同理，圓在相交的時候，某個圓的上半圓和某個圓的下半圓的位置關系也發生了一次改變

故可以維護一個關于x軸的掃描線，線上的每一個點需要标記為L(x, k) 或者 C(O,r,up/down) 随時計算y軸對應的值。

在每次插入新點的時候，需要考察最靠近的兩個點是否會與其相交，如果會需要插入事件。

故需要維護一個序列支援查詢前驅後繼，删除和添加元素，采用平衡樹可以完成這一任務。

故這樣的時間複雜度是\(O(n \log n + k)\)的。性能得到了提升

做法需要解決一些問題：

  • 多線共點，這樣可能會産生多個同時間的時間點，和交叉關系
  • 圓的上下半圓自交問題
  • 圓的變換關系

事後總結

由于本次任務的需求是确定的，沒有太多需要揣測的地方，是以需求分析花費的時間比較少。

PSP 表格

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