计算两条边的交集

Question

我有一个二维空间中的边和顶点的大图。 大图由 C++ 库中计算的函数返回。 我正在阅读该图并使用它来计算其边缘（线段）的所有交点。 我使用扫描算法。 为了检测两个边缘的交点，我遇到了一些问题。 我有 4 种不同的方法，根据这些方法我测试两条边是否相交，如果是的话，我计算并保留它们的交集：

1. 一种方法测试两条边是否是多边形的对角线。 那是 插入方程的一条线的边缘坐标 另一条线有不同的符号。

2. 每次计算交集并检查是否 找到的交集位于两个线段的端点之间。

3. 其中一个是来自此链接的代码 虽然是用 C++ 实现的。

4. 实现了 Jason Cohen ín 提出的第一种方法 这个问题。

“问题归结为这个问题：从 A 到 B 和从 C 到 D 的两条线相交吗？然后你可以问它四次（在该线和矩形的四个边之间）。

这是用于执行的向量数学我假设从 A 到 B 的线是有问题的线，从 C 到 D 的线是矩形线之一，我的符号是 Ax 是“A 的 x 坐标”，Cy 是“ C 的 y 坐标。” 并且“*”表示点积，因此例如：

A*B = Ax*Bx + Ay*By.
E = B-A = ( Bx-Ax, By-Ay )
F = D-C = ( Dx-Cx, Dy-Cy ) 
P = ( -Ey, Ex )
h = ( (A-C) * P ) / ( F * P )

这个 h 数字是关键。如果 h 介于 0 和 1 之间，则线相交，否则不相交。如果 FP为零，当然您无法进行计算，但在这种情况下，直线是平行的，因此仅在明显的情况下相交。 确切的交点是C + Fh。 如果 h 恰好为 0 或 1，则直线在端点处相交。 您可以将其视为“交集”，也可以不考虑，如您认为合适。”

对于我创建的数据（具有双值的小数据），我使用所有 4 个实现的方法获得了良好的结果。当我使用在 C++ 中实现的这些方法中的任何一个时，来自大图的数据我每次都会得到不同的结果，并且结果不佳：

1. 方法返回我需要的更多交集（所有点都在图上），但我得到太多点。

2. 无论如何，我总是获得 0 个交点。

3. 无论如何 我得到的交集比 1 多得多。

4. 对于某些示例，我得到的点不在图表上（因此甚至没有交集）。例如，我得到交点加上一些其他点。

我不知道问题出在哪里。 关于如何计算交集并测试它的任何建议或任何其他想法都非常受欢迎。 谢谢你，马达丽娜

Answer 1

您需要的是对 4 种方法进行单元测试并彻底测试它们。 特别是对于线段相交，除了所有常见的公差问题（例如，“等斜率”是什么意思？）。

如果不将事物分解为更小、更可测试的单元，您将很难缩小范围。

Answer 2

虽然在看不到您的代码的情况下很难说，但我怀疑您的浮点值遇到了鲁棒性问题。 您是否考虑过使用整数点或进行某种鲁棒性增强，例如消除浮点值中的公共位？

有一个名为 GEOS 的开源几何库（http://trac.osgeo.org/geos/）这可能有助于测试您的数据集。 GEOS 中还有一些算法可以对整数网格执行快速舍入并消除公共位，以帮助您确定是否遇到鲁棒性问题。 进一步值得注意的是 GEOS 如何使用同质空间中的点线对偶性计算交集（我无法完全判断您描述的点积投影技术在数学上是否等效）。

顺便说一句，我最喜欢的计算边图中相交的解决方案是结合使用扫描线和单调边链。 当您使用单调链时，您可以消除大量边相交测试，因为链本身永远不会相交。 这就是 GEOS 所做的。

Answer 3

为什么要重新发明轮子？

如果您可以处理对 Boost 的依赖，我会查看 沙箱。 有关如何下载此文件的说明，请阅读 wiki（说明就在前面页）。

GTL 库适合您的数据结构的任何实现（即，它是按照 STL 的精神设计的，其中数据结构和算法是正交的）。 该代码既快速又正确。 如果可以的话检查一下。

Answer 4

您可能想尝试Boost.Geometry（又名通用几何库）。

Answer 5

当我计算交集时，我在单调边缘上使用扫描线（我有一个排序函数，可以对构造函数内的边缘进行排序，并测试它们，它们是有序的），即使我获得了一些作为交集的点，这些点是一些边缘，尽管我有很多测试来消除这种情况。

这是第四种方法的代码（它给了我迄今为止最好的结果，但不是所有的交集，但至少与其他方法相比有一些好的交集）：

//4 method
double* QSweep::findIntersection(edge_t edge1,edge_t edge2) {  
    point_t p1=myPoints_[edge1[0]];
    point_t p2=myPoints_[edge1[1]];
    point_t p3=myPoints_[edge2[0]];
    point_t p4=myPoints_[edge2[1]];

    double xD1,yD1,xD2,yD2,xD3,yD3,xP,yP,h,denom;
    double* pt=new double[3];

    // calculate differences  
    xD1=p2[0]-p1[0];  
    xD2=p4[0]-p3[0];  
    yD1=p2[1]-p1[1];  
    yD2=p4[1]-p3[1];  
    xD3=p1[0]-p3[0];  
    yD3=p1[1]-p3[1];    

    xP=-yD1;
    yP=xD1;
    denom=xD2*(-yD1)+yD2*xD1;
    if (denom==0) {
        return NULL;
    }
    else{
    h=(xD3*(-yD1)+yD3*xD1)/denom;
    }
    std::cout<<"h is"<<h<<endl;
    if ((h>0)&&(h<1)){
        pt[0]=p3[0]+xD2*h;  
        pt[1]=p3[1]+yD2*h;
        pt[2]=0.00;
    }
    else{
        return NULL;
    }

    // return the valid intersection  
    return pt;  
}

void QSweep:: intersection(){
    nbIntersections=0;
    double* vector;
    for (int i=2;i<myEdges_.size()-1;i++){
        vector=findIntersection(myEdges_[i-1],myEdges_[i]);
        if (vector!=NULL){
                nbIntersections++;
                myIntersections.push_back(vector);
                swap(myEdges_[i-1], myEdges_[i]);
        }
    }
}

交集函数总是相同的，所以我只是找到 <代码>findIntersection函数。

对于方法 1 和 2，我使用以下版本的 findIntersection 函数：

double* QSweep::computeIntersection(double m1, double b1, double m2, double b2){
    double* v=new double[3];

    v[0]= (b2-b1)/(m1-m2);
    v[1]= (m1*b2-m2*b1)/(m1-m2);
    v[2]=0.00;
    return v;
    }

    double* QSweep::findIntersection(edge_t edge1, edge_t edge2){


    //equation for the support line of the first edge

    double a=myPoints_[edge1[0]][0];
    double b=myPoints_[edge1[0]][1];
    double c=myPoints_[edge1[1]][0];
    double d=myPoints_[edge1[1]][1];
    double m1=getSlope(a,b,c,d);
    double b1=getYIntercept(a,b,c,d);

    double x=myPoints_[edge2[0]][0];
    double y=myPoints_[edge2[0]][1];
    double s=myPoints_[edge2[1]][0];
    double t=myPoints_[edge2[1]][1];
    double m2=getSlope(x,y,s,t);
    double b2=getYIntercept(x,y,s,t);
    double* vector;

    double line2InLine1=evalEqnLineD(myPoints_[edge2[0]],edge1);
    double line2InLine1New=evalEqnLineD(myPoints_[edge2[1]],edge1);
    double line1InLine2=evalEqnLineD(myPoints_[edge1[0]],edge2);
    double line1InLine2New=evalEqnLineD(myPoints_[edge1[1]],edge2);

    if (m1==m2){
        return NULL;
    }
    else{

            if ((line1InLine2*line1InLine2New)<0 &&   (line2InLine1*line2InLine1New)<0){
            vector=computeIntersection(m1,b1,m2,b2);

            if ((vector[0]>a && vector[0]<c)&&(vector[0]>x && vector[0]<s)){
                return vector;
            }
            else{
                return NULL;
            }
        }
        else{
            return NULL;
        }
    }
    return vector;
}

我将从头开始，看看我想要的交点有哪些共同点。 即使在一些测试中很困难，我什至没有得到好的交点，但得到了图表上的其他点，所以我真的很困惑。

Answer 6

刚才你说：扫频算法...
我使用了 boosted Myers 1985 算法，当时该算法是最好的。

我所做的：使用整数 - 即固定精度。 - 数字，处理精度问题。

作为两个线段的交集算法：
首先对范围进行明显的测试以及线段是否平行。
然后我计算了双精度的预期交点以及两条线段的角度。
每当两条线段之间的角度“小”时，我都会计算距交点的距离，在该交点处，两条线段的距离在整数空间中变得大于 1。
然后我将两条线段分别分成 3 个，如 >--------< 具有公共部分，也就是说将交叉点扩展为自己的一个段，并删除了前两个段。 如果下面的多边形变成凹面，我不会担心。

由于计算线段是为了计算多边形的细分图，因此细分图不是两个几乎平行的线段，而是只有 3 个具有更健康角度的线段。

提升还包含事件点的分布式合并排序（现在：这样的算法是非常可并行的！！！），从而降低了排序本身的复杂性，从预期的 O(n log n) 到预期的 O(n)，但 O (n log n) 最坏情况。 我强烈建议重新审视扫描（单线程）算法，采用一些并行化的分而治之的技术。