软件工程个人项目作业
| 项目 | 内容 |
|---|---|
| 这个作业属于哪个课程 | 2020计算机学院软件工程(罗杰 任健) |
| 这个作业的要求在哪里 | 个人项目作业 |
| 教学班级 | 006 |
| 项目地址 |
一.PSP表格
| PSP2.1 | Personal Software Process Stages | 预估耗时（分钟） | 实际耗时（分钟） |
|---|---|---|---|
| Planning | 计划 | 15 | |
| · Estimate | · 估计这个任务需要多少时间 | ||
| Development | 开发 | ||
| · Analysis | · 需求分析 (包括学习新技术) | 30 | 90 |
| · Design Spec | · 生成设计文档 | 25 | |
| · Design Review | · 设计复审 (和同事审核设计文档) | 10 | 20 |
| · Coding Standard | · 代码规范 (为目前的开发制定合适的规范) | ||
| · Design | · 具体设计 | 40 | |
| · Coding | · 具体编码 | 150 | |
| · Code Review | · 代码复审 | ||
| · Test | · 测试（自我测试，修改代码，提交修改） | 45 | 120 |
| Reporting | 报告 | ||
| · Test Report | · 测试报告 | ||
| · Size Measurement | · 计算工作量 | ||
| · Postmortem & Process Improvement Plan | · 事后总结, 并提出过程改进计划 | ||
| 合计 | 320 | 585 |
二.思路描述
- 求解思路：检测已有交点集合有多少个点在新的直线上，如果至少有两个，说明是与已有的直线共线，跳过；如果个或者零个，那么就与已有的直线求交点，注意求出的交点至多为x-1个，x是该直线的标号，注意如果求出的交点重复，则该交点不加入交点集合。
- 另一种想法：构造交点集合S,这里使用一个map来表示<pair<x,y>,count>,count=1表示该点已经存在。对新加入的直线与之前的所有直线求交点，如果该交点在S中，则跳过；否则加入交点集合中。最后集合的大小就是答案。加入圆类型后类似。本次作业采用第二种思路实现。
-
基本知识参考：
直线的一般式及交点求解
圆与直线的交点
圆之间的交点
圆标准方程的交点求法
三.设计实现过程
- 总体结构：
- 一个main函数，用于读取输入，维护图形容器和交点容器。每次读到一个图形就与其它图形判断几何关系后再决定是否要求交点，调用相应类的相应方法即可。
- 一个头文件：line.h，头文件中分别定义直线类和圆类，用于保存相关的几何信息、以及定义了一些方法来计算交点，判断几何性质等等。
- 两个类：
- 直线类Line：
2020软工个人项目作业 - 圆类Circle：
2020软工个人项目作业
- 直线类Line：
- 单元测试的设计：
- 重点在于测试基础作业的直线与直线交点的测试。分别测试：两直线平行和相交的各种情况，同时测试直线解析式，测试交点坐标等等。结果均符合预期。
四.改进程序性能的过程
总共花费时间：60分钟。
- 改进1：一开始我是对所有的图形进行交点求解，全部放入一个集合S中，求完之后再对集合去重。这样的好处是逻辑明了，分工明确，但是缺点是时间代价太大。之后进行了改进：边计算交点，边检查交点是否重复，若不重复则再添加至集合S中，这样的时间开销会小一些。
- 改进2：在求出交点的时候，我最初使用map.count来查找交点是否在map中，效率极低，后来将之删除后直接使用insert，效率有所提高。
- 改进3(存疑)：考虑使用set来替代map，以达到减少insert的开销。在性能测试中做了简单的横向对比，选择了set。最后再次考虑到set的排序，后又采用了unordered_map.
-
性能分析：
一.给出了几组测试数据跑出来所需要的时间。
1.1000条直线，随机生成数据。使用map存储交点。交点数大概为49W。
2.和第一组数据一致。使用set存储交点。 2020软工个人项目作业 3.2000条直线，随机生成数据。使用map存储交点。交点数大概为190W。 2020软工个人项目作业 4.和3中的数据一致。使用set存储交点。 2020软工个人项目作业 2020软工个人项目作业 可以发现，使用set有一定的时间改善。但不排除偶然因素。
二.对第二组数据进行分析
可以看出关于set的操作开销占比较大。
进入具体代码分析，发现的确是set的插入占了很大的开销。pointss是set<pair<double,double>>，用于存储交点。
五.代码说明。
1.求两直线的交点：在调用该函数的时候先将判断两条直线不平行。
2.求圆和直线的交点：
3.求圆之间的交点：首先要判断圆之间的位置，如果不是内含或者相离，则将之转化为求与直线的交点问题。这里的直线是指将两个圆的标准方程相减得到的解析式，即两圆的交点直线。
六.源代码管理部分要求截图
1.单元测试
2.消除Code Quality Analysis的warning
一点说明：代码截图中有部分数据类型是long long以及采用的存储交点的数据结构是set，在GitHub项目中是表示为double以及存储交点的数据类型是Unordered_set。