0

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

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

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

  3. 一个是来自这个链接的代码，它是用 C++ 实现的。

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

“问题归结为这个问题：从 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 之间，则线相交，否则不相交。如果 F P 为零，您当然无法进行计算，但在这种情况下，线是平行的，因此仅在明显的情况下相交。确切的交点是 C + F h。如果 h 恰好为 0 或 1，则线在端点处相接。你可以认为这是一个“交叉点”，也可以不是你认为合适的。”

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

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

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

  3. 我得到的交叉点比 1 多得多。

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

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

4

6 回答 6

2

您需要的是对您的 4 种方法进行单元测试并对其进行彻底测试。尤其是线段相交时，除了所有常见的公差问题（例如，“等斜率”究竟是什么意思？）之外，还有很多端点情况，例如平行斜率、重合端点、完全或部分重叠。

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

于 2009-04-01T20:11:52.277 回答
0

尽管无法看到您的代码很难说，但我怀疑您的浮点值遇到了健壮性问题。您是否考虑过使用整数点或进行某种鲁棒性增强，例如消除浮点值中的公共位？

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

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

于 2009-04-01T20:48:56.010 回答
0

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

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

//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;
}

我会从头开始，看看我想要的交叉点有什么共同点。即使对一些测试很困难，我什至没有得到好的交点，而是图表上的其他点，所以我真的很困惑。

于 2009-04-02T08:53:59.340 回答
0

为什么要重新发明轮子？

如果您可以处理依赖Boost，我会查看sandbox中的 GTL 库。有关如何下载的说明，请阅读wiki（首页上的说明）。

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

于 2009-04-02T15:37:03.547 回答
0

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

于 2010-01-25T23:23:54.883 回答
0

刚才你说：sweep algorithm……我用了boosted Myers 1985算法，当时那个算法是最好的。

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

作为两个线段的交集算法：首先明显测试范围以及线段是否平行。然后我计算了双倍的预期交点，以及两个线段的角度。每当两个线段之间的角度“小”时，我都会计算到在我的整数空间中两条线段的距离大于 1 的交点的距离。然后我将两个线段中的每一个分解为 3 个，例如 >--------< 与一个公共部分，也就是说，将交叉点单独扩展到一个线段，并删除前两个线段。如果底层的多边形变成凹形，我不介意。

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

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

于 2017-06-26T07:23:40.013 回答