计算两条边的交点-Java 学习之路

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

测试两条边是多边形的对角线的一条 . 也就是插入另一条方程的一条边的坐标有不同的符号 .
每次计算交点并检查找到的交点是否在两个段的 endpoints 之间 .
尽管是在C中实现的this link代码 .
实现Jason Cohen提出的第一种方法this question .

“问题减少到这个问题：从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介于0和1之间，则线相交，否则不相交 . 如果FP为零，当然您无法进行计算，但在这种情况下，线条是平行的，因此仅在明显的情况下相交 . 确切的交点是C Fh . 如果h恰好为0或1，则线条在终点处触摸 . 您可以认为这是"intersection"或不适合您 . “

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

方法返回我需要的更多交叉点（所有点都在图表上）但是我得到的点太多了 .
无论怎样，我总是获得0个交叉点 .
我得到了比1更多的交集 .
对于一些例子，我得到了不在图上的点（所以甚至不是交点） . 但是对于一些例子，我得到交叉点加上其他一些点 .

我不知道问题出在哪里 . 关于如何计算交叉点并对其进行测试的任何建议或任何其他想法都是受欢迎的 . 谢谢，madalina

6 回答

0

为什么重新发明轮子？

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

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

回复于 2024-04-28T16:57:15+08:00
0

您可能想尝试Boost.Geometry (aka Generic Geometry Library) .

回复于 2024-04-28T16:57:15+08:00
2

您需要的是4种方法的单元测试并彻底测试它们 . 特别是对于线段交叉点，除了所有常见的公差问题（例如"equal slope"究竟是什么意思？）之外，还有许多终端情况，例如平行斜率，重合终点，完全或部分重叠 .

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

回复于 2024-04-28T16:57:15+08:00
0

虽然很难说没有能够看到你的代码，但我怀疑你的浮点值存在稳健性问题 . 您是否考虑过使用整数点或进行某种鲁棒性增强，例如消除浮点值中的公共位？

有一个名为GEOS（http://trac.osgeo.org/geos/）的开源几何库，它可能对测试您的数据集很有用 . GEOS中还有一些算法可以对整数网格执行快速舍入，并消除常见位以帮助您确定是否遇到稳健性问题 . 另外值得注意的是GEOS如何在均匀空间中使用点线对偶来计算交点（我不能确定你所描述的点积投影技术是否在数学上是等价的） .

另外，我最喜欢的在边缘图中计算交叉点的解决方案是使用扫描线和单调的边缘链 . 当你使用单调链时，你可以消除很多边缘相交测试，因为链从不相交 . 这就是GEOS所做的 .

回复于 2024-04-28T16:57:15+08:00

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

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

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

我将从头开始再看看我想要的交叉点有什么共同之处 . 即使对某些测试很难，我甚至没有得到好的交叉点，但是图中的其他点，所以我真的很困惑 .

回复于 2024-04-28T16:57:15+08:00

0

只是你说：扫描算法...我使用了一个提升的迈尔斯1985算法，那时算法是最好的 .

我做了什么：使用整数 - 即固定的prec . - 数字，以处理精度问题 .

作为两个相关段的交集算法：第一个明显的范围测试和段是否平行 . 然后我计算了双倍的预期交叉点，以及两个段的角度 . 每当两个段之间的角度为“小”时，我计算了距离交叉点的距离，其中两个线段的距离在我的整数空间中变得大于1 . 然后我将两个线段中的每一个分成3个像> ------- <的公共部分，所以说将交叉点自己扩展到一个段，并删除前两个段 . 如果下面的多边形变得凹陷，我没有打扰 .

由于计算了用于计算多边形的细分图的分段，因此细分图而不是两个几乎平行的分段仅具有3个具有更 Health 角度的分段 .

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

回复于 2024-04-28T16:57:15+08:00

计算两条边的交点

6 回答

相关问题