软工个人项目

一、PSP估算

在开始实现程序之前，在下述 PSP 表格记录下你估计将在程序的各个模块的开发上耗费的时间。（0.5’）

在你实现完程序之后，在下述 PSP 表格记录下你在程序的各个模块上实际花费的时间。（0.5’）

在任务完成后回顾这个表格，我发现我做得还算不错，总体时间小于预估，但是debug的时间较长，这也是测试花费大量时间的原因。

二、思路及设计

在拿到题目之后，我很快定位出这是一道代数几何题，我们需要用自己学过的平面图形的相关知识来求解问题，这个问题分为3部分：直线和直线的交点，圆和圆的交点以及圆和直线的交点。

因此，我先是在纸上进行了演算，直线和直线的交点很好推理，圆和圆的可以转换圆和直线的交点，那么我们求解的关键就是圆和直线的交点，因此我查阅了求解这个问题的相关资料，找到了解决办法。

设计实现过程

这部分完成的比较轻松，因为有面向对象的基本知识，所以在这到题中，我自然的设计了两个类，圆和直线。

上图是直线类的定义，我们可以看出，其中包含了确定直线的两个点的坐标，以及一个用来求解直线和直线交点的函数。

上图是圆类的定义，其中包含圆的中心点和半径，此外，还有计算垂足，计算直线到圆的距离以及求解圆和直线交点以及圆和圆交点的函数，单元测试中我主要测试了各种类型的直线之间交点的例子。

改进程序性能

这个过程经历了两个阶段：

1. 使用set存放pair作为数据结构，利用set的不重复性来求解。

2. 使用vector存放pair作为数据结构，最后对vector进行去重。
   

上面两张图是我们阶段1分别用随机生成的1000条直线（约50w交点）和3000条直线（约450w交点）测试cpu的截图，从中我们可以看出，随着交点个数以近$n^2$的比例增长，时间也大幅度的增长。

上图是3000条指令是对应的时间消耗占比，我们可看出，对set的操作花费了大量的时间。以下是其中消耗时间最长的函数：

bool line::intersect(line line2, set<pair<double, double>>& intersections)
{
    double x3 = line2.x1;
    double x4 = line2.x2;
    double y3 = line2.y1;
    double y4 = line2.y2;
    double Determinant = (y1 - y2) * (x3 - x4) - (y3 - y4) * (x1 - x2);
    if (fabs(Determinant) < 1e-6) return false;
    double intersect_x = (-(x1 - x2) * (y3 * x4 - x3 * y4) + (x3 - x4) * (y1 * x2 - x1 * y2)) / Determinant;
    double intersect_y = (-(y1 - y2) * (y3 * x4 - x3 * y4) + (y3 - y4) * (y1 * x2 - x1 * y2)) / Determinant;
    intersections.insert(make_pair(intersect_x, intersect_y));
    return true;
}

第二个阶段我们改用vector之后，用相同3000条数据测试的效果图见上图，从中可以看出，我们的cpu时间不仅获得了仅10s的缩减，瓶颈部分也发生了转变。

项目关键代码

求解直线和直线交点

bool line::intersect(line line2, vector<pair<double, double>>& intersections)
{
    double x3 = line2.x1;
    double x4 = line2.x2;
    double y3 = line2.y1;
    double y4 = line2.y2;
    double Determinant = (y1 - y2) * (x3 - x4) - (y3 - y4) * (x1 - x2);
    if (fabs(Determinant) < 1e-6) return false;
    double intersect_x = (-(x1 - x2) * (y3 * x4 - x3 * y4) + (x3 - x4) * (y1 * x2 - x1 * y2)) / Determinant;
    double intersect_y = (-(y1 - y2) * (y3 * x4 - x3 * y4) + (y3 - y4) * (y1 * x2 - x1 * y2)) / Determinant;
    intersections.push_back(make_pair(intersect_x, intersect_y));
    return true;
}

这个函数就是我们上一小节中改进后的瓶颈函数，但也是我们程序中最核心的部分。我先是在纸上对两个点确立的直线方程进行了推导，其实就是将两个形如$y = kx + b$的方程联立，直接得到上述代码中的结果。

求解圆和直线的交点

int circle::intersectLine(line line1, vector<pair<double, double>>& intersections)
{
    double distance = getDistance(line1);
    if (distance > r)
    {
        //cout << "???" << endl;
        return 0;
    }
    pair<double, double> foot = getFoot(line1);
    if (distance == r)
    {
        intersections.push_back(foot);
        return 1;
    }
    double length = sqrt(r*r - distance*distance);
    if (line1.x1 == line1.x2)
    {
        intersections.push_back(make_pair(foot.first, foot.second + length));
        intersections.push_back(make_pair(foot.first, foot.second - length));
    }
    else
    {
        double cof = (line1.y1 - line1.y2) / (line1.x1 - line1.x2);
        double x = 1 / sqrt(cof * cof + 1);
        double y = cof / sqrt(cof * cof + 1);
        intersections.push_back(make_pair(foot.first + x * length, foot.second + y * length));
        intersections.push_back(make_pair(foot.first - x * length, foot.second - y * length));
    }
    return 2;
}

可以看出，我们先是进行了直线和圆心距离的计算，然后根据计算的结果决定两者之间的关系。其中对一种较为特殊的情况进行了讨论，即直线与y轴平行，这种情况下直线的斜率不存在，无法根据斜率进行计算。

圆与圆求交点

int circle::intersectCircle(circle circle2, vector<pair<double, double>>& intersections)
{
    double distance = sqrt(circle2.r * circle2.r - r * r);
    if (distance > (r + circle2.r) || distance < fabs(r - circle2.r)) return 0;
    double right = circle2.r * circle2.r - r * r + c1 * c1 - circle2.c1 * circle2.c1 
        + c2 * c2 - circle2.c2 * circle2.c2;
    if (circle2.c1 == c1)
    {
        double y = -right / (2 * circle2.c2 - 2 * c2);
        line line1 = line(1, y, -1, y);
        return intersectLine(line1, intersections);
    }
    else if(circle2.c2 == c2)
    {
        double x = -right / (2 * circle2.c1 - 2 * c1);
        line line1 = line(x, 1, x, -1);
        return intersectLine(line1, intersections);
    }
    else
    {
        line line1 = line(0, -right/(2 * circle2.c2 - 2 * c2), -right / (2 * circle2.c1 - 2 * c1), 0);
        return intersectLine(line1, intersections);
    }
}

这个函数中我们先对圆之间的关系进行了判断，相离和内含的情况去掉后，只保留有交点的情况，我们知道圆和圆的方程直接做差就是交点连线的方程，我特判了其中的两种情况，圆心连线平行和垂直于y轴的情况。然后我们利用推导出来的公式从连线上取两个特殊的点，就确定了这条直线，然后求解已知圆和直线的交点方程即可。

单元测试和警告消除

• 单元测试结果图
  

• 编译运行结果图