个人项目作业
| 项目 | 内容 |
|---|---|
| 这个作业属于哪个课程 | 课程链接 |
| 这个作业的要求在哪里 | 作业链接 |
| 教学班级 | 006 |
| 项目地址 | Github地址 |
PSP项目表格
| PSP2.1 | Personal Software Process Stages | 预估耗时（分钟） | 实际耗时（分钟） |
|---|---|---|---|
| Planning | 计划 | ||
| · Estimate | · 估计这个任务需要多少时间 | 10 | 10 |
| Development | 开发 | ||
| · Analysis | · 需求分析 (包括学习新技术) | 200 | 180 |
| · Design Spec | · 生成设计文档 | 60 | 90 |
| · Design Review | · 设计复审 (和同事审核设计文档) | 30 | 30 |
| · Coding Standard | · 代码规范 (为目前的开发制定合适的规范) | 20 | 30 |
| · Design | · 具体设计 | 100 | 120 |
| · Coding | · 具体编码 | 200 | 180 |
| · Code Review | · 代码复审 | 100 | 60 |
| · Test | · 测试（自我测试，修改代码，提交修改） | 150 | 150 |
| Reporting | 报告 | ||
| · Test Report | · 测试报告 | 30 | 20 |
| · Size Measurement | · 计算工作量 | 30 | 30 |
| · Postmortem & Process Improvement Plan | · 事后总结, 并提出过程改进计划 | 30 | 40 |
| 合计 | 960 | 930 |
解题思路描述
-
第一次读题想到的方法是直接求交点坐标，然后思考较多的是交点的求法和记录方法。
-
根据网络资料，直线交点的计算比较容易，可用 Ax+By+C=0 对A，B，C计算得到，且除法只需要一次，精度比较可靠。
-
但直线与圆、圆与圆的交点计算比较困难，既没有较短的求解公式，计算过程中又需要多次开方，可能达不到精度的要求。
-
最终决定：直线的交点直接求解。
-
直线与圆的交点、圆与圆的交点通过计算多个中间过程再求解。具体的，交点坐标符合形式
x = （A±B）/C， Y = （D±E）/C
其中B、E中某个因式的正负决定了解的个数，所以通过计算中间过程来求交点。
设计实现过程
-
设计三个类
- Point类：记录坐标点的两个坐标。
- Line类：使用标准式Ax+By+C=0，可以处理与坐标轴平行的特殊情况，通过两个点计算A，B，C即可。
- Ciecle类：使用（x-a0）^2^+（y-y0）^2^=r^2^，实现与Line、Circle求交点的方法。
-
流程
直线与圆各自有一个set容器存储，在识别出下一个图形后取出存储的每一个图形，调用图形的GetCross方法得到交点，再将交点加入另一个set容器。
-
单元测试
- 基本功能测试有类的构造是否正确、交点计算的方法测试。
- 边界测试包括边界点、边界范围的图形、大量数据使交点靠近、重合等场景。
- 单元测试覆盖率：
没有覆盖是命令行的输入部分，主要功能都被测试覆盖到了。
性能改进
这部分使用时间60min，因为出现“在所选时间范围内没有代码运行”的玄学问题，性能分析使用VS的instrumentation功能，性能分析图：
- 第一个性能瓶颈是set容器的速度，在大量数据插入时set树的构建会占用大量运行时间。优化方法是使用unordered_set代替set，图中是优化后的截图，可以看到主要瓶颈已经变成哈希函数的性能了。但是，哈希函数需要解决双浮点精度的问题。
- 第二是计算过程的性能问题，因为涉及到交点可能重合，暂未想到优化方法。
代码说明
整体的思路是用set容器作为存储结构，下图是新增一个圆的过程：
infile >> x0 >> y0 >> x1;
Circle circle(Point(x0, y0), x1);
for (Line temp : lineSet) {
circle.GetCrossToLine(temp);
}
for (Circle temp : circleSet)
{
circle.GetCrossToCircle(temp);
}
circleSet.insert(circle);
从Lineset和Circleset中分别取出图形，各自计算交点。
GetCross方法计算图形交点，下图是直线与直线求交点的方法，首先判断平行，可避免出现除以0的问题。
Point Line::GetCrossPoint(Line l1)
{
double D;
D = l1.a * this->b - this->a * l1.b;
if (!D)
{
throw exception();
}
Point pTemp(0, 0);
pTemp.pointX = (l1.b * this->c - this->b * l1.c) / D;
pTemp.pointY = (l1.c * this->a - this->c * l1.a) / D;
return pTemp;
}
计算圆与圆的交点的方法，计算过程较长，所以性能不好
int Circle::GetCrossToCircle(Circle c1)
{
double a1, b1, r1, a0, b0, r0;
a0 = center.pointX;
b0 = center.pointY;
r0 = r;
a1 = c1.center.pointX;
b1 = c1.center.pointY;
r1 = c1.r;
double a12 = a1 * a1, b12 = b1 * b1, r12 = r1 * r1, a02 = a0 * a0, b02 = b0 * b0, r02 = r0 * r0;
double delta = (-a02 + 2 * a0 * a1 - a12 - b02 + 2 * b0 * b1 - b12 + r02 + 2 * r0 * r1 + r12) *
(a02 - 2 * a0 * a1 + a12 + b02 - 2 * b0 * b1 + b12 - r02 + 2 * r0 * r1 - r12);
if (delta < 0)
{
return 0;
}
double delta_1 = a0 * b02 - a02 * a1 - a0 * a12 + a0 * b12 + a1 * b02 + a1 * b12 - a0 * r02 + a0 * r12 + a1 * r02 - a1 * r12 + a02 * a0 + a12 * a1 - 2 * a0 * b0 * b1 - 2 * a1 * b0 * b1;
double delta_2 = sqrt(delta);
double delta_3 = 2 * (a02 - 2 * a0 * a1 + a12 + b02 - 2 * b0 * b1 + b12);
double delta_4 = a02 * b0 + a02 * b1 + a12 * b0 + a12 * b1 - b0 * b12 - b02 * b1 - b0 * r02 + b0 * r12 + b1 * r02 - b1 * r12 + b0 * b02 + b1 * b12 - 2 * a0 * a1 * b0 - 2 * a0 * a1 * b1;
Point cross1((delta_1 - b0 * delta_2 + b1 * delta_2) / delta_3, (delta_4 + a0 * delta_2 - a1 * delta_2) / delta_3);
Point cross2((delta_1 + b0 * delta_2 - b1 * delta_2) / delta_3, (delta_4 - a0 * delta_2 + a1 * delta_2) / delta_3);
pointSet.insert(cross1);
pointSet.insert(cross2);
return 2;
}
Code Quality Analysis
解决项目的心路历程与收获
个人项目可以说是对前一次所学的软件工程方法的实践。在作业的过程中一个问题是需求分析和设计花了很长时间，因为想着优化计算方法所以一直在修改设计文档，结果时间大大超出了预期。另一个问题是实现功能时很多时间花在邹欣老师《构建之法》中说的低层次问题上，比如set容器用到的自定义类的运算符重载，只有通过不断的练习，把这些低层次的问题都变成不用经过大脑的自动操作，然后才有时间和脑力来解决较高层次的问题。另外这是第一次对自己的项目使用单元测试，所以项目的结构有些问题，和单元测试配合的不是很好，下次一定使用更好的设计模式。希望在以后的结对项目和团队项目里能克服这些问题。