다각형 교차점과 봉쇄 판별

Question

단순한 (구멍이없고 자기 교차점이없는) 다각형 집합이 있고 서로 교차하지 않는지 확인해야합니다 (하나는 완전히 다른 것으로 포함될 수 있지만 괜찮습니다).). 하나의 폴리곤 대 다른 폴리곤의 정점 당 체크 만하면됩니다.

또한 어떤 폴리곤에 주어진 다각형이 포함되어 있는지를 나타내는 관계 집합 인 포함 트리를 결정해야합니다. 다각형이 다른 어떤 것도 교차 할 수 없기 때문에 포함 된 다각형에는 고유 한 컨테이너가 있습니다. "다음 큰"것. 즉, A에 B가 C를 포함하고 A가 B의 부모이고 B가 C의 부모라면 A가 C의 부모라고 생각하지 않습니다.

질문 : 어떻게 효율적으로 봉쇄 관계를 결정하고 비 교차 기준을 확인 하는가? 아마도 하나의 질문으로 생각해 봅니다. 아마도 결합 된 알고리즘이 각 문제를 개별적으로 해결하는 것보다 효율적이기 때문입니다. 알고리즘은 꼭지점 목록에 의해 주어진 다각형 목록을 입력으로 받아 들여야합니다. 폴리곤이 다른 폴리곤과 교차하지 않는 경우 및 B = true 인 경우 폴리곤 P가 자식 C의 부모 인 쌍 (P, C) 목록을 나타내는 부울 B를 생성해야합니다.

이것은 아닙니다. 숙제. 이것은 내가하고있는 취미 프로젝트를위한 것입니다.

Answer 1

먼저 봉쇄를 테스트하기위한 알고리즘이 교차점을 올바르게 테스트하지 않습니다. 이 같은 두 개의 직사각형 상상해

+--+ 
+--+--+--+ 
| | | | 
+--+--+--+ 
    +--+ 

정점 것이다 (1,2) (1,3) (4,2) (4,3) 및 (2,1) (3,1) (2 , 4) (3,4) - 어떤 정점도 어떤 다각형 안에도 없지만 실제로는 다각형이 교차합니다.

이러한 교차점을 테스트하려면 어떤 다각형 '에지가과 교차하는지 여부를 결정해야합니다. 목적에 따라 가장자리가 교차하지만 한 폴리곤이 다른 폴리곤 안에 포함되어 있지 않으면 허용되지 않는 방식으로 겹치는 것을 알 수 있습니다.

포함 트리를 결정하는 한 가지 방법은 영역별로 가장 작은 것에서 가장 큰 것부터 다각형을 정렬하는 것입니다. 폴리곤이 포함되지 않고 겹치지 않는다면 트리에있는 모든 폴리곤의 부모가 목록에있는 폴리곤을 포함하는 첫 번째 폴리곤이됩니다.

편집 : 오, 또한 빠른 경계 상자 또는 경계 서클 오버랩 루틴을 작성하고이를 사용하여 모든 선 교차 및 정점 포함 테스트를 수행하지 않아도됩니다. 그래도 여전히 빠르지 않다면 쿼드 또는 BSP 트리를 만들고 싶을 것입니다. 그것은 상당히 복잡하지만 교차 검사를 완전히 제거 할 것입니다.

Answer 2

O(n*log(n))에서 다각형이 교차하지 않는지 확인하려면 Shamos-Hoey algorithm을 적용하면됩니다. Shamos-Hoey 알고리즘이 반환하는 것에 따라 다각형 P _i에 다각형 P _j이 포함되어 있고 any vertex from P_j is inside P_i 인 경우 두 개의 다각형에 대해 O(n)이 수행됩니다.

Answer 3

코드의 경우 gpc을 참조하십시오.

Answer 4

교차로를 테스트하려면 내 프리웨어 클리퍼 라이브러리 ( http://sourceforge.net/projects/polyclipping/)를 사용할 수 있습니다.

봉쇄를 테스트하려면 먼저 위와 같이 교차로를 제외하십시오. 그런 다음 Clipper를 사용하여 모든 다각형 Clipper.AddPolygon()을 다시 추가합니다.그런 다음 폴리곤에 대해 Union (부울 OR) 연산을 수행하십시오 - Clipper.Execute (ctUnion, solution). Clipper.ForceAlternateOrientation 속성이 true 인 경우 Clipper는 솔루션 바깥 쪽 다각형에서 시계 방향으로 반환하고 다각형 (구멍)은 시계 반대 방향으로 포함합니다. 그런 다음 폴리곤 방향을 테스트하고 다른 시계 방향 폴리곤에 대해 반 시계 방향 폴리곤의 한 정점에서 PointInPolygon을 적용하는 간단한 문제 여야합니다.