구멍이없는 폴리곤 유니온

Question

메신저는 (폴리곤 유니온은 쉬운 조작이 아니라는 것을 알고 있지만, 아마도 누군가가 상대방과 쉽게 올바른 방향으로 나를 가리킬 수 있습니다.) 알고리즘은 두 개의 교차하는 폴리곤을 병합하는 알고리즘입니다. 다각형은 구멍이없는 오목 일 수 있으며 출력 다각형도 구멍이 없어야합니다. 다각형은 시계 반대 방향으로 표현됩니다. 내 말은 그림에 나타납니다. 폴리곤 조합에 구멍이 있어도 볼 수 있듯이 출력에는 필요하지 않습니다. 입력 다각형은 구멍없이 확실합니다. 나는 구멍이 없다면 더 쉽게해야한다고 생각하지만 여전히 아이디어는 없다.

Answer 1

1. 다른 다각형 내부 거짓말 다각형의 모든 꼭지점 제거 명확 : http://paulbourke.net/geometry/insidepoly/
2. 을 유니온 다각형에있을 수있는 시작점을 선택하십시오 (극단 중 하나가 작동 함)
3. 다각형의 가장자리를 반 시계 방향으로 따라 가면서 추적합니다. 이것들은 노조의 포인트입니다. 교차로에 충돌 할 때까지 추적합니다 (가장자리가 다른 다각형의 둘 이상의 가장자리와 교차 할 수 있습니다).
4. 첫 번째 교차점을 찾습니다 (두 개 이상의 교차점이있는 경우). 이것은 귀하의 연합에있는 요점입니다.
5. 다른 다각형으로 3 단계로 이동하십시오. 다음 지점은 이전 가장자리와 가장 큰 각도를 만드는 지점이어야합니다.

Answer 2

당신은 다음과 같이 진행할 수 :

첫 번째 점의 당신의 세트에 다각형의 교차의 모든 포인트를 추가합니다.

그러면 graham scan algorithm과 같이 진행 하겠지만 한 가지 제약이 더 있습니다.

이전 선과 가장 높은 각도를 이루는 점을 선택하는 대신 (그레이엄 스캔을보고 (*) 무엇을 의미하는지 확인하십시오.) 이전 각도 중 하나의 일부였던 가장 높은 각도를 가진 점을 선택하십시오 다각형.

모양을 묘사 할 envellope (볼록하지 않음)이 표시됩니다.

참고 :

그것은 당신의 포인트 볼록 선체를 찾는 비슷.

예를 들어 graham scan algorithm은 O (N * ln (N))에서 점 집합의 볼록 선체를 찾는 데 도움이됩니다. 여기서 N은 점의 수입니다.

볼록 선체 알고리즘을 찾아보고 몇 가지 아이디어를 찾을 수 있습니다.

희망이 있습니다.

remarques :

(*) 발 위키 :

가

알고리즘이 첫 번째 단계는 최저 가 y 좌표를 가진 점을 찾아내는 것이다. 가장 낮은 y 좌표가 집합의 두 개 이상의 점 에 존재하면 후보 중 가장 낮은 x 좌표를 갖는 점을 선택해야합니다. 이 단계는 O (n), 을 필요로합니다. 여기서 n은 문제의 점수입니다.

다음으로 점의 집합은 x 축을 따라 점 P와 점을 이루는 순서대로 정렬해야합니다. 범용 정렬 알고리즘이 이에 적합합니다 (예 : 힙 배열 ( 은 O (n log n) 임). 계산 속도를 높이려면 x 축의 을 사용하여 실제 각도를 계산하는 데 이 필요하지 않습니다. 대신이 각도의 코사인을 계산하면 충분합니다. 은 도메인 (첫 번째 단계로 인해 0 ~ 180도)에서 단조 감소 함수이며 간단한 산술로 계산 된 일 수 있습니다.

볼록 선체 알고리즘에서 앞면과 가장 큰 각도를 만드는 각도 점을 선택했습니다.

이전 다각형과 "붙이려면"이전에 존재했던면을 선택해야한다는 제한 조건을 추가하기 만하면됩니다.

당신은 내가 해요 각도를 180 ° 미만의

희망을 haveing의 제약 이륙

Answer 3

나는 완전한 대답이 없지만 비슷한 문제에 착수 할 예정입니다. 상당히 중요한 두 단계가 있다고 생각합니다. 첫 번째는 바깥 쪽 가장자리에있는 다각형 위에 점을 찾는 것입니다. 두 번째는 모든 꼭지점에 대한 경계 상자 목록을 만들고이 중 겹치는 부분을 확인하는 것입니다. 즉, 꼭지점을 반복 할 때 모든 것에 대한 테스트를 수행 할 필요가없고, 교차 할 가능성이있는 경우에만 (경계 상자 문제가 가벼운 경우) 알고있는 것입니다.

이제 외부 점이 있으므로 교차점을 감지 할 때까지 연결된 점을 반복 할 수 있습니다. 어느 쪽이 안쪽이고 어느 쪽이 바깥 쪽인지 알고 있으면 (이것을 알기 위해 첫 번째 꼭지점에서 어떤 작업을해야 할 수도 있습니다), 교차로에서 어떤 방향으로 갈 것인지 알 것입니다. 그렇다면 단지 다각형을 바꾸는 문제 일뿐입니다.

이 구멍을 유지하기를 원한다면 좀 더 흥미로워집니다.이 경우, 나는 모든 교차하는 경계 상자를 모두 다 써 버렸을 것입니다. 다각형이 전혀 교차하지 않을 경우 어떻게해야 하는지도 지정하지 않았습니다. 하지만 그 중 하나를 남겨 둘 것입니다 (잠재적으로 하나의 다각형을 예상하는 경우 문제가 될 수 있음) 또는 오류를 반환합니다.