个人项目作业

一、信息

项目	内容
这个作业属于哪个课程	2020春季计算机学院软件工程(罗杰任健) (北京航空航天大学 - 计算机学院)
这个作业的要求在哪里	个人项目作业
我的教学班级	周三上午三四
这个项目的GitHub地址	https://github.com/lucieningit/intersection

二、PSP


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

三、设计思路

首先应该对输入进行处理。对于直线，考虑到有各种的直线，采用一般式来表示直线，利用两个点可以表示出一般式。两个直线的交点同样可以用数学推导求出，用一般式中的系数表示。那么这个程序有两个主要过程。第一，转换输入，得到可用的数据，即图形的存储。第二，是求解交点，这些可以用初中的知识解决。

输入信息处理
- 直线：由两点(x1, y1)、(x2, y2)，一般式ax+by+c=0
  - a: y1-y2
  - b: x2-x1
  - c: x1y2-x2y1。
交点求解
- 直线与直线：ax+by+c=0，px+qy+r=0
  - x: (br - cq)/(aq - bp)
  - y: (-ar + cp)/(aq - bp)

四、设计实现

数据结构
- 图形
  
  需要三个参数和一个类型
```
struct Graph
{
    char type;
    int a;
    int b;
    int c;
};
```
  - 直线：ax+by+c=0
- 全部图形
  
  所设计算法为两两比较，因此存储所有图形，利用vector节省空间
  
  vector<Graph> graphs;
- 全部交点
  
  交点不能重复，因此选择map和set的结构
  
  map<double, set<double>> points
函数

用到的函数关系如下图所示

main主要用于输入转换和判断，交点函数用来求解交点

五、性能分析

如下图所示

上图为1000直线交点测试，其中求交点的函数占大多资源，底层为set和tree的函数。

六、代码说明

主要有两个过程

输入转换

利用两点求出参数

for (i = 0; i < gn; i++) {
        Graph graph{};
        cin >> graph.type;
        //将输入转化为可用数据
        if (graph.type == 'L') {
            cin >> x1;
            cin >> y1;
            cin >> x2;
            cin >> y2;
            graph.a = y1 - y2;
            graph.b = x2 - x1;
            graph.c = x1 * y2 - x2 * y1;
        }
        for (j = 0; j < graphs.size(); j++) {
            //判断是否有交点
            if (graph.type == 'L' && graphs.at(j).type == 'L') {
                if (graph.a*graphs.at(j).b != graphs.at(j).a*graph.b) {
                    //调用交点函数
                    line_line(graph, graphs.at(j));
                }
            }   
        }
        graphs.push_back(graph);
    }

求交点

利用推导公式求交点，并在set中查重、存储

void line_line(Graph &g, Graph &f) 
{
    //根据公式求交点
    const double x = (g.b*f.c - g.c*f.b) / (g.a*f.b - g.b*f.a);
    const double y = (g.c*f.a - g.a*f.c) / (g.a*f.b - g.b*f.a);
    
    //查重、存储
    if (points.find(x) != points.end()) {
        set<double> ys = points.at(x);
        if (ys.find(y) == ys.end()) {
            pn++;
            ys.insert(y);
        }
    } else {
        pn++;
        set<double> ys;
        ys.insert(y);
        points.insert(Mypoints::value_type(x, ys));
    }
}c

七、其他

错误与警告

unit