들로네 삼각분할 (Delaunay triangulation)
쉽게 풀면
흩어진 점들을 삼각형으로 이어 그물을 만드는 방법은 무수히 많은데, 들로네 삼각분할은 그중에서 삼각형이 최대한 정삼각형에 가까워지도록 고르는 방법입니다. 구체적으로는 어떤 삼각형의 외접원 안에 다른 점이 들어오지 않도록 만듭니다. 그 결과 길쭉한 삼각형이 줄어들어 계산이 안정적이 됩니다.
왜 중요한가
들로네 삼각분할은 불규칙삼각망을 생성하는 표준 알고리즘이므로, 점 형태의 표고 자료를 지형 표면으로 바꾸는 작업의 핵심입니다. 납작한 삼각형이 만드는 수치적 불안정을 피할 수 있어 보간과 경사 계산의 품질이 좋아집니다. 또한 티센다각형과 서로 쌍대 관계여서 한쪽을 만들면 다른 쪽을 바로 얻을 수 있다는 점도 실용적으로 중요합니다.
논문에서는 이렇게 쓰입니다
흩어진 점들을 안정적인 삼각형 그물로 이어 표면을 만든 다음, 이를 바탕으로 지형의 높낮이를 표현하는 모델을 산출했다는 뜻입니다.
조금 더 깊게 보면
들로네 삼각분할은 모든 삼각분할 가운데 최소각을 최대로 만든다는 성질을 가지며, 이 때문에 수치해석적으로 가장 바람직한 분할로 여겨집니다. 구성 알고리즘으로는 점을 하나씩 넣어 가는 증분법, 분할정복법, 쓸어내기법 등이 있고, 삼차원으로 확장하면 사면체 분할이 됩니다. 네 점 이상이 한 원 위에 놓이는 퇴화 상황에서는 분할이 유일하지 않으므로, 구현마다 다른 결과가 나올 수 있습니다.
주의할 점
티센다각형은 영역을 나누는 다각형이고 들로네 삼각분할은 점을 잇는 삼각형망이므로, 서로 쌍대이지만 결과물의 성격이 다릅니다. 또한 분할이 자동으로 지형의 능선이나 하천 같은 구조선을 따르지는 않으므로, 지형 표현에서는 구조선을 제약조건으로 넣는 처리가 필요합니다.