다각형 교차를위한 간단한 알고리즘

다각형 교차를위한 간단한 알고리즘

---

다각형 교차 / 잘림을 계산하기위한 매우 간단한 알고리즘을 찾고 있습니다. 즉, 주어진 다각형입니다 P, Q나는 다각형 찾고자 T에 포함되어 P및에서를 Q, 내가 원하는 T모든 가능한 다각형 사이에 최대로.

실행 시간은 신경 쓰지 않습니다 (매우 작은 다각형이 몇 개 있습니다). 또한 다각형 교차점 (즉, 점이 더 적지 만 다각형 교차점에 여전히 포함되어있는 다각형)의 근사치를 얻을 수 있습니다. ).

그러나 알고리즘이 간단하고 (더 저렴한 테스트) 바람직하게는 짧은 (더 적은 코드)이라는 것이 저에게 정말 중요합니다.

편집 : 교차점을 나타내는 다각형을 얻고 싶습니다. 두 다각형이 교차하는지 여부에 대한 질문에 부울 답변 만 필요하지는 않습니다.

---

나는 원래 포스터가 간단한 해결책을 찾고 있었다는 것을 이해하지만, 불행히도 실제로는 간단한 해결책이 없습니다.

그럼에도 불구하고 저는 최근에 모든 종류의 다각형 (자체 교차 다각형 포함)을 클리핑하는 오픈 소스 프리웨어 클리핑 라이브러리 (Delphi, C ++ 및 C #로 작성)를 만들었습니다. 이 라이브러리는 사용이 매우 간단합니다 : http://sourceforge.net/projects/polyclipping/ .

---

다각형 클리핑 알고리즘을 사용하여 두 다각형 사이의 교차점을 찾을 수 있습니다. 그러나 모든 에지 케이스를 고려하면 복잡한 알고리즘이되는 경향이 있습니다.

선호하는 검색 엔진을 사용하여 찾을 수있는 다각형 클리핑의 한 가지 구현은 Weiler-Atherton 입니다. Weiler-Atherton에 대한 wikipedia 기사

Alan Murta는 폴리곤 클리퍼 GPC를 완벽하게 구현했습니다 .

편집하다:

또 다른 접근 방식은 먼저 각 다각형을 처리하기 쉬운 삼각형 세트로 나누는 것입니다. Gary H. Meisters 의 Two-Ears Theorem 이 트릭을 수행합니다. McGill 의이 페이지는 삼각형 세분화를 잘 설명합니다.

---

C ++를 사용하고 알고리즘을 직접 생성하지 않으려면 Boost.Geometry 를 사용할 수 있습니다 . 위에서 언급 한 Weiler-Atherton 알고리즘의 개조 된 버전을 사용합니다.

---

다각형 표현을 제공하지 않았습니다. 그래서 나는 당신을 위해 하나를 선택하고 있습니다.

각 다각형을 하나의 큰 볼록 다각형으로 나타내고 큰 볼록 다각형에서 '빼야하는'작은 볼록 다각형 목록을 나타냅니다.

이제 해당 표현에 두 개의 다각형이 주어지면 교차점을 다음과 같이 계산할 수 있습니다.

큰 볼록 다각형의 교차점을 계산하여 교차점의 큰 다각형을 형성합니다. 그런 다음 둘 중 더 작은 모든 교차점을 '빼서'빼낸 다각형 목록을 얻습니다.

동일한 표현을 따르는 새로운 다각형을 얻습니다.

볼록 다각형 교차가 쉽기 때문에이 교차 찾기도 쉬울 것입니다.

이것은 효과가있는 것처럼 보이지만 정확성 / 시간 / 공간 복잡성에 대해 더 깊이 생각하지 않았습니다.

---

다음은 간단하고 어리석은 접근 방식입니다. 입력시 다각형을 비트 맵으로 이산화합니다. 교차하고 비트 맵을 함께. 출력 다각형을 생성하려면 비트 맵의 ​​들쭉날쭉 한 경계를 추적하고 다각형 근사화 알고리즘을 사용하여 들쭉날쭉 한 부분을 부드럽게합니다 . (링크가 가장 적합한 알고리즘을 제공하는지 기억이 나지 않습니다. Google의 첫 번째 히트작 일뿐입니다. 비트 맵 이미지를 벡터 표현으로 변환하는 도구 중 하나를 확인할 수 있습니다. 알고리즘을 다시 구현하지 않고도 호출 할 수 있습니다. ?)

가장 복잡한 부분은 경계선을 추적하는 것입니다.

그런데 90 년대 초반에 저는 직장에서 이런 문제에 직면했습니다. 나는 그것을 숨겼다 : 실수 좌표에서 작동하는 (완전히 다른) 알고리즘을 생각해 냈지만, 부동 소수점 (그리고 잡음이 많은 입력)의 현실에 직면하여 완전히 고칠 수없는 과다한 퇴화 사례에 부딪 치는 것처럼 보였다. . 아마도 인터넷의 도움으로 더 잘했을 것입니다!

---

다음은 구현하기 매우 간단하고 O (N ² ) 에서 실행되도록 만들 수있는 삼각 측량을 기반으로 한 접근 방식 입니다.

BTW, O (N ² )는이 문제에 최적입니다. 직각으로 교차하는 갈퀴 날 모양의 두 다각형을 상상해보십시오. 각각에는 가지 수에 비례하는 여러 세그먼트가 있습니다. 교차점의 다각형 수는 타인 수의 제곱에 비례합니다.

1. 먼저 각 다각형을 삼각 측량합니다.

2. P의 모든 삼각형을 Q의 모든 삼각형과 쌍으로 비교하여 교차점을 감지합니다. 교차하는 삼각형 쌍은 각각 P, Q 또는 교차점에있는 더 작은 삼각형으로 나눌 수 있습니다. (1 단계에서 사용한 것은 무엇이든 재사용 할 수 있습니다.) 교차점에있는 삼각형 만 유지하십시오.

3. 각 삼각형의 이웃을 쌍으로 비교하여 계산하고 인접 그래프를 만듭니다. 이 그래프에는 P와 Q의 교차점에있는 각 다각형에 대해 하나의 연결된 하위 그래프가 포함됩니다.

4. 이러한 각 하위 그래프에 대해 삼각형을 선택하고 가장자리까지 걸어 간 다음 가장자리 주변을 걸어 해당 출력 다각형을 경계하는 세그먼트를 생성합니다.

---

매우 간단한 해결책은 없지만 실제 알고리즘 의 주요 단계는 다음과 같습니다.

1. DO가 사용자 정의 다각형의 꼭지점과 모서리를위한 이중 연결리스트를. std::list노드에 대한 특수 작업을 위해 다음 및 이전 포인터 / 오프셋을 직접 바꿔야하기 때문에 사용 하지 않습니다. 이것이 간단한 코드를 가질 수있는 유일한 방법이며 좋은 성능을 제공합니다.
2. 각 모서리 쌍을 비교하여 교차점을 찾으십시오. 각 에지 쌍을 비교하면 O (N²) 시간이 주어 지지만 나중에 알고리즘을 O (N · logN)으로 개선하는 것은 쉽습니다. 일부 모서리 쌍 (예 : a → b 및 c → d)의 경우 교차점은 모서리 a → b의 매개 변수 (0에서 1)를 사용하여 찾습니다. tₐ = d₀ / (d₀-d₁) , 여기서 d₀은 (ca) × (ba)이고 d₁은 (da) × (ba)입니다. ×는 p × q = pₓ · qᵧ-pᵧ · qₓ와 같은 2D 외적입니다. tₐ를 찾은 후 교차점을 찾는 것은 세그먼트 a → b의 선형 보간 매개 변수로 사용합니다 : P = a + tₐ (ba)
3. 세그먼트가 교차하는 정점 (및 연결된 목록의 노드)을 추가하여 각 가장자리를 분할합니다.
4. 그런 다음 교차점 에서 노드를 교차 해야합니다 . 이것은 사용자 지정 이중 연결 목록을 수행하는 데 필요한 작업입니다. 다음 포인터 쌍을 바꾸고 그에 따라 이전 포인터를 업데이트 해야합니다 .

그런 다음 다각형 교차 해석 알고리즘의 원시 결과를 얻습니다. 일반적으로 각 영역의 권선 수에 따라 일부 영역을 선택하는 것이 좋습니다. 이에 대한 설명 은 다각형 감기 번호 를 검색 하십시오.

이 O (N²)에서 O (N · logN) 알고리즘을 만들려면 라인 스윕 알고리즘 내에서 수행하는 것을 제외하고는 정확히 동일한 작업을 수행해야합니다. Bentley Ottman 알고리즘을 찾습니다 . 내부 알고리즘은 동일하지만 루프 내부에서 비교할 에지 수가 줄어든다는 점만 다릅니다.

---

같은 문제에 대해 내가 일한 방식

1. 다각형을 선분으로 나누기
2. IntervalTrees또는 사용하여 교차 선 찾기LineSweepAlgo
3. GrahamScanAlgo인접한 정점이있는 닫힌 경로 찾기를 사용하여 닫힌 경로 찾기
4. 상호 참조 3. DinicAlgo해산을 위해

참고 : 내 시나리오는 다각형에 공통된 정점이 있다는 점을 고려할 때 달랐습니다. 그러나 이것이 도움이 될 수 있기를 바랍니다.

---

이것은 다각형에 따라 큰 근사치가 될 수 있지만 다음은 하나입니다.

• Compute the center of mass for each polygon.
• Compute the min or max or average distance from each point of the polygon to the center of mass.
• If C1C2 (where C1/2 is the center of the first/second polygon) >= D1 + D2 (where D1/2 is the distance you computed for first/second polygon) then the two polygons "intersect".

Though, this should be very efficient as any transformation to the polygon applies in the very same way to the center of mass and the center-node distances can be computed only once.

참고URL : https://stackoverflow.com/questions/2272179/a-simple-algorithm-for-polygon-intersection