在此 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;
}

如果点在多边形中，则此函数 return 为真。但是，如果给定的点位于多边形的边缘，则它不会正常运行。如果该点在边缘，我应该在此处进行哪些更改以使其 return 为真？

完整代码：

#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;

但是你要小心浮点数错误。计算舍入误差会使结果错误。您可以添加 epsilon 比较：

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

Answer 2

多边形可以是凸的也可以是凹的。如果你有一个凸多边形，那么每个边界将 space 分成两半。如果从边框的角度判断一个点是否在"good place"上，并且在"wrong side"上，则该点在多边形之外。如果从凸多边形的所有边界来看，该点都在"good place"内，则在凸多边形内部。

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

如果你有两个以上的维度，那么你必须首先检查点是否在多边形所在的平面内。如果是，那么您必须按照上述方法对其进行分析。如果不在同一平面内，则不在多边形内。

在此 pnpoly 算法中包括边

Including edges in this pnpoly algorithm

c

math

graph

vertex

point-in-polygon