軟工

個人項目作業

項目	内容
這個作業屬于哪個課程	2020春季計算機學院軟體工程(羅傑 任健)
這個作業的要求在哪裡
我在這個課程的目标是	學習工程化開發軟體,體驗團隊開發和結隊開發
這個作業在哪個具體方面幫助我實作目标	通過個人項目作業體會PSP
教學班級	006
項目位址	https://github.com/themaker123/intersect

PSP表

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

解題思路:

• 分别求直線與直線的交點,直線與圓的交點,圓與圓的交點,然後每求出一個交點之後就将其加入到一個集合set中,保證不會重複,這樣這個集合的大小就是所求的結果.
• 對于直線的交點采用公式:

  x = (b1*c2-b2*c1)/(a1*b2-a2*b1),y = (a2*c1-a1*c2)/(a1*b2-a2*b1)

• 對于直線與圓的交點,首先将直線分為斜率不存在和斜率存在的兩種情況,然後聯立直線方程與圓的方程,就得到坐标,同時根據判别式也可以從中得到坐标的數量.
• 對于圓與圓的交點,兩個圓的方程相減,得到一個直線方程,然後求這個直線與圓的交點坐标即可

設計實作過程(含代碼分析):

• 總體考慮到項目本身的功能非常單一,實作也相對來說比較簡單,是以整體隻有兩個檔案

  main.cpp

  和頭檔案

  global.h

  ,函數主要有計算直線交點的函數

  calaIntersectLineOnly

  ,計算直線和圓交點的函數

  calaIntersectLineCircle

  ,計算圓與圓交點的函數

  calaIntersectCircleOnly

  ,同時三個累計求所有交點的函數,包括

  lineOnly(), lineAndCircle(), circleOnly();

  ,資料結構有

  Line,dot

  等
• 對于直線,首先使用

  trans

  函數将兩個坐标轉換為直線的一般表達式即

  y = a*x+b*y+c

  void trans(line &l,int x1,int y1,int x2,int y2) {
  	int a, b, c;
  	a = y1 - y2;
  	b = x2 - x1;
  	c = x1 * y2 - x2 * y1;
  	l.a = a;
  	l.b = b;
  	l.c = c;
  }
             

• 資料結構
  • 直線(一般表達式),由于圓的表達也是三個參數與直線高度重合,是以為了友善我們采取同樣的資料結構來表示圓形.

    struct line {
    	double a;
    	double b;
    	double c;
    };
               

  • 交點:

    class dot {
    public:
    	double x;
    	double y;
    	
    	bool operator < (const dot& d)const
    	{
    		if (fabs(d.x - x) < 1e-7 && fabs(d.y - y) < 1e-7) return false;
    		else {
    			if (d.x > x) return true;
    			else if (d.x == x) {
    				if (d.y < y) return true;
    				else return false;
    			}
    			else return false;
    		}
    		
    	}
    };
               

• 對于求兩個直線的交點,首先判斷兩個直線是否平行,如果平行則直接退出,否則根據公式求直線的交點,

  int calaIntersectLineOnly(line l0,line l1){
  	double x, y, k;
  	dot d;
  	k = l0.a * l1.b - l0.b * l1.a;//如果k==0則兩直線平行
  	if (k == 0) return -1;//平行沒有交點
  	d.x =  (l0.b * l1.c - l0.c * l1.b) / k;
  	d.y =  (l1.a * l0.c - l1.c * l0.a) / k;
  	dots.insert(d);
  	return 0;
  }
             

• 對于直線與圓的交點,我們首先設法将直線的一般方程轉換為斜率式

  y=k*x+b

  ,當然對于斜率不存在的情況,我們需要特殊考慮.然後将直線方程與圓的方程進行聯立,得到一個一進制二次方程,根據判别式

  b^2-4ac

  的符号判斷交點的數量,如果小于0則沒有交點,等于0一個交點,大于零兩個交點

  int calaIntersectLineCircle(line l, line circle) {
  	double  a = 0, c = 0, r = 0 ;
  	dot d1, d2;
  	a = circle.a;
  	c = circle.b;
  	r = circle.c;
  	//如果斜率不存在
  	if (l.b == 0) {
  		double t;
  		t= -1 * l.c / l.a;
  		double delt;
  		delt = r * r - a * a - (l.c * l.c + 2 * l.c * a * l.a) / (l.a * l.a);
  		if (delt < 0) return -1;
  		double t1;
  		t1= sqrt(delt);
  		d1.x = t;
  		d1.y = c + t1;
  		d2.x = t;
  		d2.y = c - t1;
  		dots.insert(d1);
  		dots.insert(d2);
  	}
  	else {
  		double b_2 = l.b * l.b;
  		double a2 = b_2+l.a*l.a;
  		double b2 = -2*b_2*a + 2 * l.a * (l.c + l.b * c);
  		double c2 = a*a*b_2 + (l.c + l.b * c) * (l.c + l.b * c) - r*r*b_2;
  		double delt2;
  		delt2 = b2 * b2 - 4 * a2 * c2;
  		if (delt2 < 0) return -1;
  		double delt;
  		delt = sqrt(delt2);
  		d1.x = (-1 * b2 + delt) / (2 * a2);
  		d2.x = (-1 * b2 - delt) / (2 * a2);
  		d1.y = (-l.a*d1.x-l.c)/l.b;
  		d2.y = (-l.a * d2.x - l.c) / l.b;
  		dots.insert(d1);
  		dots.insert(d2);
  	}
  	return 0;
  }
             

• 對于圓與圓的交點,整體思路是求圓方程相減後的直線方程,然後這個直線與圓的交點即是兩個圓的交點,通過這個轉化,我們就不用再額外的計算圓與圓的交點,隻需要利用直線與圓的交點的函數即可

  int calaIntersectCircleOnly(line c1, line c2) {
  	double a1 = c1.a, b1 = c1.b, r1 = c1.c;
  	double a2 = c2.a, b2 = c2.b, r2 = c2.c;
  	double a, b, c;
  	a = 2 * (a2 - a1);
  	b = 2 * (b2 - b1);
  	c = a1 * a1 + b1 * b1 - a2 * a2 - b2 * b2 + r2 * r2 - r1 * r1;
  	//得到兩圓的交線的方程;
  	line l;
  	l.a = a;
  	l.b = b;
  	l.c = c;
  	if (a == 0 && b == 0) return -1;
  	//if ((a1 - a2) * (a1 - a2) + (b1 - b2) * (b1 - b2) - (r1-r2)*(r1-r2) < 0) return -1;
  	calaIntersectLineCircle(l,c1);
  	return 0;
  }
             

• 然後分别求直線與直線的交點,直線與圓的交點,圓與圓的交點,

  lineOnly();
  lineAndCircle();
  circleOnly();
             

• 本工程的核心是三個函數: 計算直線與直線交點函數, 計算直線與圓交點函數, 計算圓與圓交點函數, 是以單元測試的核心是以這三個函數為基礎,分别測試隻有直線的情況, 隻有圓的情況, 直線與圓的情況.

  

改程序式性能:

從圖中可以看出

calaIntersectLineCircle

函數占用的時間最多,而這個函數主要是用來計算直線與圓形的交點,

是以,而對這個函數主要進行了以下優化,判斷交點的個數減少向set中加入新的dot的次數,因為在這個函數中,set,insert操作又占有相當大的時間.

代碼風格檢查: