점이 부분적으로 열린 다각형에 있는지 확인하십시오.

Question

점이 다각형인지 아닌지보고 싶습니다. 물론 내가 봤 거든이 질문이 일찍 대답하고 다음이 알고리즘을 발견하면 보았다 : http://www.ecse.rpi.edu/Homepages/wrf/Research/Short_Notes/pnpoly.html 다각형이 부분적으로 열려 있지 않으면이 잘 작동합니다. 예 :

A-E가 감지되었지만 B- 다각형의 열린 부분도 닫힌 것으로 간주됩니다. 이 예제 코드를 실행하면 당신은 내가 무슨 뜻인지 확인할 수 있습니다 :

#include <stdio.h> 

int pnpoly(int nvert, float *vertx, float *verty, float testx, float testy) 
{ 
    int i, j, c = 0; 
    for (i = 0, j = nvert-1; i < nvert; j = i++) { 
    if (((verty[i]>testy) != (verty[j]>testy)) && 
     (testx < (vertx[j]-vertx[i]) * (testy-verty[i])/(verty[j]-verty[i]) + vertx[i])) 
     c = !c; 
    } 
    return c; 
} 

int main(int argc, char *argv[]) 
{ 
     // 1 closed [A] 
     float x1[] = { 0, 1, 1, 0, 0 }; 
     float y1[] = { 0, 0, 1, 1, 0 }; 
     printf("1: %d (1 expected)\n", pnpoly(5, x1, y1, 0.8, 0.8)); 
     printf("1: %d (0 expected)\n", pnpoly(5, x1, y1, -0.8, -0.8)); 

     // 1 closed [B] with a partial open 
     // please note that the vertex between [0,-1] and [0,0] is missing 
     float x2[] = { 0, 1, 1, 0, 0, -1, -1, 0 }; 
     float y2[] = { 0, 0, 1, 1, 0, 0, -1, -1 }; 
     printf("2: %d (1 expected)\n", pnpoly(8, x2, y2, 0.8, 0.8)); 
     printf("2: %d (0 expected)\n", pnpoly(8, x2, y2, -0.8, -0.8)); // <- fails 

     // 2 closed [C/D/E] 
     float x3[] = { 0, 1, 1, 0, 0, -1, -1, 0, 0 }; 
     float y3[] = { 0, 0, 1, 1, 0, 0, -1, -1, 0 }; 
     printf("3: %d (1 expected)\n", pnpoly(9, x3, y3, 0.8, 0.8)); 
     printf("3: %d (1 expected)\n", pnpoly(9, x3, y3, -0.8, -0.8)); 

     return 0; 
} 

X2 /의 Y2 다각형은 부분적으로 개방 블록에 연결된 닫힌 블록으로 구성되어 있습니다. pnpoly 함수는 여전히 열려있는 블록의 "in"지점을 다각형으로 간주합니다.

내 질문은 지금 : 어떻게이 문제를 해결할 수 있습니까? 또는 나는 무엇인가 내려다보고 있냐?

미리 감사드립니다.

Answer 1

아마도 늦은 답변이지만, 어쨌든 기여하고 싶습니다.

이러한 알고리즘은 마지막 점을 첫 번째 점에 연결하기 때문에 폴리곤 배열 데이터에서 사전 처리해야합니다. 특히이 알고리즘의 설명에서 볼 수 있듯이 다각형을 처리하며 열린 영역은 다각형이 아니므로이 알고리즘으로 처리 할 수 ​​없습니다.

나는 다음과 같은 아이디어를 사용하여 다각형의 일부 전처리을 제안 : 하위 다각형으로 갈라, 그것은해야 다각형을 나타낼 수 점의 각 세트의 "

을 할 때마다 당신을 의 시작점을 찾으십시오.이 다각형을 저장하고이 지점에서 시작하여 새 점을 작성하고 에 도달 할 때까지 처리를 계속하십시오. 따라서 모든 하위 폴리곤 끝점이 으로 끝나지 않으므로 치료시 무시해야합니다. 따라서 submission 알고리즘에 itted. 이 사전 처리 방식을 사용하면 만 알고리즘 그의 지점을 종료 시작점과 동일 그 하위 다각형을 제출한다 "

는

월 그것은 당신이하는 데 도움이 -. 당신은 아직도 그것을 필요로하는 경우. ..