다각형에서의 연산 - 발견 된 정점을 정렬하는 방법

Question

2 개의 오목한 폴리곤을 점의 두 벡터로 나타낸 입력에 배치했습니다. 노동 조합, 교차점 및 차이점에 대해 다각형 작업을하고 싶습니다. 나는이 다각형들 사이에 교차점을 발견하고이를 각 다각형의 올바른 위치에 삽입했습니다. 그런 다음 위치에 대한 정보를 제공합니다 (내부 - 다른 다각형 내부, 내부 - 다른 다각형 외부, 교차점 - 폴리곤의 두 모서리가 교차). 각 꼭지점에 대한 정보를 제공합니다. 이제 어떤 점이이 폴리곤 (외곽 및 교차점) 등의 결합을 만드는 지 알고 있지만 올바른 순서로 정렬하는 방법을 알아야합니다. 교차 연산의 경우 교차점 결과가 둘 이상의 다각형이 될 수 있으므로 이러한 정렬 된 점을 올바른 수의 집합으로 나누어야합니다.

저는 C++을 사용하고 있지만 반드시 코드가 필요하지는 않습니다. 이러한 최종 다각형 점을 정렬하는 방법 만 필요합니다. 그리고 이미 내 자신의 기능을 가지고 있기 때문에 이러한 작업에 라이브러리를 사용하고 싶지는 않습니다.

이 질문은 How to intersect two polygons?과 그 외 일부를 살펴 보았지만 최종 정렬을 해결하지 못했습니다. 나는 또한이 기사 http://www.gvu.gatech.edu/~jarek/graphics/papers/04PolygonBooleansMargalit.pdf을 읽었지만 아마 얻지 못할 것이다.

어떤 도움

주시면 감사하겠습니다.

Answer 1

당신이 내 의견에서 내 모든 권고에 따라 경우

이

• 는 교회법 및 접촉 지점 사이에 구별을
• 두 다각형의 교차점의 2 당량 사이의 링크를 유지

유니온의 솔루션은 다음과 같습니다.

1. 는
2. 두 다각형의 포인트 다른 방향 (세트 중 하나는, 시계 방향으로 반 시계 방향의 다른 하나)
에 정렬되어 있는지 확인에만 외부, 만지고 교차 사항을 고려
3. 두 다각형 중 임의의 지점에서 임의의 지점을 시작하십시오.
4. 두 폴리곤 중 하나의 모든 정점에 대해 방문한 경우 계속 유지
5. 교차점이 생길 때마다 교차점에 해당하는 직후에 다른 다각형의 다음 지점을 따라 계속 이동합니다.
6. 시작 지점으로 돌아 오면 두 폴리곤 조인의 구성 요소 중 하나가 닫힙니다. 모든 꼭지점을 가로 지르지 않은 경우 방문하지 않은 모든 꼭지점에서 전체를 반복합니다.
7. 결국 발견 한 모든 다각형의 면적을 계산하십시오. 가장 큰 지역은 진정한 노동 조합이 될 것입니다. 나머지는 노조에 구멍이 될 것입니다.

에 대한 해결책은 될 것 가입 :

이

1. 은 내부와 교차하는 지점
2. 두 다각형의 점 같은 방향으로 정렬되어 있는지 확인을 고려
3. 두 개의 다각형 중 임의의 지점에서 임의로 시작합니다.
4. 두 폴리곤 중 하나의 모든 정점에 대해 방문한 경우 계속 유지
5. 교차점이 생길 때마다 교차점에 해당하는 직후에 다른 다각형의 다음 지점을 따라 계속 이동합니다.
6. 시작 지점으로 돌아 오면 두 폴리곤 조인의 구성 요소 중 하나가 닫힙니다. 모든 꼭지점을 가로 지르지 않은 경우 방문하지 않은 모든 꼭지점에서 전체를 반복합니다.

편집 : 이미 언급 한 바와 같이, 내가 다각형 방향으로 내 접근을 느끼고 하나님을 개정 할 필요가있다. The Vatti clipping algorithm

EDIT2One more article 자르기와 알고리즘을 설명 : 웹을 통해 검색 할 때 그러나, 나는 당신을 위해 일을 할 수있는 알고리즘에 대한 설명을 발견했다.