软工个人项目:平面直线交点

项目 内容
这个作业属于哪个课程 计算机学院软件工程
这个作业的要求在哪里 个人项目作业
教学班级 005
GitHub链接 个人仓库地址

PSP2.1表格

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

解题思路

一开始考虑的是存放线和点的数据结构。

如何表达一根线?一开始想的是用 y = k*x + b 的形式表达直线,有两个量。然后发现这种形式无法表达和x轴垂直斜率无限大的直线,改用 A * x + B * y + C = 0 的标准形式。

存放的数据结构,一开始想的是给线和点各创一个类,用map存储线;由于map需要不冲突的key值,而无论是A、B、C都有可能两条不同直线有相同的key值。于是思考自定义key值类型,由于map的数据结构是一棵有序红黑树,key值无法重复,判断重复用到了自带comparator。因此要重载自定义key值的operator<()操作符,否则会出现错误。(其他解决办法:比较函数的函数对象:利用std::function、重载operator的类、less函数的模板定制)

在表示点与直线的时候新建了类,并把类写进头文件

考虑了数据结构,思考如何通过输入的点坐标形成线,如何通过两根线得到一个交点

纸笔推导公式:

  • 两个点形成直线:

(x1 , y1),(x2, y 2);

A = y2 - y1;

B = x1 - x2;

C = x2 * y1 - x1 * y2;

  • 两根线成交点:

a1 * x + b1 * y + c1 = 0;

a2 * x + b2 * y + c2 = 0;

x = (b1 * c2 - b2 * c1) / (a1 * b2 - a2 * b1);

y = (a2 * c1 - a1 * c2) / (a1 * b2 - a2 * b1);

具体设计(合并代码说明)

在实际编码的过程中意识到数据结构设计的问题。由于key值已经存储了直线所有的信息,因此key-value对的map形式显然已经有些冗余,将map改成只有key且key为value的set数据结构

点的类里面包括了operator<()操作符重载,方便set内存放不报错。

头文件包含了默认内联构造方法:

class Dot {
    public:
        float x;
        float y;
        Dot(float a, float b) {
            x = a;
            y = b;
        }
        bool operator<(const Dot& p)const {
            return (x < p.x) || (x == p.x && y < p.y);
        }
    };

线的类内

包括了operator<()操作符重载,方便set内存放不报错。

包含了parallel方法,返回是否平行

包含了intersect方法,返回了与其他Line对象交点的Dot对象

头文件内:

class Line {
    public:
        int A;
        int B;
        int C;
        Line(int x1, int y1, int x2, int y2);
        bool operator<(const Line& p)const {
            return (A < p.A) || 
                (A == p.A && B < p.A) || 
                (A == p.A && B == p.B && C < p.C);
        }
        bool parallel(Line l);
        Dot intersect(Line l);
    };

实现细节:

构造方法:

Line::Line(int x1, int y1, int x2, int y2) {
    A = y2 - y1;
    B = x1 - x2;
    C = x2 * y1 - x1 * y2;
}

判断重合或者平行的函数(没有交点):

bool Line::parallel(Line l) {
    if ((Line::A * l.B - l.A * Line::B) == 0)
    {
        return true;
    }
    return false;
}

得到交点的函数:

Dot Line::intersect(Line l) {
    float a1 = float(Line::A);
    float b1 = float(Line::B);
    float c1 = float(Line::C);
    float a2 = float(l.A);
    float b2 = float(l.B);
    float c2 = float(l.C);
    float x = (b1 * c2 - b2 * c1) / (a1 * b2 - a2 * b1);
    float y = (a2 * c1 - a1 * c2) / (a1 * b2 - a2 * b1);
    return Dot(x,y);
}

尽管Class Line 实现了操作符重载,但不知道是因为重载写法有问题还是其他因素

        bool operator<(const Line& p)const {
            return (A < p.A) || 
                (A == p.A && B < p.A) || 
                (A == p.A && B == p.B && C < p.C);
        }

测试的时候发现某些数据在debug模式下运行会造成崩溃报错

release模式下运行不会报错

本地可重现的样例:

循环体内输入部分如下:

        cin >> a >> b >> c >> d;
        Line l(a, b, c, d);
        for (auto it : lineSet) {
            if (it.parallel(l)) {
                continue;
            }
            else {
                Dot dot = it.intersect(l);
                dotSet.insert(dot);
            }
        }
        //cout <<l.A<<" ** "<<l.B<<" ** " << l.C<<endl;
        lineSet.insert(l);

输入L 0 0 1 1,

LineSet(原用于存放Lines的set结构,set lineSet)加入一个对象Line line1 ,

line1.A= 1,line1.B = -1 ,line1.C = 0 ;LineSet.size() = 1;

输入L 0 0 0 1,

LineSet 加入一个对象Line line2,

line1.A= 1,line1.B = 0 ,line1.C =0 ;LineSet报错 invalid comparator;

此时line1<line2为true line2<line1为false。无法找到less函数报错的原因;

故将Line类的保存数据结构换成vector容器,且任何形式下都不使用其自带sort!!

修改部分:

vector<Line> lineVector;
        for (auto it : lineVector) {
            if (it.parallel(l)) {
                continue;
            }
            else {
                Dot dot = it.intersect(l);
                dotSet.insert(dot);
            }
        }
        //cout <<l.A<<" ** "<<l.B<<" ** " << l.C<<endl;
        lineVector.push_back(l);

单元测试:

随机数生成两条直线得到交点坐标

#define random(x) rand()%(2*x)-x
Line randomLine(int x) {
    return Line(random(x), random(x), random(x), random(x));
}
int main() {
    srand((int)time(0));
    int n;
    cin >> n ;
    Line l1 = randomLine(n);
    Line l2 = randomLine(n);
        cout << l1.A << " " << l1.B << " " << l1.C << endl;
        cout << l2.A << " " << l2.B << " " << l2.C << endl;
    if (l1.parallel(l2)) {
    
    }
    else {
        Dot dot = l1.intersect(l2);
        cout << "x = "<<dot.x << "y = " << dot.y << endl;
    }

    
    return 0;
}

通过geogebra验证交点正确性

性能分析:

Code Quality Analysis
软工个人项目:平面直线交点

其余性能分析:未完成

上一篇:TypeScript type 类型别名


下一篇:第三章、简单的算术运算和表达式