c++ - 如何检查两条线的交点？

Question

可能重复：
找出两条线是否相交

如果将 2 行传递给一个函数，它如何推断它们是否相交？每条线都是 2 个对象的形式CPoint——所以我总共有 4 个点。以下是我想出的。它计算每条线的斜率和 Y 轴截距，并从中计算交点。然后它检查交点是否在线段上；如果是，则返回 false；如果否，即它们不相交，则返回 true。虽然，它显示了许多问题。有没有更简单、更有效的方法来做到这一点？

注意：我不太确定用于斜率和 Y 截距的数据类型。

bool CShortestPathFinderDoc::edgeTest(CPoint P,CPoint P2,CPoint E,CPoint E2)
{
 bool status=true;
 double m1,m2;  //slopes
     double b1,b2;     //y-intercepts
 double y,x;     //intersection point

 m1=((double)P.y-P2.y)/((double)P.x-P2.x);   
 m2=((double)E.y - E2.y)/( (double)E.x - E2.x);    

 if(m1 == m2)    //if lines are colinear
    return true;


 b1=P.y-(m1*P.x)                         // Get the..
 b2=E->y - (m2*E.x);            //    Y-intercepts.

 x=(b2-b1)/(m1-m2);
 y=m1*x + b1;         //x,y is the intersection point!!!

 if((x<P2.x && x>P.x))             //if intersection point lies on line!!!!!
  {
    if(P2.y > P.y)
        if(y<P2.y && y>P.y)
            status=false;
            if(P2.y < P.y)
        if(y<P.y && y>P2.y)
                status=false;       
  }

 return status;
 }

Answer 1

Wolfram 拥有您需要的一切，特别是Line-Line Distance，即线之间的距离。如果线为零（+-epsilon），则它们相交。

Answer 2

线段交点是您要寻找的。也许您可以根据需要调整扫描线算法。

顺便说一句：在上面的代码片段中，为了确定两条二维线是否平行，您只需从输入点定义的向量计算标量积。