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

Question

我正在尝试用 C 编写一个程序来检查直线多边形的线是否在任何点相互相交。
我只需要在任何点都不相交的简单直线多边形。可以逆时针也可以顺时针

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

传递的输入采用来自输入文件的方向形式，例如；也显示在图片中：

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）。请参阅此工作示例：

多边形存储在整数数组 P = {0, 0, x1, y1, x2, y2, ...}
线段是两点多边形。函数 'intersection' 检查是否两个这样的线段 Q 和 P 相交；如果是这样，returns 交点坐标。
它使用辅助函数 'between' 检查一个数字是否介于两个其他数字之间。
函数'next'计算多边形的下一个点，假设输入以字符串形式提供（例如：“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");
}

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

How to check if rectilinear polygons intersect

c

arrays

algorithm

geometry

polygon