个人项目作业

个人项目作业

前言

项目	内容
这个作业属于哪个课程	北航2020春软工
这个作业的要求在哪里	个人项目作业
我在这个课程的目标是	学习并实践软件开发，提高团队合作的能力
这个作业在哪个具体方面帮助我实现目标	个人开发实践
我的教学班级	005
项目地址	https://github.com/zhyixuan/intersect

---

PSP表格

PSP2.1	Personal Software Process Stages	预估耗时（分钟）	实际耗时（分钟）
Planning	计划
· Estimate	· 估计这个任务需要多少时间	10	10
Development	开发
· Analysis	· 需求分析 (包括学习新技术)	180	240
· Design Spec	· 生成设计文档	30	30
· Design Review	· 设计复审 (和同事审核设计文档)	20	10
· Coding Standard	· 代码规范 (为目前的开发制定合适的规范)	10	0
· Design	· 具体设计	40	30
· Coding	· 具体编码	120	150
· Code Review	· 代码复审	20	30
· Test	· 测试（自我测试，修改代码，提交修改）	120	20
Reporting	报告
· Test Report	· 测试报告	30	20
· Size Measurement	· 计算工作量	10	10
· Postmortem & Process Improvement Plan	· 事后总结, 并提出过程改进计划	30	10
	合计	620	560

问题：测试与改进工作没有完全完成，对C++不熟悉，学习新技术占了一定的时间。

---

解题思路描述

• 没有想到其他办法，所以采用了暴力求解。复杂度O(N²)。

  • 题目保证有限个交点，因此不会出现两直线重合
  • 平行线间无交点。不平行的两条直线必定相交于一点

• 如何描述直线

  一般式都可以表达，所以选择了一般式

  • 根据给定的两点求直线

    先写成两点式：

    $frac{y - y_2}{y_1- y_2} = frac{x - x_2}{x_1- x_2} $。

    再化成一般式 $(y_1 - y_2)x + (x_2 -x_1)y + (x_1y_2 -x_2y_1) = 0$

    所以
    $$
    A = y_1 - y_2,B = x_2 -x_1,C =x_1y_2 -x_2y_1
    $$

• 交点坐标公式

  首先判断是否平行，平行则无交点

  • 平行的条件$A2B1-A1B2 =0$

  • 交点坐标
    $$
    x=frac{C1B2-C2B1}{A1B2-A2B1},y =frac{C1A2-C2A1}{A2B1-A1B2}
    $$

• 如何保证精度

  • 使用double存储，当两个浮点数之差小于1e_15时，认为相等。

设计实现过程。设计包括代码如何组织，比如会有几个类，几个函数，他们之间关系如何，关键函数是否需要画出流程图？单元测试是怎么设计的？

• 类

  • 点类
    • x，y坐标
    • 两点重合：x,y分别相等（浮点数的相等）
  • 直线类 A、B、C三个参数

• 函数及其之间的关系

  • 主函数

    • 数据结构：vector来存储直线。因为要求交点的个数，所以采用unordered_set来存储交点。便于去重。

    • 流程。比较简单，不再画出流程图，下面简述流程。

      首先读取命令行参数，打开输入文件依次读取每一条直线并求解直线的A、B、C参数，将直线放入容器Vector中。

      遍历每两条直线，如果二者不平行，则计算两者交点，并加入set中。

  • 求直线交点
    遍历所有直线，求交点。将交点放入set中。当两条直线已经不再比较的时候，放入

  • 重载unordered_set的相等方法，以判断两个交点是否为同一个。

代码说明。展示出项目关键代码，并解释思路与注释说明。

关键代码：

Point类

class Point//一个点有x,y两个坐标值
{
public:
	Point();
	Point(double x0, double y0);
	double x;
	double y;
};

直线类

class Line//直线的一般式为Ax+By+C=0.因此确定一条直线需要以下参数
{
public:
	Line(long long x1, long long y1, long long  x2, long long y2);
	long long A;
	long long B;
	long long C;

};

求直线的三个参数

//根据数学公式直接得出
A = y1 - y2;
B = x2 - x1;
C = x1 * y2 - x2 * y1;

计算两直线的交点

//根据数学公式直接得出
x = (c1 * b2 - c2 * b1) / (a2 * b1 - a1 * b2);
y = (c1 * a2 - c2 * a1) / (a1 * b2 - a2 * b1);

判断坐标点相等

const double EPS = 1e-15;
bool double_equal(double a, double b) {
	if (fabs(a - b) < EPS) {
		return true;
	}
	return false;
}

思路说明

​ 一条直线（一般式）应该具有3个参数(A,B,C)，平面坐标系上的坐标点应该有两个参数(x,y)。因此先构造两个类用于存储直线和点。

​ 使用vector保存多条直线。在主函数中，每读取到一条直线，就按照上面的方法计算出其参数A、B、C，并将这条直线放入vector数组中。

​ 在读取完所有的直线后，遍历每两条直线，当二者不平行时，用上述代码求解交点，并将求出的交点放入存储交点的一个unorder_set的集合中。（开始用的set，但是发现自己写的重载operator不太对，所以换成了用unorder_set）

​ 最后将存储交点的集合的大小输出到output.txt即可。

​