如何检查直线多边形是否相交

Question

我试图在C中创建一个程序来检查直线多边形的直线在任何一点上是否相交。

我只需要简单的直线多边形，在任何一点都不相交。它可以是逆时针，也可以是顺时针.

方向值将小于10。NS方向必须与我们的方向交替，反之亦然。

正在传递的输入以来自输入文件(例如；)的方向的形式传递，并且还显示在图片中：

S_2 E_4 S_2 E_4 N_2 W_4 N_2 W_4

​

​

我试图将点存储在二维数组中，每个点都被检查为真，但我无法弄清楚如何在逆时针方向移动，因为这些点可能是N4 E6或S4 W6。在这种情况下，如果我将值加为N-4 (x，y) = (0,4)，而当S-4 (x，y) = (0，-4)时减去，则当将其用作数组中的索引时，将失败。

int arr[10][10];
int xPrime = 0, yPrime = 0;

bool checkContinuity(int y, const char * dir ){

    if(strcmp(dir, "S")==0){
        y = -y;
        cols = y;
        int j;
        for(j = cols; j >= 0; j--){
            if(arr[xPrime][j] == 1 && j != yPrime){
                return false;
            }
            arr[xPrime][j] = 1;             
            printf(" %d ", j);
        }
        yPrime -= y;
        if(yPrime < 0)
            yPrime = -yPrime;
    }
    else if(strcmp(dir, "W")==0){
        y = -y;
        cols = y;       
        int j;
        for(j = cols; j >= 0; j--){
            if(arr[j][yPrime] == 1 && j != xPrime && (j != 0 && yPrime != 0)){
                return false;
            }
            arr[j][yPrime] = 1;
            printf(" %d ", j);  
        }
        xPrime -= y;
        if(xPrime < 0)
            xPrime = -xPrime;
    }
    else if(strcmp(dir, "N")==0){
        cols = y;
        int j;
        for(j = 0; j <= cols; j++){
            if(arr[xPrime][j] == 1)
                return false;
            arr[xPrime][j] = 1; 
            printf(" %d ", j);
        }
        yPrime += y;
    }
    else if(strcmp(dir, "E")==0){
        cols = y;
        int j;
        for(j = 0; j <= cols; j++){
            if(arr[j][yPrime] == 1 && j != xPrime)
                return false;
            arr[j][yPrime] = 1;
            printf(" %d ", j);  
        }
        xPrime += y;
    }
    else
        return false;
            
    return true;
}

Answer 1

它可能更容易存储实际多边形，而不是所有可能的点的平面。然后，我们将不受点数组的选择(代码中的arr)的限制。参见此工作示例：

多边形存储在int数组P= {0，0，x1，y1，x2，y2，.}中。

• 片段是两点多边形.函数“交集”检查两个这样的段Q和P是否相交；如果是，则返回交集坐标.

• --它使用助手函数“中间”来模仿一个数字是否介于另外两个数字之间。

函数“next”计算多边形的下一个点，假设输入以char-string形式提供(例如："S2E4S2E4N2W4N2W4") )。

函数main中的

• 现在循环遍历所有段，并检查它们是否与前面的段相交。

当然，应该在某个时候检查输入是否正常，等等，。

#include <stdio.h>
#include <string.h>
#include <stdlib.h>


void
next(           const char *s,
                int *v          )
{
        v[2] = v[0]; 
        v[3] = v[1];
        int step = s[1] - '0';
        switch(s[0]) {
        case 'S': v[3] -= step; break;
        case 'N': v[3] += step; break;
        case 'W': v[2] -= step; break;
        case 'E': v[2] += step; break;
        }
}


int
between(        int x,
                int a,
                int b           )
{
        return a < b ? x >= a && x <= b : x >= b && x <= a;
}

int
intersection(   int *P,
                int *Q,
                int *R          )
{
        if(P[0] == P[2] && Q[1] == Q[3]){  // P vertical, Q horizontal (w.l.o.g.)
                if(between(P[0], Q[0], Q[2]) && between(Q[1], P[1], P[3])){
                        R[0] = P[0]; 
                        R[1] = Q[1]; 
                        return 1;
                } else
                        return 0;
        }else if(Q[0] == Q[2] && P[1] == P[3])
                return intersection(Q, P, R);
        else return 0;
}

int
main() {
        char *s = "S2E4S2E4N2W4N2W4";
        
        int n = strlen(s) / 2,                                  // number of steps
                *P = calloc((n + 1) * 2, sizeof(int)),          // polygon
                R[2];                                           // intersection
        if(!P) exit(137);
        
        for(int k = 0; k < n; k++){
                next(s + 2 * k, P + 2 * k);
                for(int j = 0; j < k - 1; j++) {
                        if(intersection(P + k * 2, P + j * 2, R)) {
                                printf("Intersection at: %d, %d\n", R[0], R[1]);
                                exit(0);
                        }
                }
        }
        printf("No intersection\n");
}