Включение ребер в этот алгоритм pnpoly

Question

У меня есть эта точка в функции многоугольника для использования в моей программе поиска пути.

int point_in_pol(int vertcount, float *vertx, float *verty, int vertexx, int vertexy){
    double vertexx1;
    vertexx1 = vertexx;
    double vertexy1;
    vertexy1 = vertexy;
  int i ,j, c = 0;
  for (i = 0, j = vertcount-1; i < vertcount; j = i++) {
    if ( (((verty[i]>=vertexy1) && (verty[j]<=vertexy1) )  ||  ((verty[i]<=vertexy1)   && (verty[j]>=vertexy1) )) &&
     (vertexx1 < (vertx[j]-vertx[i]) * (vertexy1-verty[i]) / (verty[j]-verty[i]) + vertx[i]) )
       c = !c;
  }
  return c;
}

Эта функция возвращает true, если точка находится в многоугольнике. Тем не менее, он не ведет себя должным образом, если указанная точка находится на краю многоугольника. Какие изменения я должен сделать здесь, чтобы вернуть значение true, если точка находится на краю?

весь код:

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


typedef struct Node Node;
typedef struct Qnode Qnode;
void enqueue(Node* node);
void enqueue_left(Node* node);
Node* generate(int x, int y);
Node* dequeue();
void expand(Node* node, int xend, int yend);
int point_in_pol(int vertcount, float *vertx, float *verty, int vertexx, int vertexy);
struct Node{
    Node* predecessor;
    Node* up;
    Node* down;
    Node* left;
    Node* right;
    int xpos;
    int ypos;
    int marked;
};
struct Qnode{
    Qnode* next;
    Node* Gnode; 
};
Qnode* front = NULL;
Qnode* rear = NULL;
int queuesize = 0;
int des;
int solutioncost = 0;
Node* closednodes[80000];
int nodesclosed = 0;
float polygonx[20][50];
float polygony[20][50];
int polycount = 0, vertcount = 0;
int vertcounts[20];

void enqueue(Node* node){
    if (queuesize == 0){
        rear = (Qnode*)malloc(sizeof(Qnode));
        rear->Gnode = node;
        rear->next = NULL;
        front = rear;
    }
    else{
        Qnode* temp = (Qnode*)malloc(sizeof(Qnode));
        rear->next = temp;
        temp->Gnode = node;
        temp->next = NULL;
        rear = temp;
    }
        queuesize++;
}
void enqueue_left(Node* node){
    if(queuesize == 0){
        front = (Qnode*)malloc(sizeof(Qnode));
        front->Gnode = node;
        front->next = NULL;
        rear = front;
    }
    else{
        Qnode* temp = (Qnode*)malloc(sizeof(Qnode));
        temp->Gnode = node;
        temp->next = front;
        front = temp;
    }
    queuesize++;
}

Node* dequeue(){
    Qnode* temp = front;
    if (queuesize == 0){
        printf("Error!");
    }
    else{
        Node* temp1 = front->Gnode;
        temp = front->next;
        free(front);
        front = temp;
        queuesize--;
        return temp1;
    }

}

Node* generate(int x, int y){
    int i = 0, j = 0;
    //printf("Generating node (%d,%d)...\n", x, y);
    if ((x >0 && x <=400) && (y >0 && y <=200)){
    Node* temp = (Node*)malloc(sizeof(Node));
    temp->xpos = x;
    temp->ypos = y;
    temp->marked = 0;
    for(i; i<polycount; i++){
        if(point_in_pol(vertcounts[i], polygonx[i],polygony[i], x, y)){
            temp->marked = 1;
        }
    }
    temp->up = NULL;
    temp->predecessor = NULL;
    temp->down = NULL;
    temp->left = NULL;
    temp->right = NULL;
    return temp;
    }
    else{
        printf("Invalid starting point! \n");
    }
}

void expand(Node* node, int xend, int yend){
    //printf("Expanding node (%d, %d)...\n", node->xpos, node->ypos);
    solutioncost++;
    int flag = 0;
    closednodes[nodesclosed] = node;
    nodesclosed++;
    dequeue();
    if(node->marked == 1){
    //  printf("Cannot expand. Part of a polygon.\n");
    }

    else{
        if (node->xpos == xend && node->ypos == yend){
            printf("Node reached!");
            printf("Path in reverse order: \n(%d, %d)\n", xend, yend);
            while(node->predecessor!= NULL){
                printf("(%d, %d)\n", node->predecessor->xpos, node->predecessor->ypos);
                node = node->predecessor;
            }
            queuesize = 0; 
            return;
        }
        if (node->xpos-1 >0 && node->left == NULL){
            int k = 0;
            int j = 0;
            Qnode* temp2 = front;
            for(k; k<queuesize; k++){
                int xx = temp2->Gnode->xpos;
                int yy = temp2->Gnode->ypos;
                if (xx == node->xpos-1 && yy == node->ypos)
                    flag = 1;
                temp2 = temp2->next;
                }
            for(j; j<nodesclosed; j++){
                int xx = closednodes[j]->xpos;
                int yy = closednodes[j]->ypos;
                if (xx == node->xpos-1 && yy == node->ypos)
                    flag = 1;
            }
            if (flag == 0){
                node->left = generate(node->xpos-1, node->ypos);
                node->left->predecessor = node;
                node->left->right = node;
                if(des == 1)
                    enqueue(node->left);
                else if(des == 2)
                    enqueue_left(node->left);
            }
            else{
                //printf("(%d, %d) not generated.\n", node->xpos-1, node->ypos);
                flag = 0;
            }
        }
        if (node->xpos+1 <=400 && node->right ==NULL){
        int k = 0;
        int j = 0;
        Qnode* temp2 = front;
            for(k; k<queuesize; k++){
                int xx = temp2->Gnode->xpos;
                int yy = temp2->Gnode->ypos;
                if (xx == node->xpos+1 && yy == node->ypos)
                    flag = 1;
                temp2 = temp2->next;
                }

            for(j; j<nodesclosed; j++){
                int xx = closednodes[j]->xpos;
                int yy = closednodes[j]->ypos;
                if (xx == node->xpos+1 && yy == node->ypos)
                    flag = 1;
            }
            if (flag == 0){
                node->right = generate(node->xpos+1, node->ypos);
                node->right->predecessor = node;
                node->right->left = node;
                if(des == 1)
                    enqueue(node->right);
                else if(des == 2)
                    enqueue_left(node->right);
            }
            else{
                //printf("(%d, %d) not generated.\n", node->xpos+1, node->ypos);
                flag = 0;
            }
        }
        if (node->ypos+1 <=200 && node->up ==NULL){
        int k = 0;
        int j = 0;
        Qnode* temp2 = front;
        for(k; k<queuesize; k++){
            int xx = temp2->Gnode->xpos;
            int yy = temp2->Gnode->ypos;
            if (xx == node->xpos && yy == node->ypos+1)
                flag = 1;
            temp2 = temp2->next;
                }   
            for(j; j<nodesclosed; j++){
                int xx = closednodes[j]->xpos;
                int yy = closednodes[j]->ypos;
                if (xx == node->xpos && yy == node->ypos+1)
                    flag = 1;
            }

            if (flag ==0){
                node->up = generate(node->xpos, node->ypos+1);
                node->up->predecessor = node;
                node->up->down = node;
            if(des == 1)
                enqueue(node->up);
            else if(des == 2)
                enqueue_left(node->up);
            }
            else{
                //printf("(%d, %d) not generated.\n", node->xpos, node->ypos+1);
            flag = 0;
            }
        }
        if (node->ypos-1 >0 && node->down ==NULL){
        int k = 0;
        int j = 0;
        Qnode* temp2 = front;
            for(k; k<queuesize; k++){
                int xx = temp2->Gnode->xpos;
                int yy = temp2->Gnode->ypos;
                if (xx == node->xpos && yy == node->ypos-1)
                    flag = 1;
                temp2 = temp2->next;
                }

            for(j; j<nodesclosed; j++){
                int xx = closednodes[j]->xpos;
                int yy = closednodes[j]->ypos;
                if (xx == node->xpos && yy == node->ypos-1)
                    flag = 1;
            }
            if (flag ==0){
                node->down = generate(node->xpos, node->ypos-1);
                node->down->predecessor = node;
                node->down->up = node;
            if(des == 1)
                enqueue(node->down);
            else if(des == 2)
                enqueue_left(node->down);
            }
            else{
        //  printf("(%d, %d) not generated.\n", node->xpos, node->ypos-1);
            flag = 0;
            }
        }
        return;
    }

}

int point_in_pol(int vertcount, float *vertx, float *verty, int vertexx, int vertexy){
    double vertexx1;
    vertexx1 = vertexx;
    double vertexy1;
    vertexy1 = vertexy;
  int i ,j, c = 0;
  for (i = 0, j = vertcount-1; i < vertcount; j = i++) {
    if ( (((verty[i]>=vertexy1) && (verty[j]<=vertexy1) )  ||  ((verty[i]<=vertexy1)   && (verty[j]>=vertexy1) )) &&
     (vertexx1 < (vertx[j]-vertx[i]) * (vertexy1-verty[i]) / (verty[j]-verty[i]) + vertx[i]) )
       c = !c;
   // if ((vertexx1 == ((vertx[j]-vertx[i]) * (vertexy1-verty[i]) / (verty[j]-verty[i])+ vertx[i])) )
//  return 1;
  }
  return c;
}

int main(){

    printf("\nFILE NUMBER 1\n");

    int x_start, y_start, x_end, y_end;
    clock_t begin, end;
    double time_spent;
    FILE *fp;
    fp = fopen("1.txt", "r");
    if (fp == NULL)
        printf("Error printing output. \n");
    else
    fscanf(fp, "(%d,%d)\n", &x_start, &y_start);
    fscanf(fp, "(%d,%d)\n", &x_end, &y_end);
    printf("Starting point is (%d, %d)\n", x_start, y_start);
    printf("Ending point is (%d, %d)\n", x_end, y_end);
    char temp3[255];
    char* source;
    int t;
    while(fgets(temp3, 255, fp)!= NULL){
        source = temp3;
        t = 0;
        printf("Polygon %d: ", polycount);
        while(sscanf(source, "(%f,%f)%*[^(]%n", &polygonx[polycount][vertcount], &polygony[polycount][vertcount], &t) == 2){
            printf("(%.2f,%.2f),",polygonx[polycount][vertcount], polygony[polycount][vertcount]);
            source+=t;
            vertcount++;
        }
        printf("\n");
        vertcounts[polycount] = vertcount;
        vertcount = 0;
        polycount++;
    }
    printf("Select a search algorithm:\n 1. BFS\n 2: DFS\n 3: A*");
    scanf("%d", &des);
    if (des == 1 || des == 2){
        begin = clock();
        Node* start = generate(x_start, y_start);
        enqueue(start);
        while(queuesize!=0){
        expand(front->Gnode, x_end, y_end);
        }
        end = clock();
        time_spent = (double)(end - begin) / CLOCKS_PER_SEC;
        printf("Solution cost is: %d.\n", solutioncost);
        printf("Running time is %f.\n", time_spent);

        fclose(fp);
    }
}

используя это как ввод для 1.txt:

(4,4)
(1,1)
(3,2),(2,2),(2,3),(3,3)

не даст ответа

Answer 1

int
point_in_pol(int vertcount, float *vertx, float *verty,
int vertexx, int vertexy)
{
    double vertexx1;
    vertexx1 = vertexx;
    double vertexy1;
    vertexy1 = vertexy;

    int i ,j, c = 0;
    for (i = 0, j = vertcount-1; i < vertcount; j = i++)
    {
        if ( (((verty[i]>=vertexy1) && (verty[j]<=vertexy1) )
            || ((verty[i]<=vertexy1) && (verty[j]>=vertexy1))) // this checks
                                                               // whether y-coord
                                                               // i.e. vertexy1 is
                                                               // between edge's
                                                               // vertices
            && (vertexx1 < (vertx[j]-vertx[i]) 
                * (vertexy1-verty[i]) / (verty[j]-verty[i])
                                              + vertx[i]) )    // this checks
                                                               // whether x-coord
                                                               // i.e. vertexx1
                                                               // is to the left
                                                               // of the line

       c = !c;
  }
  return c;
}

Прототип этого алгоритма называется pnpoly, и его объяснение можно найти здесь. Одним из его ограничений является то, что он не может обрабатывать точки, расположенные точно на границе, то есть он не может сказать, когда это так.

Точка на границе

Pnpoly разбивает плоскость на точки внутри многоугольника и точки вне многоугольника. Точки, которые находятся на границе, классифицируются как внутри или снаружи.

Я думаю, что это должно сработать:

if (vertexx1 == (vertx[j]-vertx[i]) 
     * (vertexy1-verty[i]) / (verty[j]-verty[i])
                                   + vertx[i]) ) // this will check if vertexx1
                                                 // is equal to x-coordinate
                                                 // of what would have point on the
                                                 // edge with y=vertexy1 had
    return 1;

Но вы должны быть осторожны с ошибкой с плавающей точкой. Вычислительная ошибка округления сделает результат неправильным. Вы можете добавить эпсилон сравнения:

if (fabs(vertexx1 - (vertx[j]-vertx[i]) 
     * (vertexy1-verty[i]) / (verty[j]-verty[i])
                                   - vertx[i]) < EPSILON)
    return 1;

Answer 2

Многоугольник может быть выпуклым или вогнутым. Если у вас выпуклый многоугольник, то каждая граница разделяет пространство на две половины. Если вы определяете, находится ли точка в "хорошем месте" с точки зрения границы и находится ли она "с другой стороны", то эта точка находится за пределами многоугольника. Если точка находится в "хорошем месте" с точки зрения всех границ выпуклого многоугольника, то она находится внутри выпуклого многоугольника.

Если у вас есть вогнутый многоугольник, то вы можете определить свой вогнутый многоугольник как набор выпуклых многоугольников. Если точка находится внутри любого из этих выпуклых многоугольников, то она находится внутри вогнутого многоугольника.

Если у вас более двух измерений, вы должны сначала проверить, находится ли точка внутри плоскости, где находится многоугольник. Если да, то вы должны проанализировать это, как описано выше. Если он не находится в той же плоскости, то он не находится внутри многоугольника.