델라우나이 삼각측량

수학 및 계산 기하학에서 일반 위치의 이산형 점의 주어진 집합 P에 대한 델라우나이 삼각측량(Delaunay 삼각측량이라고도 함)은 DT(P)의 어떤 삼각형 원곡선 안에 P의 점이 없는 삼각형 DT(P)이다. 삼각형 삼각형은 삼각형 안에 있는 삼각형의 모든 각도의 최소 각도를 최대화한다. 삼각형은 작은 삼각형을 피하는 경향이 있다. 이 삼각측량은 1934년부터 이 주제에 대한 그의 연구를 위해 보리스 들로네이(Boris Delaunay)의 이름을 따서 명명되었다.^[1]

같은 선의 점 집합에 대해서는 델라우나이 삼각측정이 없다(이 경우 삼각측량 개념은 퇴보한다). 동일한 원의 4개 이상의 점(예: 사각형의 꼭지점)에 대해 델라우나이 삼각측량은 고유하지 않다. 쿼드랑글을 두 개의 삼각형으로 분할하는 두 개의 가능한 삼각측량은 각각 "델라우나이 조건(Delaunay 조건)"을 만족한다. 즉, 모든 삼각형의 원주에 빈 내부가 있어야 한다는 요건을 충족한다.

한정된 구를 고려함으로써 델라우나이 삼각측량 개념은 3차원 이상까지 확장된다. 유클리드 거리 이외의 지표에 일반화가 가능하다. 그러나 이러한 경우 델라나이 삼각측량은 존재하거나 고유하다고 보장되지 않는다.

보로노이 다이어그램과의 관계

일반 위치에서 이산점 집합 P의 델라우나이 삼각측량은 P에 대한 보로노이 도표의 이중 그래프에 해당한다. 델라우나이 삼각형의 원곡선은 보로노이 다이어그램의 정점이다. 2D 사례에서 보로노이 정점은 가장자리를 통해 연결되며, 이는 델라우나이 삼각형의 인접 관계에서 도출될 수 있다. 두 삼각형이 델라오나이 삼각측량에서 하나의 가장자리를 공유하는 경우, 그들의 원곡선은 보로노이 테셀레이션에서 가장자리와 연결되어야 한다.

이러한 관계가 유지되지 않거나 모호한 특수 사례에는 다음과 같은 경우가 포함된다.

• 원주가 무한 반지름인 세 개 이상의 시준점.
• 삼각형이 모호하고 모든 원곡선이 사소한 정도로 동일한 완벽한 원에 있는 4개 이상의 점.
• 무한대로 가는 보로노이 다이어그램의 가장자리는 유한 집합 P의 경우 이 관계에 의해 정의되지 않는다. Delaunay 삼각측정이 Bowyer-Watson 알고리즘을 사용하여 계산되는 경우, "슈퍼" 삼각형과 공통된 정점을 갖는 삼각형의 원곡선을 무시해야 한다. 무한대로 가는 가장자리는 원곡선에서 시작하며 유지되는 삼각형과 무시되는 삼각형 사이의 공통 가장자리와 수직이다.

d차원 딜라우나이

(d-차원) 유클리드 공간에서 점의 P 집합에 대해 델라우나이 삼각측량은 DT(P)에서 D-simplex의 원주-하이퍼스피어 안에 P의 점이 없는 삼각측량 DT(P)이다. P가 일반적인 위치의 점 집합인 경우 P에 대한 독특한 델로나이 삼각측정이 존재한다고 알려져^[1] 있는데, 즉 P의 아핀 선체는 d차원이고 내부가 P와 교차하지 않는 공의 경계에는 P의 d + 2점 집합이 없다.

d차원 유클리드 공간에서 점 집합의 델라우나이 삼각측량을 찾는 문제는 (d + 1)차원 공간에서 점 집합의 볼록한 선체를 찾는 문제로 전환될 수 있다. 이는 각 점 p에 p 와 동일한 추가 좌표를 부여하여 이를 초-파라볼로이드(이를 "리프팅"이라고 한다), 볼록 선체의 하단(상단 끝 캡이 원점에서 위로 향하며 폐기해야 함)을 취하고 마지막 좌표를 삭제하여 d-차원 공간에 다시 매핑함으로써 수행될 수 있다. 볼록한 선체가 독특하기 때문에 볼록한 선체의 모든 면이 단순하다고 가정하는 삼각 측량도 그러하다. 비물질적 파장은 원래 점의 d + 2가 동일한 d-하이퍼스페어에 놓여 있을 때만 발생한다. 즉, 점들이 일반 위치에 있지 않은 경우.^[2]

특성.

n을 점의 수로 하고 d 치수의 수로 하자.

• 삼각측량에서 모든 단순함의 결합은 점의 볼록한 선이다.
• Delaunay 삼각측량에는 O(n^{⌈d / 2⌉}) 단순화가 포함되어 있다.^[3]
• 평면(d = 2)에서 볼록한 선체에 b 정점이 있는 경우 점의 삼각형은 최대 2n - 2 b 삼각망과 외부 표면 1개를 더한다( 오일러 특성 참조).
• 평면에서 일정한 강도를 갖는 포아송 공정에 따라 점이 분포하는 경우 각 꼭지점에는 평균 6개의 주변 삼각형이 있다. 일반적으로 d차원에서 동일한 공정의 경우 평균 이웃 수는 d에만 의존하는 상수다.^[4]
• 이 평면에서는 딜라우나이 삼각측정이 최소 각도를 최대화한다. 점의 다른 삼각측정에 비해 델라나이 삼각측량에서 가장 작은 각도는 적어도 다른 어떤 각도에서 가장 작은 각도만큼 크다. 그러나 딜라우나이 삼각측정이 반드시 최대 각도를 최소화하는 것은 아니다.^[5] 딜라우나이 삼각측량도 반드시 가장자리 길이를 최소화하는 것은 아니다.
• Delaunay 삼각형을 둘러싸는 원은 내부에 다른 입력 지점을 포함하지 않는다.
• 입력 지점의 두 지점을 통과하는 원이 내부에 다른 입력 지점을 포함하지 않는 경우, 두 점을 연결하는 세그먼트는 주어진 점의 델라우나이 삼각측정의 가장자리가 된다.
• d차원 공간에서 점 집합의 델라우나이 삼각형의 각 삼각형은 점들이 (d + 1)차원 파라볼로이드에 투영되는 볼록한 선체의 한 면에 해당한다.
• 가장 가까운 이웃 그래프는 들로나이 삼각측량의 하위 그래프이기 때문에 어느 점 p에 가장 가까운 이웃 b는 들로나이 삼각측량에서 가장 가까운 이웃 bp에 있다.
• Delaunay 삼각측량은 기하학적 스패너다. 평면(d = 2)에서 델라우나이 가장자리를 따라 두 꼭지점 사이의 최단 경로는 이들 사이의 유클리드 거리의 1.998배 이하인 것으로 알려져 있다.^[6]

Visual Delaunay 정의: 플립

위의 속성에서 중요한 특징이 나타난다. 공통의 가장자리 BD(그림 참조)를 가진 두 삼각형 ABD와 BCD를 보면, 각도 α와 α의 합이 180° 이하일 경우 삼각형들이 델로나이 조건을 충족한다.

이것은 플립 기술을 사용할 수 있기 때문에 중요한 재산이다. 두 삼각형이 Delaunay 조건을 만족하지 않는 경우 공통 에지 AC에 대한 공통 에지 BD를 전환하면 Delaunay 조건을 만족하는 두 개의 삼각형이 생성된다.

• 

  이 삼각측량은 델라우나이 조건(α와 α의 합이 180°보다 크다)을 충족하지 못한다.

• 

  이 한 쌍의 삼각형은 델라우나이 조건을 만족시키지 못한다(원주형의 내부 안에 점이 있다).

• 

  공통 가장자리를 플립하면 네 점에 대해 유효한 딜라우나이 삼각측정이 생성된다.

이 작업을 플립이라고 하며, 3차원 이상까지 일반화할 수 있다.^[7]

알고리즘

Delaunay 삼각측량을 계산하는 많은 알고리즘은 삼각형의 원주 내에 점이 있을 때를 감지하기 위한 빠른 작동과 삼각망과 가장자리를 저장하기 위한 효율적인 데이터 구조에 의존한다. 두 가지 차원에서 D 지점이 A, B, C의 원주에 있는지 탐지하는 한 가지 방법은 다음과 같은 결정 요소를 평가하는 것이다.^[8]

${\displaystyle {\regated}>{\reason{vmatrix}A_{x}&A_{y}&A_{x}^{2}+A_{y}^{2}&1\\B_{x}&B_{y}&B_{x}^{2}+B_{y}^{2}&1\\C_{x}&C_{y}&C_{x}^{2}+C_{y}^{2}&1\\D_{x}&D_{y}&D_{x}^{2}+D_{y}^{2}&1\end{vmatrix}}\\[8pt]={}&{\begin{vmatrix}A_{x}-D_{x}&A_{y}-D_{y}&(A_{x}^{2}-D_{x}^{2}+(A_{y}^{y}^{2}-D_{y}^{2})\\B_{x}-D_{x}&B_{y}-D_{y}^{2}-D_{x}^{x}^{2}+(B_{y}^{2}-D_{y}^{2})\\C_{x}-D_{x}&C_{y}-D_{y}-{y}^{2}-D_{x}^{2}+(C_{y}^{2}-D_{y}^{2}^{2})+(C_{y}^{2}-D_{y}^{2}}^\end{vmatriged}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}.$

A, B, C를 시계 반대 방향으로 정렬할 때, 이 결정 인자는 D가 원주 안에 있을 때만 양수다.

플립 알고리즘

위에서 언급했듯이 삼각형이 Delaunay가 아닌 경우, 우리는 삼각형의 가장자리 중 하나를 뒤집을 수 있다. 이것은 간단한 알고리즘으로 이어진다: 점의 삼각측량을 구성하고 삼각형이 Delaunay가 아닌 삼각형이 없을 때까지 가장자리를 뒤집는다. 불행하게도, 이것은 Ω(n²) 에지 플립을 필요로 할 수 있다.^[9] 이 알고리즘은 3차원 이상으로 일반화할 수 있지만, 기본 플립 그래프의 연결성으로 조건화되기 때문에 이러한 경우 수렴이 보장되지 않는다: 이 그래프는 2차원 점 집합에 대해 연결되지만 더 높은 차원에서는 분리될 수 있다.^[7]

증분형

Delaunay 삼각측량을 효율적으로 계산하는 가장 간단한 방법은 그래프의 영향을 받는 부분을 다시 배열하면서 한 번에 하나의 꼭지점을 반복적으로 추가하는 것이다. 정점 v가 추가되면 v가 포함된 삼각형을 세 개로 나눈 다음 플립 알고리즘을 적용한다. 순진하게도, 이것은 시간이 걸릴 것이다: 우리는 v가 들어 있는 삼각형을 찾기 위해 모든 삼각형을 뒤지고, 그리고 잠재적으로 모든 삼각형을 뒤집는다. 그러면 전체 런타임은 O(n²)이다.

정점을 임의의 순서로 삽입하면, 각 삽입물이 평균적으로 O(1) 삼각형만 뒤집힐 수 있지만 때로는 더 많이 뒤집힐 수 있다는 것이 (어느 정도 복잡한 증거로) 밝혀진다.^[10] 이는 여전히 포인트 위치 개선 시간을 남겨두고 있다. 우리는 분할과 플립의 이력을 저장할 수 있다: 각 삼각형은 그것을 대체한 두 세 개의 삼각형에 포인터를 저장한다. v가 들어 있는 삼각형을 찾기 위해 루트 삼각형에서 시작하여 아직 대체되지 않은 삼각형을 찾을 때까지 v가 들어 있는 삼각형을 가리키는 포인터를 따른다. 평균적으로, 이것은 또한 O(log n) 시간이 걸릴 것이다. 모든 정점에 걸쳐 이 작업은 O(n log n) 시간이 걸린다.^[11] 기법이 더 높은 차원(에델스브루너와 샤가^[12] 입증한 바와 같이)까지 확장되는 반면, 최종 델라나이 삼각측정이 작더라도 런타임은 차원에서 기하급수적일 수 있다.

Bowyer-Watson 알고리즘은 증분 구성을 위한 또 다른 접근방식을 제공한다. 그것은 새롭게 삽입된 꼭지점을 포함하는 델로나이 삼각형을 계산하기 위한 가장자리 플립의 대안을 제공한다.

불행히도 플립 기반 알고리즘은 일반적으로 병렬화하기가 어렵다. 일정 지점(예: 왜건 휠의 중심점)을 추가하면 최대 O(n) 연속 플립으로 이어질 수 있기 때문이다. Blelloch 외 연구진은 폴리 로가리듬 스팬과 실용적이고 고도로 병렬화된 립앤텐트에 기반한 증분 알고리즘의 또 다른 버전을 제안했다.^[13]

분열시켜 정복하다.

이차원의 삼각측정에 대한 분할 및 정복 알고리즘은 리와 샤히터가 개발하고 기바스와 스톨피가^[14][15] 개선했으며 이후 드와이어가 개선했다.^[16] 이 알고리즘에서 한 사람은 반복적으로 선을 그려 정점을 두 세트로 나눈다. Delaunay 삼각측량은 각 세트에 대해 계산된 다음, 두 세트가 분할선을 따라 병합된다. 몇 가지 교묘한 트릭을 사용하면 병합 연산은 시간 O(n)로 할 수 있으므로 총 실행 시간은 O(n log n)이다.^[17]

균일한 무작위 분포와 같은 특정 유형의 점 세트의 경우 분할선을 지능적으로 선택하여 최악의 성능을 유지하면서 예상 시간을 O(n 로그 n)로 줄일 수 있다.

d차원에서 삼각측량을 수행하기 위한 분열과 정복 패러다임은 "DeWall: 빠른 분열과 E에서의^d 델라나이 삼각측량 알고리즘을 정복"에서 P에 의해 제시된다. 시그노니, C. 몬타니,^[18] R. 스코피뇨

분할 정복 알고리즘은 가장 빠른 DT 생성 기법인 것으로 나타났다.^[19][20]

스윕홀

스위프홀^[21](Sweephull)은 방사상으로 전파되는 스위프홀(sweep-hull)과 플립 알고리즘을 사용하는 2D Delaunay 삼각측량용 하이브리드 기법이다. 스위프홀은 방사형으로 편향된 2D 지점 세트를 반복하고 볼록한 선체의 가시 부분에 삼각형을 연결함으로써 순차적으로 생성되며, 이를 통해 오버랩되지 않는 삼각측정이 가능하다. 점의 순서가 어떤 점도 삼각형 안에 들어가지 않을 것을 보증하는 한, 이런 방식으로 볼록한 선체를 만들 수 있다. 그러나 방사상 분류는 시작하기에 Delaunay가 높기 때문에 플립을 최소화해야 한다. 그리고 이것은 최종 반복 삼각형 뒤집기 스텝과 짝을 이룬다.

적용들

점 집합의 유클리드 최소 스패닝 트리는 동일한 점의 델라우나이 삼각측정의 서브셋이며,^[22] 이를 이용하여 효율적으로 계산할 수 있다.

지형이나 점 구름이 주어진 다른 물체를 모델링하는 경우, 델라나이 삼각측량은 모델에서 다각형으로 사용할 수 있는 멋진 삼각형 세트를 제공한다. 특히 델라우나이 삼각측량은 좁은 삼각형을 피한다(그들의 면적에 비해 원주가 크기 때문에). 삼각형 불규칙 네트워크를 참조하십시오.

DTFE(Delaunay tescelation field estimator)를 통해 점 샘플링의 밀도 또는 강도를 결정하는 데 Delaunay 삼각측량을 사용할 수 있다.

델로나이 삼각측량은 각도 보증과 빠른 삼각측량 알고리즘이 개발되었기 때문에 유한요소법, 물리학 시뮬레이션의 유한 볼륨법 등 공간 분산 솔버의 메쉬 생성에 자주 사용된다. 일반적으로 메싱될 도메인은 거친 단순화 콤플렉스로 지정된다. 메쉬가 수치적으로 안정되려면 예를 들어, Ruppert의 알고리즘을 사용하여 정제해야 한다.

유한요소법과 경계요소법 기법의 인기가 높아짐에 따라 자동매싱 알고리즘을 개선하려는 동기가 높아진다. 그러나 이러한 모든 알고리즘은 왜곡되고 심지어 사용할 수 없는 그리드 요소를 만들 수 있다. 다행히도, 기존의 메쉬를 가지고 그것의 품질을 향상시킬 수 있는 몇 가지 기술이 존재한다. 예를 들어 스무딩(메쉬 정교화라고도 함)은 노드가 요소 왜곡을 최소화하도록 재배치하는 방법 중 하나이다. 늘어난 격자 방식은 딜라우나이 기준을 충족하는 사이비 정규 메쉬를 1단계 솔루션으로 쉽고 빠르게 생성할 수 있다.

제한된 델로나이 삼각측량에서는 자동 주행 및 지형 측량에서 경로 계획에서 응용 프로그램이 발견된다. ^[23]

참고 항목

참조

외부 링크

• "Delaunay 삼각 측량" 울프램 수학월드. 2010년 4월 검색됨

소프트웨어

• CGAL의 Delaunay 삼각 측량, 계산 지오메트리 알고리즘 라이브러리:
  • 마리엣 이바인크 2D 삼각 측량 2010년 4월 검색됨
  • 파이온, 실베인; 틸라우드, 모니크 3D 삼각측량 2010년 4월 검색됨
  • 호르누스, 사무엘, 데빌러, 올리비에, 자민, 클레멘트, dD 삼각측량.
  • 허트, 수잔; 실, 마이클. 디디 볼록스 헐스와 들라우나이 삼각측량. 2010년 4월 검색됨
• "폴리2트리: 증분 제약 딜라우나이 삼각측량. 오픈 소스 C++ 구현. 2019년 4월 회수
• "Divide & Cuper Delaunay 삼각 측량 공사" 오픈 소스 C99 구현. 2019년 4월 회수