检查有限线截取 C

Question

我正在尝试创建一个函数来检查两条有限线是否相互交叉(返回 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;

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

Answer 1

1. 在赋值部分，我们知道你想知道两条线段是否交叉。
2. 我不知道你定义的struct中的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;
    }

}

为什么？您可以从 here 获得更多信息