지형 삼각 측량 알고리즘

Question

지형은 3D-space에 큰 점 집합으로 표시됩니다. 그것을 삼각 화하는 가장 좋은 방법은 무엇입니까?

2D-space에 모든 점을 투영 할 수 있습니다. O(n * log(n))의 Delaunay 삼각 측량을 수행하고 이전의 높이로 되돌립니다. 그러나 충분히 좋은가? 몇 가지 특별한 경우에 Delounay 삼각 측량에 대해 O(n * log(log(n))라고 들었습니다. 내 경우에 가능할까요? 아니면 근사 알고리즘을 사용해야합니까?

Answer 1

사실 당신은 숙제를 마쳤습니다. Delaunay 삼각 측량은 문제에 대한 아주 좋은 해결책입니다.

Answer 2

2D에서의 투영 및 델 로니 삼각 측량은 확실히 좋은 모양의 삼각형을 생성하는 좋은 솔루션입니다. 지형의 경우 특정 가장자리를 적용해야 할 수도 있으므로 제한된 Delaunay 삼각 측량을 찾으십시오.

런타임과 관련하여 : 실제 데이터의 경우 선형 runtime으로 가정 할 수 있습니다. 성능이 중요한 경우 입력 데이터가 퇴화되지 않는지 확인하십시오. 스캔 장치는 종종 그리드의 포인트를 반환합니다. 약간의 소음을 추가하여 상황을 개선 할 수 있습니다.