How to check if rectilinear polygons intersect

user_15684879 0
Viewed 244

I am trying to create a program in C to check if the lines of rectilinear polygon intersect each other at any point.
I only need simple rectilinear polygons that do not intersect at any point. It can be counter-clockwise or clockwise.

The direction values will be less than 10. NS direction must alternate with WE direction and vice versa.

The inputs being passed are in the form of direction from an input file such as; and also shown in the pictures:

S 2 E 4 S 2 E 4 N 2 W 4 N 2 W 4

EXAMPLE Images

I tried to store points in a two-dimensional array with every point being checked as true, but I am unable to figure out how to move in case of counter and clockwise direction as the points could be N4 E6 or S4 W6. In such a case if I add when the value is N-4 (x,y) = (0,4) and subtract when S-4 (x,y) = (0,-4) that would fail when using it as index in array.

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;
}
polygon geometry c arrays algorithm
1 Answers

It might be easier to store the actual polygon rather than all possible points of the plane. We are then not restricted by the choice of the point array (arr in your code). See this working example:

  • the polygon is stored in the int-array P = {0, 0, x1, y1, x2, y2, ...}

  • segments are two-point polygons. The function 'intersection' checks if two such segments Q and P intersect; if so, returns the intersection coordinates.

  • It uses the helper function 'between' to ckeck if one number is between two others.

  • the function 'next' calculates the next point of the polygon, assuming the input is provided as char-string (eg: "S2E4S2E4N2W4N2W4")

  • In the function main we now loop over all segments, and check if they intersect with any previous one.

    Of course, the input should at some point be checked for sanity etc.

#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");
}
user_157089520
Related