救命！！！已知2条线段的两端点，求判断线段相交的算法！！！

(x1,y1) (x2, y2); k1, b1 (x1<=x2)
(x3,y3), (x4,y4); k2, b2 (x3<=x4)
if(x1 != x2)
{
      k1 = (y1 - y2) / (x1 - x2);
      b1 = y1 - k1*x1;
}
if(x3 != x4)
{
      k2 = (y3 - y4) / (x3 - x4);
      b2 = y3 - k2*x3;
}特殊情况
if(x1 == x2)
{
    if(x3 == x4)
       无交点
    else
       线段有交点(y1, k2*y1+b2)
}
else
{
   if(x3 == x4)
       线段有交点(y3, k1*y3+b1)
   else
   {
       直线有交点((b1-b2)/(k2-k1), (k1*b2-k2*b1)/(k1-k2));
       if((b1-b2)/(k2-k1) >= x1 && b1-b2)/(k2-k1) >= x3
         && ((b1-b2)/(k2-k1) <= x2 && b1-b2)/(k2-k1) <= x4)
       {
             两线段有交点;
        }
   }
}

数学方法，思路很简单
既然知道两端点，那么可以算出它的直线方程Ax+By+C=0的各个参数A，B，C，程序很容易写，都是四则运算。
假设A1x+B1y+C1=0 和 A2x+B2y+C=0
若A1*B2=A2*B1 则两直线重合或平行。否则就相交。当然也可扩展到三维

(x1,y1) (x2, y2); k1, b1 (x1<=x2)
(x3,y3), (x4,y4); k2, b2 (x3<=x4)
if(x1 != x2)
{
      k1 = (y1 - y2) / (x1 - x2);
      b1 = y1 - k1*x1;
}
if(x3 != x4)
{
      k2 = (y3 - y4) / (x3 - x4);
      b2 = y3 - k2*x3;
}特殊情况
if(k1 == k2)
    无交点
else
{
if(x1 == x2)
{
    if(x3 == x4)
       无交点
    else
       线段有交点(y1, k2*y1+b2)
}
else
{
   if(x3 == x4)
       线段有交点(y3, k1*y3+b1)
   else
   {
       直线有交点((b1-b2)/(k2-k1), (k1*b2-k2*b1)/(k1-k2));
       if((b1-b2)/(k2-k1) >= x1 && b1-b2)/(k2-k1) >= x3
         && ((b1-b2)/(k2-k1) <= x2 && b1-b2)/(k2-k1) <= x4)
       {
             两线段有交点;
        }
   }
}
}

其实很简单拉，因为只要两条直线的斜率不相等就要相交啊。
比如
  (x1,y1)(x2,y2) -----L1
  (x3,y3)(x4,y4) -----L2
  只要((y4-y3)/(x4-x3)) ==((y2-y1)/(x2-x1)) 就可以拉，干嘛那么麻烦啊。

直线 vs 线段平行 vs 不平行相交 vs 相邻 vs ...

可以用斜率，但要考虑((y4-y3)/(x4-x3)) ==((y2-y1)/(x2-x1)) 成立的条件
但变化一下 (x2-x1)*(y4-y3)==(y2-y1)*(x2-x1)
直接这种方法扩展到三维不是很方便

楼上的，斜率不相等并不一定相交，比如相邻，
我的思路是计算Line1和Line2的交点（无就说明两直线不相交，有在判断该点是不是在两直线段间）
或者边界判断在判断斜率（这样的方法快点）具体代码我就不写了

只是判断 Line1和Line2相交，没必要求交点的，
用数学里面的“叉乘”来判断就足够了，这样计算量很小

“叉乘” 就是判断两个向量相互之间的方向
设：Line1： P1, P2
    Line2:  P3, P4
在利用快速排斥（判断两条直线端点的最大和最小值之间的关系），先判断了两条直线不相交后，
      如果 t1=（P3-P1）* (P2-P1) 是向量P1P3 与P1P2之间的相对方向
           t2= (P4-P1) * (P2-P1) 是向量P1P4 与P1P2之间的相对方向      if(t1*t2<＝0) 那么相交
      else   不相交代码在下面#include <iostream.h>

class Seg{
public:
int x1, y1;
int x2, y2;
Seg(int, int, int, int);
~Seg(){};
};Seg::Seg(int a1, int b1, int a2, int b2){
x1 = a1, y1 = b1;
x2 = a2, y2 = b2;
}int max_value(int a, int b){
return a>b ? a:b;
}int min_value(int a, int b){
return a<b ? a:b;
}bool judge_range(const Seg m, const Seg n){
if(min_value(m.x1,m.x2) > max_value(n.x1, n.x2) ||
   min_value(m.y1,m.y2) > max_value(n.y1, n.y2) ||
   min_value(n.x1,n.x2) > max_value(m.x1, m.x2) ||
   min_value(n.y1,n.y2) > max_value(m.y1, m.y2))
   return 0;
return 1;
}int det(int x1, int y1, int x2, int y2){       // to calculate the det for a 2*2 matrix
return x1*y2 - x2*y1;
}bool judge_cross(const Seg m, const Seg n){    // cross experiment
int t1, t2;
t1 = det(n.x1-m.x1, n.y1-m.y1, m.x2-m.x1, m.y2-m.y1);  //direction 1
t2 = det(n.x2-m.x1, n.y2-m.y1, m.x2-m.x1, m.y2-m.y1);  //direciton 2
if(t1*t2 <= 0) return 1;                                // yes: in two different directions
return 0;                                            // no :
}int main()
{
int a1, b1, a2, b2;
cout << "Input the location for Point A:" << endl;
cin >> a1 >> b1 >> a2 >> b2;
    Seg m(a1, b1, a2, b2);
cout << "Input the location for Point B:" << endl;
cin >> a1 >> b1 >> a2 >> b2;
Seg n(a1, b1, a2, b2); if(judge_range(m, n) && judge_cross(m, n))
cout << "The two segment cross indeed!" << endl;
else cout << "Not cross!" << endl; return 1;
}

按照CPUFU()的方法还是解决不了，我的函数如下
BOOL IsIntersect(POINT p1,POINT p2,POINT p3,POINT p4)
{
CVector P1(p1.x,p1.y);
CVector P2(p2.x,p2.y);
CVector P3(p3.x,p3.y);
CVector P4(p4.x,p4.y); BOOL a=((P2-P1)^(P3-P1))<0;
BOOL b=((P4-P1)^(P2-P1))<0; if(a&&b)
return TRUE;
else return FALSE;
}

我按照cupful的代码原封不动的运行，感觉判断得还是有问题啊

http://222.76.141.171/bbs/dispbbs.asp?boardID=54&ID=2369&page=1
你看看就知道了

我是在窗口内用橡皮筋画法画折线，每次得折线都不能相交，我在OnLButtonDown（）里判断，但有问题啊

已知直线ab和cd。
1.求ab、ac和ad的斜率
如果ab的斜率在ac和ad的斜率之间执行2
2.求ca、cd和cb的斜率（1、2可以抽成一个函数）
如果cb的斜率不在ca和cd之间，ab和cd可以判定相交
写的不是很清晰，但是应该是可行的
另外边界值没有说明，到时候自己考虑吧。
以上是2维情况，3维情况可以转化为2维，因为相交的两个线段应该在一个平面内。至于多维的就要看看书了。

调试易

救命！！！已知2条线段的两端点，求判断线段相交的算法！！！

解决方案 »