두 개의 볼록 다각형이 교차하는지 어떻게 결정합니까?
https://stackoverflow.com/questions/753140
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian문제
평면에 많은 볼록한 다각형, 아마도지도가 있다고 가정 해 봅시다. 이 다각형은 서로 부딪 치고 가장자리를 공유 할 수 있지만 겹칠 수는 없습니다.
두 개의 다각형이 있는지 테스트합니다 피 그리고 큐 오버랩, 먼저 각 모서리를 테스트 할 수 있습니다 피 가장자리와 교차하는지 확인하려면 큐. 교차로가 발견되면 나는 그것을 선언합니다 피 그리고 큐 교차. 교차하지 않으면 사례를 테스트해야합니다. 피 완전히 포함되어 있습니다 큐, 그 반대. 다음으로, 그 경우가 있습니다 피==큐. 마지막으로, 몇 개의 가장자리를 공유하는 경우가 있지만 전부는 아닙니다. (이 마지막 두 경우는 아마도 같은 일반적인 경우로 생각 될 수 있지만 중요하지 않을 수도 있습니다.)
두 줄 세그먼트가 교차하는 위치를 감지하는 알고리즘이 있습니다. 두 세그먼트가 공동선이라면 내 목적을 위해 교차하는 것으로 간주되지 않습니다.
케이스를 올바르게 열거 했습니까? 이러한 경우 테스트에 대한 제안이 있습니까?
교차로 인 새로운 볼록 다각형을 찾지 않으려 고 생각합니다. 교차로가 있는지 알고 싶습니다. 교차로를 찾기위한 잘 문서화 된 알고리즘이 많이 있지만 모든 노력을 겪을 필요는 없습니다.
해결책
당신은 사용할 수 있습니다 이 충돌 알고리즘:
두 개의 볼록 다각형이 교차하는지 여부를 결정할 수 있도록 (서로 닿는) 분리 축 정리를 사용할 수 있습니다. 본질적으로 :
- 두 개의 볼록 다각형이 교차하지 않으면 그들 사이에 전달되는 선이 있습니다.
- 그러한 선은 다각형 중 하나의 측면 중 하나가 그러한 선을 형성하는 경우에만 존재합니다.
첫 번째 진술은 쉽습니다. 다각형은 모두 볼록하기 때문에 한쪽에 하나의 다각형이 있고 다른쪽에는 교차하지 않는 한 다른쪽에는 선을 그릴 수 있습니다. 두 번째는 약간 덜 직관적입니다. 그림 1을보십시오. 다각형의 가장 가까운면이 서로 평행하지 않으면, 서로 가장 가까이있는 지점은 한 다각형의 모서리가 다른 다각형의 측면에 가장 가까워지는 지점입니다. 이면은 다각형 사이에 분리 축을 형성합니다. 측면이 평행하면 둘 다 축을 분리하고 있습니다.
그렇다면 이것은 다각형 A와 B가 교차하는지 여부를 구체적으로 결정하는 데 어떻게 도움이됩니까? 글쎄, 우리는 단지 각 다각형의 각 측면을 넘어서 분리 축을 형성하는지 확인합니다. 이를 위해 우리는 기본 벡터 수학을 사용하여 두 다각형의 모든 지점을 잠재적 분리 라인에 수직 인 선에 스쿼시 할 것입니다 (그림 2 참조). 이제 전체 문제는 편리하게 1 차원입니다. 우리는 각 다각형의 지점이 놓인 영역을 결정할 수 있으며,이 영역이 겹치지 않으면이 선이 분리 된 축입니다.
두 다각형에서 각 라인을 확인한 후 분리 축이 발견되지 않은 경우, 다각형이 교차하고 그에 대해 무언가를해야한다는 것이 입증되었습니다.
다른 팁
다각형이 항상 볼록한 경우 먼저 다각형의 중심에서 중앙으로 그려진 선의 각도를 계산하십시오. 그런 다음 다른 다각형에서 180도 떨어진 다각형의 절반에서 가장자리 세그먼트를 테스트 할 필요가 없습니다.
가장자리를 제거하려면 왼쪽의 다각형부터 시작하십시오. 이전 총알의 선 세그먼트에 수직 인 다각형 중심에서 선 세그먼트를 가져 와서 다각형의 양쪽에 닿으십시오. 정점 P1 및 P2와 함께이 줄 세그먼트 P를 호출하십시오. 그런 다음 x 좌표가 p1.x 및 p2.x 미만인 경우 모든 정점의 경우 정점이 "안전한 버킷"으로 들어갈 수 있습니다.
그렇지 않은 경우 라인의 "안전한"측면에 있는지 확인해야합니다 (Y 좌표도 확인하십시오).
-다각형의 라인 세그먼트에 "안전한 버킷"에 모든 정점이있는 경우 무시할 수 있습니다.
-두 번째 다각형에 대해 "오른쪽 지향적"이되도록 극성을 반대하십시오.
다각형이 전혀 교차하지 않는 경우 (완전히 외부 또는 완전히 내부), 부분 교차 형태가있는 경우 (중첩이있는 경우 항상 교차)가있는 경우 테스트 사례가 작동해야합니다. .
테스트를 위해서는 모든 잠재적 조합을 테스트해야합니다. 내가 보는 것에서 위에 누락 된 것은 단일 모서리이지만 하나는 다른 하나에 포함되어 있습니다. 또한 예방 조치로 Tri-> 많은 측면에서 더 복잡한 폴리 모양에 대한 테스트를 추가 할 것입니다.
또한, 당신이 폴리를 완전히 둘러싸는 U 자형 폴리를 가지고 있다면, 겹치지 않았다면, 당신의 케이스가 그것을 처리 할 것이라고 생각하지만, 나는 그것을 점검으로 추가 할 것입니다.
Altcognito는 이미 당신에게 해결책을 주었기 때문에 나는 단지 지적 할 것입니다. 계산 형상에 관한 훌륭한 책 그것은 당신에게 관심을 가질 수 있습니다.
아이디어는 다음과 같습니다.
각 다각형의 중심점을 찾으십시오
각 다각형의 두 지점을 다른 다각형의 중심 지점에 가장 가까운 것을 찾으십시오. 그들은 볼록한 다각형의 인접한 지점이 될 것입니다. 이들은 각 다각형의 가장 가까운 가장자리를 정의하고 포인트를 {a, b} 및 {y, z}라고 부릅니다.
라인 AB와 Yz의 교차점을 찾으십시오. 라인 세그먼트가 교차하는 경우 (AB의 교차로가 A와 B 사이에 있습니다) 다각형이 교차합니다. AB와 XY가 평행 한 경우이 조건을 무시하면 다음 단계가 문제를 가두게됩니다.
확인해야 할 경우가 하나 더 있습니다. 이는 AB와 XY가 완전히 지나가고 실제로 교차하지 않을 정도로 다각형이 크게 교차 할 때입니다. 이 경우를 가두려면 AB 및 XY의 수직 거리를 각 다각형 중심 지점으로 계산하십시오. 어느 중 어느 쪽이든 반대쪽 다각형의 선분에 더 가깝다면 다각형이 크게 겹치게됩니다.
볼록한 다각형 사이의 교차 및 / 또는 격리를 감지하는 몇 가지 방법이 있습니다. 그것은 모두 알고리즘을 얼마나 효율적으로 원하는지에 달려 있습니다. R 및 B 정점이있는 두 개의 볼록 다각형 R과 B를 고려하십시오.
