3

我试图创建一个函数来检查两条有限线是否相互交叉（返回 0 或 1 ）。

首先我声明这些结构

typedef struct _Point{
    double x;
    double y;
}point;
typedef struct _Line{
    int numVertex;
    point *vertex;
}line;

比，我在这里开始功能。

int lineInterceptsLine(line L1, line L2){
    double b1,b2,a1,a2,xi,yi;

    // First of all Im using both vertex to get each line equation in the form -> y=bx + a. And I start making an exception because if both vertex have the same value for x, b will be 0, but in the equation Ill endup dividing by 0 and will cause error.
    if((L1.vertex[1].x-L1.vertex[0].x)==0){
        b1 = 0; // Check line1
    }else{
        b1 = (L1.vertex[1].y-L1.vertex[0].y)/(L1.vertex[1].x-L1.vertex[0].x);
    }
    if((L2.vertex[1].x-L2.vertex[0].x)==0){
        b2 = 0; // Check line 2
    }else{
        b2 = (L2.vertex[1].y-L2.vertex[0].y)/(L2.vertex[1].x-L2.vertex[0].x);        
    }
    a1 = L1.vertex[0].y-b1*L1.vertex[0].x;
    a2 = L2.vertex[0].y-b2*L2.vertex[0].x;

    // Now I have both lines equation

    if(a1==a2){ 
        if(b1==b2){ 
        }else{
            if(((L1.vertex[0].x<0)&&(L1.vertex[1].x>0)&&(L2.vertex[0].x<0)&&(L2.vertex[1].x>0)) ||
               ((L1.vertex[0].x>0)&&(L1.vertex[1].x<0)&&(L2.vertex[0].x>0)&&(L2.vertex[1].x<0))    ) {
                return 1;
            }else{
                 return 0;
            }
        }
        return 0;
    }else if(b1==b2){
        return 0;        
    }else{
        xi = (b2-b1)/(a1-a2);
        yi = ((a2*b1)-(a1*b2))/(a2-a1);
        if(((L1.vertex[0].x-xi)*(xi-L1.vertex[1].x))>=0 && 
                ((L2.vertex[0].x-xi)*(xi-L2.vertex[1].x))>=0 && 
                ((L1.vertex[0].y-yi)*(yi-L1.vertex[1].y))>=0 && 
                ((L2.vertex[0].y-yi)*(yi-L2.vertex[1].y))>=0 )
            {
            return 1;
        }
        else{
            return 0;
        }
    }
}

我不知道为什么某些测试不起作用，例如具有以下值的测试：

   L1.vertex[0].x=0;
    L1.vertex[0].y=1;
    L1.vertex[1].x=3;
    L1.vertex[1].y=1;
    L2.vertex[0].x=2;
    L2.vertex[0].y=2;
    L2.vertex[1].x=2;
    L2.vertex[1].y=0;

如果您找不到问题并知道有效的算法，那也很棒。提前致谢！

4

3 回答 3

1
  1. 在赋值部分，我们知道你想知道两条线段是否交叉。
  2. 我不知道你定义的结构中的numVertex是什么意思，而且评论对我来说真的很难阅读，所以我重写了一个，希望它可以帮助你。

首先，两点（起点和终点）可以确定一条直线，如果两条线段相交（A线和B线），我们可以看到A线的两个点在B线的不同侧（或一个点是 B) 线的一个端口，否则它们不会越过。

typedef struct {
    int x, y;
} point;

typedef struct {
    point sp;    // start point
    point ep;    // end point
} line;

int is_segment_line_cross(line l1,  line l2)
{
    int sidea, sideb, side;     

    int l1_x_vector = l1.sp.x - l1.ep.x;
    int l1_y_vector = l1.sp.y - l1.ep.y;

    int l1_l2_ax_vector = l1.sp.x - l2.sp.x;
    int l1_l2_ay_vector = l1.sp.y - l2.sp.y;

    int l1_l2_bx_vector = l1.sp.x - l2.ep.x;
    int l1_l2_by_vector = l1.sp.y - l2.ep.y;

    sidea = l1_x_vector * l1_l2_ay_vector - l1_y_vector * l1_l2_ax_vector;
    sideb = l1_x_vector * l1_l2_by_vector - l1_y_vector * l1_l2_bx_vector;

    side = sidea * sideb;

    if (side <= 0) {
       return 1;
    } else {
       return 0;
    }

}

为什么？你可以从这里获得更多

于 2013-08-27T03:12:47.517 回答
0

垂直线会带来挑战，推荐另一种方法：参数化线 L(t) = (Ax,Ay) + t*(Dx,Dy)

// Pseudo code
// D slope
D1 = (L1[1].x - L1[0].x, L1[1].y - L1[0].y)
D2 = (L2[1].x - L2[0].x, L2[1].y - L2[0].y)

// Parametric line
L1(t1)  = (L1[0].x, L1[0].y) + t1*D1
L2(t2)  = (L2[0].x, L2[0].y) + t2*D2

// Simultaneous  equation
// Solve the 2 equations with 2 unknowns t1, t2 
(D1.x     -D2.x)(t1)    =   (L2[0].x – L1[0].x)
(D1.y     -D2.y)(t2)    =   (L2[0].y – L1[0].y)

// If determinant is 0, lines are parallel.  Special handling
// Else if 0.0  <= t0 & t1  <= 1.0, lines intersect

细节

L1[0]并且L1[1]是定义段的 2 个点。（OP 使用L1.vertex[0].x，我使用缩短L1..x notation。）L1(t1)是一个函数，它定义了一条通过这两个点的线作为 的函数t1。注意什么时候t1是 0，L1是(L1[0].x, L1[0].y)，什么时候t1是 1，(L1是L1[1].x, L1[1].y)。L2 类似。现在我们有 2 个参数线方程作为 和 的t1函数t2。

下一步是找到 和 的值，t1它们为两条线t2生成相同的(x,y)点，也就是交点。因此：

D1.x  = L1[1].x - L1[0].x
D1.y  = L1[1].y - L1[0].y
D2.x  = L2[1].x - L2[0].x
D2.x  = L2[1].y - L2[0].y
L1[0].x + t1*D1.x = L2[0].x + t2*D2.x
L1[0].y + t1*D1.y = L2[0].y + t2*D2.y
// or
DX = L2[0].x - L1[0].x
DY = L2[0].y - L1[0].y
D1.x*t1 - D2.x*t2 = DX
D1.y*t1 - D2.y*t2 = DY
// or in matrix notation
(D1.x - D2.x)(t1)  = (DX)
(D1.y - D2.y)(t2)  = (DY)
//
d = D1.x*D2.y - (-D2.x)*(-D1.y)
// if d is 0, lines are parallel and need to determine if co-incident or distinct.
t1 = ( DX(-D2.y) - DY*(- D2.x) )/d
t2 = ( DX(-D2.x) - DY*(- D1.x) )/d

最后我们有t1和t2。如果两者都在 0 到 1 的范围内，则相交发生在原始段中。这回答了“如果两条有限线（线段）相互交叉？”的问题。

于 2013-08-27T01:30:21.853 回答
0

如果我是你，我会完全重构代码。像现在这样，您可能会很快失去效率。尝试这样的事情；

/* 2D point */
typedef struct _Point{
  float x;
  float y;
} point;
/* 2D line data */
typedef struct _LineSegmentData{
  point* a;
  point* b;
} lineSegmentData;

/* General shape structure */
typedef struct _Shape shape;
typedef struct _Shape{
  void* shapeData;
  char(*shapeIntersect)(shape*,shape*);
};
    /* Shape hierarchy data */
typedef struct ShapeTree{
  shape* left;
  shape* right;
} shapeTree;

或类似的东西，然后使用边界框层次结构和函数指针使一切变得更加简单。或者，如果您不是函数指针的忠实粉丝，只需使用与定义段相同的点来定义框，并将char isLine变量作为结构的一部分。

您的代码的效率将大大提高（二进制搜索），并且更容易调试。

一切顺利！

于 2013-08-27T01:34:36.483 回答