在這個pnpoly算法中包含邊緣

我有這個要點在我的尋路程序中使用的多邊形函數。在這個pnpoly算法中包含邊緣

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)

將產生無應答

來源

2015-09-27 bhounter

Point * on *邊緣應該是一種罕見的情況。幸運的是，檢查一個點是否在線段上是一個直截了當的計算（它唯一的缺點實際上是計算機的有限數學精度）。我會建議爲它創建一個單獨的函數，並且只檢查point-in-poly是否返回false。您可能需要在調用這些函數之前添加全局邊界框檢查（並且如果您有大量的多邊形檢查，請緩存邊界）。 – usr2564301

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;

來源

2015-09-27 11:48:04 4pie0

它沒有做到這一點。 :(注意，我將第一個不等式改爲至少用水平線（如方框）在多邊形上得到正確的輸出。 – bhounter

@bhounter它是最有可能的，因爲浮點錯誤的 – 4pie0

@tinky_winky上你認爲哪會出現這些浮點錯誤類型的參數？我只在這個函數中使用了所有的整數輸入，即使是最簡單的輸入也不行。 – bhounter

多邊形可以是凸或凹。如果您有一個凸多邊形，則每個邊框將分隔兩半的空間。如果從邊界的角度來確定一個點是否處於「合適的位置」，並且位於「錯誤的一邊」，那麼該點位於多邊形之外。如果從凸多邊形的所有邊界的角度來看，該點處於「良好位置」，則它位於凸多邊形內部。

如果您有一個凹多邊形，那麼您可以將您的凹多邊形定義爲一組凸多邊形。如果點在任何這些凸多邊形內部，那麼它位於凹多邊形內部。

如果您有兩個以上的尺寸，那麼您必須首先檢查點是否在多邊形所在的平面內。如果是的話，那麼你必須按照上面的描述進行分析。如果它不在同一平面內，那麼它不在多邊形內。

來源

2015-09-27 15:28:59

能否請您進一步解釋？我仍然投射光線來做到這一點？凸多邊形的 – bhounter

每個邊界是保持邊界線的有限長度的子集。如果該線嚴格位於多邊形的任意一點和您檢查的點之間，則該點位於多邊形之外。如果沒有邊框，其骨幹線爲嚴格多邊形的任意點，並正在分析的點之間，則該點是凸多邊形內部。如果你的多邊形是凹的，你需要把它分成凸多邊形，這樣你的任務就可以減少到幾個相似但更簡單的任務。 –

在這個pnpoly算法中包含邊緣

回答

相關問題