| 項目 | 内容 |
|---|---|
| 所屬課程 | 2020年春季計算機學院軟體工程(羅傑 任健) |
| 作業要求 | 個人項目作業 |
| 課程目标 | 切身參與完整的軟體開發流程，積累專業技術知識和團隊合作經驗 |
| 本次作業實作方面 | 體驗完整的項目開發流程，加深對于PSP的了解 |
| 教學班級 | 006(周五上午三四節) |
| 項目位址 | https://github.com/Miracle-dz/IntersectProject |
一、PSP表格
| PSP2.1 | Personal Software Process Stages | 預估耗時(分鐘) | 實際耗時(分鐘) |
|---|---|---|---|
| Planning | 計劃 | ||
| · Estimate | · 估計這個任務需要多少時間 | 20 | |
| Development | 開發 | ||
| · Analysis | · 需求分析 (包括學習新技術) | 60 | |
| · Design Spec | · 生成設計文檔 | 15 | |
| · Design Review | · 設計複審 (和同僚稽核設計文檔) | ||
| · Coding Standard | · 代碼規範 (為目前的開發制定合适的規範) | 10 | |
| · Design | · 具體設計 | 90 | |
| · Coding | · 具體編碼 | 120 | 180 |
| · Code Review | · 代碼複審 | 45 | 75 |
| · Test | · 測試（自我測試，修改代碼，送出修改） | ||
| Reporting | 報告 | ||
| · Test Report | · 測試報告 | ||
| · Size Measurement | · 計算工作量 | ||
| · Postmortem & Process Improvement Plan | · 事後總結, 并提出過程改進計劃 | 30 | 50 |
| 合計 | 525 | 710 |
二、解題思路描述
整個題目讀下來，感覺是比較簡單的平面幾何問題，由于圓和直線的内容并不複雜，是以并沒有去查閱太多數學方面的資料，整體的想法就是最簡單的将每兩個幾何對象的方程聯立，代入求解。反倒是在想實作代碼的資料結構時費了些功夫，考慮到若兩兩聯立，必然會導緻出現在三個及以上的幾何對象上的點被重複計數，這就需要進行存儲時的判重處理，而且由于點的坐标隻能使用浮點類型無法精确表示，故判斷相等的方法和精度選擇也十分重要，查閱了C++的各種STL，其中set和HashMap都能夠實作高效的查詢和判重，而對于自定義類型的set，需要重載小于運算符<保證查重時的判斷，正好可以利用這一特點在重載方法中嵌入對于浮點數精度的判斷，進而實作目的效果。
三、設計實作過程
- Point類：存儲交點的浮點型坐标，重載<符号用于set并設定精度為1e-8的相等判斷。
class Point {
public:
double x;
double y;
Point(double x, double y) {
this->x = x;
this->y = y;
}
bool operator<(const Point& p) const {//使用自定義類型的set需要重載<運算符
if (x < p.x && p.x - x > 1e-8) {
return true;
}
else {
if (fabs(x - p.x) <= 1e-8 && y < p.y && p.y - y > 1e-8) { //采用1e-8的精度判斷相等
return true;
}
}
return false;
}
};
- Line類：采用一般式Ax+By+C=0的形式存儲讀入的直線，聲明了兩個構造函數，第一個是由讀入的兩點計算一般式的三個參數，第二個則是直接給三個參數指派。
class Line {
public://使用一般式表示直線，避免使用double出現精度損失。
long long a;
long long b;
long long c;
Line(long long x1, long long y1, long long x2, long long y2) {
this->a = y2 - y1;
this->b = x1 - x2;
this->c = x2 * y1 - x1 * y2;
}
Line(long long a, long long b, long long c) {
this->a = a;
this->b = b;
this->c = c;
}
};
- Circle類：存儲讀入的圓，直接指派圓心坐标和半徑。
class Circle {
public:
long long x;
long long y;
long long r;
Circle(long long x, long long y, long long r) {
this->x = x;
this->y = y;
this->r = r;
}
- 存儲結構：
vector<Line> lines;
vector<Circle> circles;
set<Point> points; //使用set保證同一點不被重複計數
-
單元測試的設計：
1.對于重複交點的測試(即測試set功能是否保證消除重複)
2.邊界條件測試：
-直線平行
-直線相交
-直線與圓相離
-直線與圓相切
-直線與圓相交
-圓與圓相離(内含、外離)
-圓與圓相切(内切、外切)
-圓與圓相交(圓心在内or圓心在外)
通過測試截圖：
個人項目作業
四、性能分析
(VS上的性能分析工具隻顯示一個函數，而沒有下面各函數的具體細節，在群裡求助老師同學也沒有得到有效地解決，故隻能手動分析，若後續找到有效的解決方法，會将相應圖檔和分析補全。)
通過和其他同學的交流讨論以及自己思考，可以得出整體的性能大部分花費到了set集合的insert操作上面，這其中就包含了對于重複節點的判斷過程。在思考改進的方面考慮了換其他的資料結構如HashMap等，但是發現對于結點的出現次數并沒有記錄的必要，使用key-value對隻是浪費空間和時間，閱讀其他同學的部落格時看到unsorted_set這一結構，其内部不像sort一樣排序可以提高一些效率，我便去尋找了有關的一些資料，發現之是以set要重載小于運算符，正是因為要滿足其内部的排序需求，而對于重複元素的判斷則是進行一次小于判斷後交換兩元素的位置再進行一次小于判斷，結果均為false時就判定為兩者相等。而unsorted_set則是重載相等運算符，不需要受限于大小順序，進而在每一次判重過程都少了一次比較。
五、代碼說明
- 每兩個幾何對象聯立求交點：
for (int i = 0; i < (int)lines.size(); ++i) {//直線與直線相交
for (int j = i + 1; j < (int)lines.size(); ++j) {
lineIntersectLine(lines[i], lines[j]);
}
}
for (int i = 0; i < (int)lines.size(); ++i) {//直線與圓相交
for (int j = 0; j < (int)circles.size(); ++j) {
lineIntersectCircle(lines[i], circles[j]);
}
}
for (int i = 0; i < (int)circles.size(); ++i) {//圓與圓相交
for (int j = i + 1; j < (int)circles.size(); ++j) {
circleIntersectCircle(circles[i], circles[j]);
}
}
}
- 直線與直線聯立：直接将化簡得到的公式代入值
void lineIntersectLine(Line l1, Line l2) {
if (l1.b * l2.a != l1.a * l2.b) { //不平行才會相交
double x = (double)(l2.c * l1.b - l1.c * l2.b) / (double)(l1.a * l2.b - l1.b * l2.a);
double y = (double)(l2.c * l1.a - l1.c * l2.a) / (double)(l1.b * l2.a - l1.a * l2.b);
Point p(x, y);
points.insert(p);
}
}
- 直線與圓聯立：由直線解出y表示x，代入圓方程得y的一進制二次方程，由判别式判斷是否有交點并解出坐标；對于A為0時的直線，無法使用y表示x，直接将得到的y值代入圓得到x的一進制二次方程求解。
void lineIntersectCircle(Line l, Circle cir) {
if (l.a == 0) { //水準線，直接得到y，再代入圓
double y = -(double)l.c / (double)l.b; //将y值代入圓方程
long long a = l.b * l.b;
long long b = -2 * l.b * l.b * cir.x;
long long c = l.c * l.c + 2 * l.b * l.c * cir.y + (cir.x * cir.x + cir.y * cir.y - cir.r * cir.r) * l.b * l.b;
long long delta = b * b - 4 * a * c;
if (delta > 0) {
double x1 = (-b + sqrt(delta)) / (2l * a);
double x2 = (-b - sqrt(delta)) / (2l * a);
Point p1(x1, y);
Point p2(x2, y);
points.insert(p1);
points.insert(p2);
}
if (delta == 0) {
double x = (-b + sqrt(delta)) / (2l * a);
Point p(x, y);
points.insert(p);
}
}
else {//直線Ax+By+C=0中A不為零，可以将x用y表示代入圓方程。
long long a = l.a * l.a + l.b * l.b;
long long b = 2 * (l.b * l.c + l.a * l.b * cir.x - l.a * l.a * cir.y);
long long c = l.c * l.c + 2 * l.a * l.c * cir.x + (cir.x * cir.x + cir.y * cir.y - cir.r * cir.r) * l.a * l.a;
long long delta = b * b - 4 * a * c;
if (delta > 0) {
double y1 = (-b + sqrt(delta)) / (2l * a);
double y2 = (-b - sqrt(delta)) / (2l * a);
double x1 = (-l.b * y1 - l.c) / l.a;
double x2 = (-l.b * y2 - l.c) / l.a;
Point p1(x1, y1);
Point p2(x2, y2);
points.insert(p1);
points.insert(p2);
}
if (delta == 0) {
double y = (-b + sqrt(delta)) / (2l * a);
double x = (-l.b * y - l.c) / l.a;
Point p(x, y);
points.insert(p);
}
}
- 圓與圓聯立：兩圓方程相減得到過交點的直線方程，轉為直線與圓交點問題。
void circleIntersectCircle(Circle c1, Circle c2) {
if ((c1.x - c2.x) * (c1.x - c2.x) + (c1.y - c2.y) * (c1.y - c2.y) <= (c1.r + c2.r) * (c1.r + c2.r)//外切外交
|| (c1.x - c2.x) * (c1.x - c2.x) + (c1.y - c2.y) * (c1.y - c2.y) >= (c1.r - c2.r) * (c1.r - c2.r)) {//内切内交
long long a = 2 * (c1.x - c2.x);
long long b = 2 * (c1.y - c2.y);
long long c = c2.x * c2.x - c1.x * c1.x + c2.y * c2.y - c1.y * c1.y + c1.r * c1.r - c2.r * c2.r;
Line l(a, b, c);
lineIntersectCircle(l, c1);
}
}
六、Code Quality Analysis分析并消除所有的警告
