두 개의 다각형 교차점 찾기

Question

두 개의 볼록 다각형의 경우 교차점 내부의 점을 찾아야합니다. 교차점의 모서리와 정점은 계산되지 않습니다. 포인트가 교차점의 가장자리에 상대적 일 필요는 없지만 중간의 어딘가에 위치해야한다는 요구 사항이 없습니다.

충돌 감지의 경우 SAP를 사용합니다. SAP에 계산을 통합 할 수 있다면 실행 속도가 빨라야 좋을 것입니다. 다각형은 각각 몇 개의 꼭지점을 가지며 모양은 매우 단순합니다.

Answer 1

Sweep Line 접근 방식을 사용하여 원하는 것을 할 수 있으며 충분히 빠릅니다.

두 폴리곤의 정점을 x 좌표로 정렬 한 다음 두 개의 교차 세그먼트 (첫 번째 다각형과 두 번째 다각형 중 하나)를 찾을 때까지 세로선을 왼쪽에서 오른쪽으로 스윕합니다. 그런 다음 이들 세그먼트의 교차점에서 내부 점을 선택하고 중지하십시오.