GC 친화적 인 볼록 클리핑 (합집합 및 차이) 알고리즘

Question

다른 볼록 다각형을 기반으로 볼록 다각형을 자르는 알고리즘을 찾고 있습니다. 파괴적인 지형 (diff)과 게임의 2D지도에서 지형 (노조)을 만드는 것입니다.

알고리즘은 가비지 수집기와 호환되어야하며 부울 연산은 필요한 유일한 Union은 & 차이입니다.

나는 약간의 연구를했는데 일부 github 프로젝트가 있지만, 모두 약간의 쓰레기를 생산합니다.

https://github.com/w8r/GreinerHormann

https://github.com/tmpvar/2d-polygon-boolean

나는 최선의 해결책이 중 하나를 배우고 그것을 내 방식대로 다시 만드는 것 같아요. 하지만 내 요구에 맞는 것을 들어 본 적이 있습니까?

감사합니다.

Answer 1

이 문제는 두 개의 하위

1. 두 윤곽

2. 합류하는 MU 정점에 가입

   사이의 교차점을 찾을 수를 포함한다.

1. 볼록성을 활용할 수 있습니다. 두 다각형을 두 개의 모노톤 체인으로 볼 수 있습니다. twopolygons의 사슬을 동시에 움직일 때, x를 늘림으로써 가로 좌표가 가로 좌표 사이에서 교차 할 때 교차점이 감지됩니다.

2. 공용체 또는 차이점은 모든 인터셉션 포인트에서 한 폴리곤과 다른 폴리곤간에 번갈아 나오는 윤곽의 부분으로 구성됩니다.

차이점의 경우 몇 개의 연결이 끊긴 부분이있을 수 있습니다.

나는 모든 (그러나 출력 다각형)에서 모든 할당/해제하지 않고이를 구현 할 수있는 것 같아요.