BUAA 軟體工程個人作業

BUAA 軟體工程 個人項目作業

• Author: 17373015 喬玺華
• 教學班級 ：005
• 項目位址：https://github.com/JordenQiao/SE_Homework_Personal

項目	内容
這個作業屬于哪個課程	2020春季計算機學院軟體工程(羅傑 任健)
這個作業的要求在哪裡	個人項目作業
我在這個課程的目标是	學習軟體工程的開發知識，培養工程化開發能力
這個作業在哪個具體方面幫助我實作目标	通過實操掌握PSP開發基礎

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

一. 解題思路描述

上網搜尋

嘗試在網絡上找到複雜度低于o(n^2)的算法，找到一個涉及線段與線段交點的o(nlogn)，關于直線搜尋無果

解題思路

寫代碼前，并未找到優秀的算法，于是選擇暴力求解，即讀入一條直線，立即與前n條直線進行相交求解，每一個求解得到的點都需要進行去重處理，即便理vector尋找相同點，複雜度極高。

改進

将點的橫縱坐标組成string，形成key，選取哈希存儲，即橫縱坐标成為哈希清單的key值，value值為點這個結構體，這是寫代碼前的想法

二. 設計實作過程

由于是較為簡單的C++代碼，并沒有刻意使用面向對象的思路

• class: Function（即整個程式本體，為友善進行Test時，直接調用接口
  • set<Node, cmp> nodes：寫代碼時使用set而不是hashmap，是由于hashmap的開銷遠大于set，需要多出一個double轉string的過程，可能存在精度損失，開銷亦極大
  • void getLinePara: 使用ax + b = cy的方式代表直線，而不是使用最初的y = kx + b是為了減少除法的使用，最大限度保留資料的精度和準确性，讀入直線時，調用此函數，擷取a b c的數值，存入直線的結構體種
  • void readFile: 使用本函數進行檔案讀入，并将所有的Line存入vector<Line>Lines中
  • bool L2LIsCross: 使用本函數求解直線與直線的交點，即解二進制一次方程組，求解前會先判斷直線是否存在交點，求解得到焦點後立刻存入nodes中，并傳回true，否則不存在交點，傳回false
  • bool C2LIsCross: 使用本函數求解圓與直線的交點，根據圓心以及給出直線的垂線斜率，得到過圓心關于給出直線的垂線，後求出兩直線的交點，根據交點到圓心的距離，判斷相交相切相離，若相離，則傳回false；否則，得到給出直線的正負機關向量，分别乘以與圓交線段的一半，計即可得到兩個交點的坐标，傳回true
  • bool C2LIsCross: 使用本函數求解兩個圓的交點，首先利用圓的方程相減，得到過焦點的直線的方程，簡化為求直線與圓的交點問題，直接調用函數即可
  • int Solve: 調用上述函數，完成讀入到求出交點個數的過程，友善test接口使用
• pair: Node(存放點的typedef，并未使用結構體，而是用了pair)
• struct: Line (存放直線的結構體，包括兩個點的橫縱坐标，使用long存儲，以及ax + b = cy中的a, b, c)
• struct: Circle(存放圓的結構體，包括圓心node以及半徑r)

小tricks：

• 使用set<pair>，無需double轉string，減少大量工作量
• 重寫set中pair的比較函數，保證精度達到小數點後12位

單元測試

• 考慮極端情況，直線平行，直線垂直，直線與圓相交，直線與圓相切，直線與圓相離，圓與圓相交，圓與圓内含，圓與圓相切
• 壓力測試，2000條直線，進行測試

三. 性能測試

根據總CPU時間配置設定，可以看出主要占用時間的函數

可以看出set.insert函數，消耗最大，也可以了解，而第一版代碼中使用的hashmap，由于需要double轉string，其消耗極大，甚至超過了向hashmap中插入的消耗，是以改進為使用set，紅黑樹存儲，既可以保證不出現重複，又可以減少不必要的消耗，而向set中插入pair的方法，我并沒有太多的好辦法進行優化。

四. 代碼說明

代碼品質分析圖

關鍵函數實作

• 圓與直線交點求解

  

• 圓與圓交點求解

  

• 直線與直線交點求解