在这个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。但是，如果给定的点位于多边形的边上，它将无法正常工作。如果点位于边缘，我应该做些什么改变才能使其返回真？

整个代码：

#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它的解释可以发现here。其中一个限制是它不能处理完全位于边界上的点，即它不能说明它是什么时候的情况。

点上的（边界）边缘

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

多边形可以是凸或凹。如果您有一个凸多边形，则每个边框将分隔两半的空间。如果从边界的角度来确定一个点是否处于“合适的位置”，并且位于“错误的一边”，那么该点位于多边形之外。如果从凸多边形的所有边界的角度来看，该点处于“良好位置”，则它位于凸多边形内部。

如果您有一个凹多边形，那么您可以将您的凹多边形定义为一组凸多边形。如果点在任何这些凸多边形内部，那么它位于凹多边形内部。

如果您有两个以上的尺寸，那么您必须首先检查点是否在多边形所在的平面内。如果是的话，那么你必须按照上面的描述进行分析。如果它不在同一平面内，那么它不在多边形内。