델로네 삼각분할
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.
1. 개요
델로네 삼각분할은 주어진 점 집합을 삼각형으로 분할하는 방법으로, 보로노이 다이어그램의 쌍대 그래프이다. 2차원 평면뿐만 아니라 임의의 차원 공간에서도 정의될 수 있으며, 모든 단순(simplex)들의 합집합은 입력 점들의 볼록 껍질이 된다. 평면 상의 델로네 삼각분할은 최소 각도를 최대화하는 속성을 가지며, 델로네 삼각형의 외접원은 내부에 다른 입력 점을 포함하지 않는다. 델로네 삼각분할은 뒤집기, 점진적, 분할 정복, Sweephull 알고리즘 등 다양한 알고리즘을 통해 계산되며, 유클리드 최소 신장 트리 계산, 지형 모델링, 메쉬 생성, 경로 계획 등 다양한 분야에 응용된다.
더 읽어볼만한 페이지
| 델로네 삼각분할 | |
|---|---|
| 개요 | |
 | |
| 분야 | 계산 기하학 |
| 이름의 유래 | 보리스 델로네 |
| 관련 항목 | 볼로노이 도형 최단 경로 문제 |
| 정의 | |
| 설명 | 2차원 이상의 공간에서 주어진 점들의 집합을 연결하는 선형 삼각 분할 각 삼각형의 외접원 내부에 다른 점이 존재하지 않도록 구성 |
| 특징 | 볼로노이 다이어그램의 쌍대 그래프 주어진 점들을 연결하는 가능한 모든 삼각 분할 중 가장 큰 최소 각도를 가짐 (최대-최소 각도 속성) |
| 활용 | 컴퓨터 그래픽스 지리 정보 시스템 (GIS) 최단 경로 문제 해결 유한 요소 해석을 위한 메시 생성 |
| 알고리즘 | |
| 점진적 삽입 알고리즘 | 점들을 하나씩 추가하면서 델로네 조건을 만족하도록 삼각 분할을 수정하는 방식 |
| 분할 정복 알고리즘 | 점들을 부분 집합으로 분할하고 각 부분 집합에 대해 델로네 삼각 분할을 수행한 후, 결과를 병합하는 방식 |
| 뒤집기 알고리즘 | 초기 삼각 분할에서 시작하여 델로네 조건을 만족하지 않는 변을 뒤집어 가면서 삼각 분할을 개선하는 방식 |
| 속성 | |
| 유일성 | 점들의 위치가 일반적인 경우 (어떤 네 점도 동일한 원 위에 있지 않음) 델로네 삼각 분할은 유일함 |
| 복잡도 | 2차원 평면에서 n개의 점에 대한 델로네 삼각 분할의 간선 수는 최대 3n - 6개 점진적 삽입 알고리즘의 시간 복잡도는 평균적으로 O(n log n) |
| 드로네 속성 | 빈 원 속성이라고도 하며, 델로네 삼각 분할의 각 삼각형의 외접원 내부에 다른 점이 존재하지 않는 속성 |
| 최대-최소 각도 속성 | 주어진 점들을 연결하는 가능한 모든 삼각 분할 중에서 델로네 삼각 분할이 가장 큰 최소 각도를 가짐 |
| 가장 가까운 이웃 | 델로네 삼각 분할에서 각 점의 가장 가까운 이웃은 해당 점과 연결된 삼각형의 꼭짓점 중 하나임 |
| 일반화 | |
| 제약 조건이 있는 델로네 삼각 분할 | 일부 변이 미리 지정된 경우에도 델로네 조건을 만족하도록 삼각 분할을 구성하는 방식 |
| 삼차원 델로네 사면체화 | 삼차원 공간에서 점들의 집합을 사면체로 분할하는 것으로, 델로네 삼각 분할의 개념을 삼차원으로 확장한 것 |
2. 보로노이 다이어그램과의 관계
일반적인 위치에 있는 이산 공간의 점 집합 P에 대한 델로네 삼각분할은 P에 대한 보로노이 다이어그램의 쌍대 그래프에 해당한다. 델로네 삼각형의 외심은 보로노이 다이어그램의 꼭짓점이 된다. 2차원 공간에서는 보로노이 꼭짓점들이 델로네 삼각형의 인접 관계로부터 파생되는 가장자리로 연결된다. 즉, 두 델로네 삼각형이 가장자리를 공유하면, 그 삼각형들의 외심은 보로노이 테셀레이션에서 가장자리로 연결된다.
하지만 다음과 같은 특수한 경우에는 이 관계가 성립하지 않거나 모호해질 수 있다.
- 세 개 이상의 점이 한 직선 위에 있는 경우: 이 점들을 지나는 외접원의 반지름은 무한대가 된다.
- 네 개 이상의 점이 하나의 원 위에 있는 경우 (공원점): 이 경우 삼각분할 방법이 유일하지 않아 모호하며, 모든 외심은 동일한 점이 된다.
- 유한한 점 집합 P의 경우, 무한대로 뻗어 나가는 보로노이 다이어그램의 가장자리는 이 관계로 정의되지 않는다. 만약 델로네 삼각분할을 보이어-왓슨 알고리즘으로 계산한다면, 계산 과정에 사용된 "슈퍼 삼각형"과 공통 꼭짓점을 갖는 삼각형의 외심은 무시해야 한다. 무한대로 향하는 가장자리는 유지된 삼각형의 외심에서 시작하며, 유지된 삼각형과 무시된 삼각형 사이의 공통 가장자리에 수직이다.
반대로 주어진 보로노이 다이어그램으로부터 대응하는 델로네 삼각분할을 만들 수도 있다. 각 보로노이 영역(셀)마다 하나의 점(모점)을 선택하고, 두 보로노이 영역이 서로 인접하면 해당 모점들을 선분으로 연결한다. 인접하지 않은 영역의 모점들은 연결하지 않는다. 이렇게 생성된 삼각분할에서 원래 보로노이 다이어그램의 모점을 델로네 점이라 하고, 델로네 점들을 잇는 선분을 델로네 변 또는 델로네 경계라고 부른다. 2차원 델로네 삼각분할에서 델로네 점과 델로네 변은 다각형(델로네 다각형)을 형성하는데, 특별한 경우(퇴화된 경우, 이는 모점을 적절히 바꾸어 해결 가능)를 제외하면 이 다각형은 삼각형이 된다. 이 과정을 통해 평면은 델로네 삼각형들의 집합으로 분할되며, 이를 델로네 삼각분할이라고 한다. 이러한 개념은 더 높은 차원에서도 유사하게 적용될 수 있다(델로네 단순체 분할).
3. ''d''차원 델로네 삼각분할
''d''차원 유클리드 공간에 있는 점들의 집합 '''P'''에 대해, '''델로네 삼각분할'''은 DT('''P''')를 만족하는 삼각분할이며, '''P'''의 어떤 점도 DT('''P''')에 있는 어떤 ''d''-단순체의 외접 초구 내부에 포함되지 않는다. 만약 '''P'''가 ''일반적인 위치''에 있는 점들의 집합이라면, 즉 '''P'''의 아핀 껍질이 ''d''차원이고, '''P'''에 속하는 어떤 ''d'' + 2개의 점도 내부에 '''P'''의 다른 점을 포함하지 않는 구의 경계 위에 동시에 존재하지 않는다면, '''P'''에 대한 델로네 삼각분할은 유일하게 존재한다.
''d''차원 유클리드 공간에 있는 점들의 집합에 대한 델로네 삼각분할을 찾는 문제는 (''d'' + 1)-차원 공간에 있는 점들의 집합에 대한 볼록 껍질을 찾는 문제로 변환될 수 있다. 이는 각 점 ''p''에 |''p''|2라는 추가 좌표를 부여하여 점들을 (''d'' + 1)-차원 공간의 포물면 위로 사영(이를 "리프팅"이라고 한다)한 뒤, 이 점들의 볼록 껍질을 구하는 방식으로 이루어진다. 이 볼록 껍질의 아랫면(lower hull)을 다시 ''d''차원 공간으로 사영하면 델로네 삼각분할을 얻을 수 있다(윗면은 사용하지 않는다). 볼록 껍질은 유일하게 결정되므로, 점들이 일반적인 위치에 있다면 델로네 삼각분할도 유일하다. 만약 볼록 껍질의 면(facet)이 단순체가 아니라면, 이는 ''d'' + 2개 이상의 점들이 동일한 ''d''-초구 위에 놓여 있다는 의미이며, 이 경우 점들은 일반적인 위치에 있지 않다.
''n''을 점의 개수, ''d''를 차원의 수라고 할 때, ''d''차원 델로네 삼각분할은 다음과 같은 속성을 가진다.
- 삼각분할을 구성하는 모든 단순체들의 합집합은 점들의 볼록 껍질이다.
- 델로네 삼각분할은 O(''n''⌈''d''/2⌉)개의 단순체를 포함한다.
- 평면(''d'' = 2)에서 볼록 껍질의 정점 개수가 ''b''개일 때, 점들의 모든 삼각분할은 최대 2''n'' – 2 – ''b''개의 삼각형과 하나의 외부 면을 가진다( 오일러 특성 참조).
- 점들이 평면에서 푸아송 과정에 따라 균일하게 분포되어 있다면, 각 정점은 평균적으로 6개의 이웃 삼각형을 가진다. 일반적으로 ''d''차원 공간에서도 평균 이웃 수는 ''d''에만 의존하는 상수이다.
- 평면에서 델로네 삼각분할은 최소 각도를 최대화한다. 즉, 델로네 삼각분할의 가장 작은 각도는 다른 어떤 삼각분할의 가장 작은 각도보다 크거나 같다. 그러나 델로네 삼각분할이 반드시 최대 각도를 최소화하거나 변의 길이를 최소화하는 것은 아니다.
- 델로네 삼각분할의 각 삼각형(또는 단순체)의 외접 초구는 내부에 다른 입력 점을 포함하지 않는다.
- 두 입력 점 ''p'', ''q''를 지나는 원(또는 초구)이 내부에 다른 입력 점을 포함하지 않으면, 두 점을 연결하는 선분 ''pq''는 델로네 삼각분할의 변이다.
- ''d''차원 공간의 점 집합에 대한 델로네 삼각분할의 각 단순체는, 점들을 (''d'' + 1)-차원 포물면으로 사영했을 때 생기는 볼록 껍질의 면(facet)에 해당하며, 그 역도 성립한다.
- 어떤 점 ''p''에 가장 가까운 점 ''b''가 있다면, 선분 ''pb''는 델로네 삼각분할의 변이다. 이는 최근접 이웃 그래프가 델로네 삼각분할의 부분 그래프이기 때문이다.
- 델로네 삼각분할은 기하 스패너이다. 평면(''d'' = 2)에서 두 정점 사이의 델로네 경로(델로네 변으로만 이루어진 경로) 중 가장 짧은 경로의 길이는 두 점 사이의 유클리드 거리의 1.998배 이하임이 알려져 있다.
주어진 보로노이 다이어그램으로부터 그에 대응하는 델로네 삼각분할을 만들 수 있다. 보로노이 다이어그램의 각 영역(보로노이 셀)에 해당하는 생성점(generator)을 '''델로네 점'''으로 간주하고, 서로 인접한 보로노이 셀에 해당하는 델로네 점들을 선분으로 연결하면 된다. 이 선분을 '''델로네 변''' 또는 '''델로네 경계'''라고 한다. 2차원 평면의 경우, 델로네 점과 델로네 변은 다각형('''델로네 다각형''')을 형성하는데, 퇴화된 특별한 경우를 제외하면 이 다각형은 항상 삼각형이 된다. 이렇게 평면을 델로네 삼각형들의 집합으로 분할하는 것을 '''델로네 삼각분할'''이라고 한다. 더 높은 차원에서도 유사한 방식으로 델로네 단순체 분할을 정의할 수 있다.
4. 속성
일반적인 위치에 있는 이산적인 점 집합 '''P'''에 대한 델로네 삼각분할은 '''P'''에 대한 보로노이 다이어그램의 쌍대 그래프에 해당한다. 델로네 삼각형의 외심은 보로노이 다이어그램의 꼭짓점이다. 2차원인 경우, 보로노이 꼭짓점은 델로네 삼각형의 인접 관계에서 파생될 수 있는 가장자리로 연결된다. 즉, 두 삼각형이 델로네 삼각분할에서 가장자리를 공유하면, 해당 외심은 보로노이 테셀레이션에서 가장자리로 연결된다.
이 관계가 성립하지 않거나 모호한 특수한 경우는 다음과 같다.
- 세 개 이상의 공선 점: 외접원의 반지름이 무한대가 된다.
- 완전한 원 위에 있는 네 개 이상의 점: 삼각분할이 모호해지고 모든 외심은 동일하다.
- 유한 집합 '''P'''의 경우, 무한대로 향하는 보로노이 다이어그램의 가장자리는 이 관계에 의해 정의되지 않는다. 델로네 삼각분할이 보이어-왓슨 알고리즘을 사용하여 계산될 때, "슈퍼" 삼각형과 공통 꼭짓점을 갖는 삼각형의 외심은 무시해야 한다. 무한대로 향하는 가장자리는 외심에서 시작하며, 유지된 삼각형과 무시된 삼각형 사이의 공통 가장자리에 수직이다.
''n''을 점의 개수, ''d''를 차원의 개수라고 할 때, 델로네 삼각분할은 다음과 같은 속성을 갖는다.
- 삼각분할의 모든 단순(simplex)들의 합집합은 점들의 볼록 껍질(convex hull)이다.
- 델로네 삼각분할은 O(''n''⌈''d''/2⌉)개의 단순(simplex)들을 포함한다.
- 평면(''d'' = 2)에서 볼록 껍질에 ''b''개의 정점이 있다면, 점들의 모든 삼각분할은 최대 2''n'' – 2 – ''b''개의 삼각형과 하나의 외부 면을 갖는다( 오일러 특성 참조).
- 점들이 일정한 강도를 가진 평면의 푸아송 과정에 따라 분포되어 있다면, 각 정점은 평균적으로 6개의 주변 삼각형을 갖는다. 더 일반적으로 ''d''차원에서 동일한 과정의 경우, 평균 이웃 수는 ''d''에만 의존하는 상수이다.
- 평면에서 델로네 삼각분할은 최소 각도를 최대화한다. 즉, 점들의 다른 삼각분할과 비교했을 때, 델로네 삼각분할의 가장 작은 각도는 다른 어떤 삼각분할의 가장 작은 각도보다 크거나 같다. 그러나 델로네 삼각분할이 반드시 최대 각도를 최소화하거나 가장자리 길이를 최소화하지는 않는다.
- 델로네 삼각형을 외접하는 원(외접원)은 그 내부에 다른 입력 점을 포함하지 않는다. 이를 빈 원 속성(empty circle property)이라고도 한다.
- 두 개의 입력 점 ''p'', ''q''를 지나는 원 중에서 내부에 다른 입력 점을 포함하지 않는 원이 존재하면, 두 점을 연결하는 선분 ''pq''는 주어진 점들의 델로네 삼각분할의 가장자리이다.
- ''d''차원 공간의 점 집합에 대한 델로네 삼각분할의 각 단순체는, 점들을 (''d'' + 1)-차원 포물면으로 투영했을 때 생기는 볼록 껍질의 면(facet)에 해당하며, 그 반대도 성립한다.
- 어떤 점 ''p''에 가장 가까운 이웃 점 ''b''가 있다면, 선분 ''pb''는 델로네 삼각분할의 가장자리이다. 이는 최근접 이웃 그래프가 델로네 삼각분할의 부분 그래프이기 때문이다.
- 델로네 삼각분할은 기하 스패너이다. 평면(''d'' = 2)에서 델로네 가장자리를 따라 두 정점 사이의 최단 경로는 그 사이의 유클리드 거리의 약 1.998배보다 길지 않다.
위의 속성으로부터 중요한 특징이 나타난다. 공통 변 ''BD''를 가진 두 삼각형 ''ABD'', ''BCD''를 볼 때(아래 그림 참조), 각도 ''α''와 ''γ''의 합이 180° 이하(''α'' + ''γ'' ≤ 180°)이면, 두 삼각형은 델로네 조건을 만족한다.
이것은 ''플리핑''(flipping) 기법을 사용할 수 있게 해주기 때문에 중요한 속성이다. 만약 두 삼각형이 델로네 조건을 만족하지 않으면(즉, ''α'' + ''γ'' > 180°), 공통 변 ''BD''를 공통 변 ''AC''로 교체(플립)하면 델로네 조건을 만족하는 새로운 두 삼각형 ''ABC'', ''ADC''가 생성된다.
이 연산을 ''플립''(flip)이라고 하며, 3차원 및 더 높은 차원으로 일반화할 수 있다.
5. 시각적 정의: 뒤집기 (Flipping)
공통 변 BD를 가진 두 삼각형 △''ABD''와 △''BCD''를 생각해 보자(그림 참조). 만약 두 삼각형의 마주보는 각의 합, 즉 α + γ가 180° 이하라면 (α + γ ≤ 180°), 이 두 삼각형은 델로네 조건을 만족한다.
이 성질은 "뒤집기(flipping)"라는 기법을 가능하게 하므로 중요하다. 만약 두 삼각형이 델로네 조건을 만족하지 않는다면, 즉 α + γ > 180° 라면, 공통 변 BD를 새로운 공통 변 AC로 교체("뒤집기")함으로써 델로네 조건을 만족하는 두 개의 새로운 삼각형 △''ABC''와 △''ADC''를 만들 수 있다.
이 변 교체 연산을 뒤집기(flip)라고 하며, 이는 3차원 및 더 높은 차원으로도 일반화될 수 있다.
델로네 삼각분할을 계산하는 많은 알고리즘은 특정 점이 삼각형의 외접원 내부에 있는지 빠르게 감지하는 연산과, 삼각형 및 모서리(변) 정보를 효율적으로 저장하는 자료 구조에 의존한다. 2차원에서 점 D가 세 점 A, B, C로 이루어진 삼각형의 외접원 내부에 있는지 판별하는 한 가지 방법은 다음과 같은 행렬식의 값을 계산하는 것이다.
:
만약 점 A, B, C가 반시계 방향 순서로 배열되어 있다면, 이 행렬식의 값이 양수일 경우에만 점 D가 외접원 내부에 존재한다. 즉, 델로네 조건을 만족하지 않는 상태임을 의미한다.
6. 알고리즘
델로네 삼각분할을 계산하는 다양한 알고리즘이 존재한다. 주요 접근 방식으로는 점을 하나씩 추가하며 삼각분할을 수정하는 점진적 알고리즘(예: 뒤집기 알고리즘, 보이어-왓슨 알고리즘), 점 집합을 나누어 처리한 뒤 병합하는 분할 정복 알고리즘, 그리고 스윕 라인 기법과 볼록 껍질을 활용하는 Sweephull 알고리즘 등이 있다. 각 알고리즘은 계산 효율성, 구현 복잡성, 병렬 처리 가능성 등에서 장단점을 가진다.
6. 1. 뒤집기 알고리즘
삼각형이 델로네 삼각분할 조건을 만족하지 않으면, 해당 삼각형의 가장자리 중 하나를 뒤집을 수 있다. 이를 이용한 간단한 알고리즘은 다음과 같다: 먼저 점들의 임의의 삼각분할을 만든 뒤, 모든 삼각형이 델로네 조건을 만족할 때까지 조건에 맞지 않는 가장자리를 계속 뒤집는다. 하지만 이 방식은 최악의 경우 Ω(''n''2) 번의 가장자리 뒤집기가 필요할 수 있다. 이 알고리즘은 3차원 이상으로 일반화될 수 있지만, 수렴이 항상 보장되지는 않는다. 이는 알고리즘의 기반이 되는 플립 그래프의 연결성 문제 때문인데, 2차원 점 집합에서는 플립 그래프가 연결되어 있지만, 더 높은 차원에서는 연결되지 않을 수 있기 때문이다.델로네 삼각분할을 효율적으로 계산하는 가장 간단한 방법 중 하나는 점(정점)을 하나씩 반복적으로 추가하면서, 그래프에서 새로 추가된 점의 영향을 받는 부분만 다시 삼각 분할하는 것이다. 정점 ''v''가 추가되면, 먼저 ''v''를 포함하는 삼각형들을 찾아 분할하고, 이후 앞서 설명한 가장자리 뒤집기(플립) 알고리즘을 적용한다. 단순하게 구현할 경우, 새로운 정점 ''v''를 포함하는 삼각형을 찾기 위해 모든 삼각형을 검사해야 하고(이 과정에 O(''n'') 시간이 소요될 수 있음), 이후 잠재적으로 많은 삼각형을 뒤집어야 할 수 있어 전체 실행 시간은 O(''n''2)이다.
정점을 무작위 순서로 삽입하면, 각 정점을 삽입할 때 평균적으로 O(1)개의 삼각형만 뒤집게 된다는 것이 증명되었다. (물론, 특정 경우에는 훨씬 더 많은 삼각형을 뒤집을 수도 있다.) 하지만 이 방법만으로는 점 위치를 찾는 시간을 개선해야 한다. 이를 위해 분할 및 뒤집기 기록을 저장하는 방법을 사용할 수 있다. 각 삼각형이 분할되어 새로 생긴 두세 개의 삼각형을 가리키는 포인터를 저장하는 방식이다. 새로운 정점 ''v''를 포함하는 삼각형을 찾을 때, 초기 삼각형(루트)에서 시작하여 ''v''를 포함하는 다음 삼각형을 가리키는 포인터를 따라가면 된다. 이 과정은 평균적으로 O(log ''n'') 시간이 걸린다. 결과적으로 모든 정점을 추가하는 데 걸리는 총 시간은 평균 O(''n'' log ''n'')이다. 이 기법은 더 높은 차원으로 확장될 수 있으며(Edelsbrunner와 Shah가 증명함), 평균 시간 복잡도는 여전히 O(''n'' log ''n'')이다. 그러나 최종 델로네 삼각분할의 크기와 관계없이, 실행 시간은 차원의 수에 따라 지수적으로 증가할 수 있다는 단점이 있다.
보이어-왓슨 알고리즘은 점진적 구성 방식을 사용하는 또 다른 접근법이다. 이 알고리즘은 새로 삽입된 정점을 포함하는 델로네 삼각형을 계산할 때 가장자리 뒤집기 대신 다른 방법을 사용한다.
가장자리 뒤집기에 기반한 알고리즘은 일반적으로 병렬화하기 어렵다는 단점이 있다. 특정 점(예: 바퀴 모양의 점 집합에서 중심점)을 추가할 경우, 최대 O(''n'')개의 뒤집기가 연쇄적으로 발생할 수 있기 때문이다. Blelloch 등은 립앤텐트(rip-and-tent) 기법에 기반한 새로운 점진적 알고리즘을 제안했다. 이 알고리즘은 실용적이며, 다중 로그(polylogarithmic) 스팬(span)을 가지므로 병렬화에 유리하다.
6. 2. 분할 정복 알고리즘
2차원 삼각분할을 위한 분할 정복 알고리즘은 리(Lee)와 샥터(Schachter)에 의해 개발되었고, 기바스(Guibas)와 스톨피(Stolfi)에 의해 개선되었으며, 이후 드와이어(Dwyer)에 의해 더욱 발전되었다. 이 알고리즘은 점들을 두 개의 집합으로 나누기 위해 재귀적으로 선을 그어 분할하는 방식을 사용한다. 각 부분 집합에 대해 델로네 삼각분할을 계산한 다음, 두 집합을 분할선을 따라 병합한다. 효율적인 병합 기법을 사용하면 병합 과정은 O(n) 시간에 수행될 수 있으며, 따라서 전체 알고리즘의 실행 시간은 O(n log n)이다.점들이 균일한 임의 분포와 같이 특정 유형으로 분포되어 있는 경우, 분할선을 지능적으로 선택하면 최악의 경우 성능을 유지하면서도 평균적인 예상 실행 시간을 O(n log log n)으로 줄일 수 있다.
P. 치뇨니(Cignoni), C. 몬타니(Montani), R. 스코피뇨(Scopigno)는 "DeWall: E''d''에서 빠른 분할 정복 들로네 삼각분할 알고리즘"이라는 연구에서 d 차원 공간에서도 삼각분할을 수행할 수 있는 분할 정복 방법을 제시했다.
분할 정복 알고리즘은 순차적으로 실행되는 델로네 삼각분할 생성 기술 중 가장 빠른 것으로 알려져 있다.[2][3]
6. 3. Sweephull 알고리즘
Sweephull[4]은 2차원 델로네 삼각분할을 생성하기 위한 하이브리드 기법으로, 스윕-헐(sweep-hull)과 플립(flip) 알고리즘을 결합하여 사용한다. 이 알고리즘은 먼저 스윕-헐 단계를 통해 초기 삼각분할을 구축한다. 스윕-헐 단계에서는 주어진 2차원 점들을 반경 방향으로 정렬한 뒤, 이 정렬된 점 집합을 반복적으로 순회한다. 각 순회 과정에서 현재까지 구성된 볼록 껍질의 보이는 부분에 새로운 점을 이용해 삼각형을 추가하며, 이를 통해 겹치지 않는 삼각분할을 점진적으로 만들어 나간다. 이때 점들을 정렬하는 순서는 생성되는 삼각형 내부에 다른 어떤 점도 포함되지 않도록 보장해야 한다.반경 방향 정렬 방식은 초기 삼각분할이 최종적인 델로네 삼각분할 결과에 가깝도록 만들어, 후속 플립 작업의 필요성을 줄여준다는 장점이 있다. 스윕-헐 단계가 완료된 후에는, 최종적으로 반복적인 삼각형 플립 단계를 거쳐 델로네 삼각분할 조건을 만족하도록 삼각망을 조정하여 알고리즘을 마무리한다.
7. 응용 분야
점 집합의 유클리드 최소 신장 트리는 동일한 점들의 델로네 삼각분할의 부분 집합이며, 이를 활용하여 효율적으로 계산할 수 있다.
지형이나 점군이 주어진 다른 객체를 모델링하기 위해, 델로네 삼각분할은 모델에서 다각형으로 사용할 수 있는 좋은 삼각형 집합을 제공한다. 특히 델로네 삼각분할은 좁은 삼각형(면적에 비해 외접원이 큰 삼각형)을 피하는 경향이 있다. 이는 삼각 불규칙 네트워크(TIN) 생성에 유용하다.
델로네 삼각분할은 델로네 테셀레이션 필드 추정기를 통해 점 샘플링의 밀도 또는 강도를 결정하는 데 사용될 수 있다.
델로네 삼각분할은 메쉬 생성에 자주 사용된다. 각도 보장과 빠른 삼각분할 알고리즘이 개발되었기 때문에, 물리 시뮬레이션의 유한 요소법 및 유한 체적법과 같은 공간 이산화 솔버를 위한 메쉬 생성에 활용된다. 일반적으로 메쉬화할 도메인은 조잡한 단순 복합체로 지정되며, 메쉬가 수치적으로 안정적이려면 예를 들어 루퍼트 알고리즘을 사용하여 세분화해야 한다.
유한 요소법 및 경계 요소법 기술의 인기가 높아짐에 따라 자동 메쉬 생성 알고리즘을 개선하려는 노력이 증가하고 있다. 그러나 이러한 알고리즘들은 왜곡되거나 심지어 사용할 수 없는 그리드 요소를 생성할 수 있다. 다행히 기존 메쉬를 가져와서 품질을 개선할 수 있는 여러 기술이 존재한다. 예를 들어 스무딩(메쉬 개선이라고도 함)은 요소 왜곡을 최소화하기 위해 노드를 재배치하는 방법 중 하나이다. 스트레치 그리드 방법은 델로네 기준을 쉽게 충족하고 한 단계 솔루션으로 빠르게 충족하는 의사 규칙적인 메쉬를 생성할 수 있게 해준다.
제약 델로네 삼각분할은 자동 운전 및 지형 측량에서 경로 계획에 적용되었다.
8. 참고 문헌
- Shewchuk, J.; Dey, T. K.; Cheng, S. W. (2016). ''델로네 메시 생성''. Chapman and Hall/CRC. ISBN 9781584887317.
- Si, Hang (2015). "TetGen, 델로네 기반 품질 사면체 메시 생성기". ''ACM Transactions on Mathematical Software (TOMS)''. '''41''' (2): 1–36 (11쪽). ISSN 0098-3500.
- Du, Q.; Wang, D. (2006). "견고하고 품질 좋은 델로네 메시 생성에 대한 최근 진전.". '':en:Journal of Computational and Applied Mathematics''. '''195''' (1-2): 8–23. ISSN 0377-0427.
- Shewchuk, J. R. (2002). "삼각형 메시 생성을 위한 델로네 정제 알고리즘". ''Computational geometry''. '''22''' (1-3): 21–74. ISSN 0925-7721.
- Shewchuk, Jonathan Richard (1997). ''델로네 정제 메시 생성''. 카네기 멜론 대학교 피츠버그 파 컴퓨터 과학부, 박사 학위 논문. 연구 논문 (카네기 멜론 대학교. 컴퓨터 과학부), CMU-CS-97-137. OCLC 37586603.
- 스기하라 고키치 (2013). ''계산 기하학''. 수리 공학 라이브러리, 1. 아사쿠라 서점. ISBN 9784254116816.
- 아사노 테츠오 (2007). ''계산 기하: 이론의 기초부터 구현까지''. 쿄리츠 출판. ISBN 9784320121768.
- 스기하라 고키치 (1998년 3월 20일). ''FORTRAN 계산 기하 프로그래밍''. 이와나미 컴퓨터 과학. 이와나미 서점. ISBN 4000077082.
참조
[1]
문서
Loosely speaking, the region that a rubber band stretched around the points would enclose.
[2]
웹사이트
Archived copy
http://www.cs.berkel[...]
2010-08-18
[3]
웹사이트
Triangulation Algorithms and Data Structures
https://www.cs.cmu.e[...]
2018-04-25
[4]
웹사이트
S-hull
http://www.s-hull.or[...]
2018-04-25
[5]
간행물
Constraint-based planning and control for safe, semi-autonomous operation of vehicles
https://wiki.epfl.ch[...]
IEEE
2012-07-05
[6]
서적
Voronoi Diagrams And Delaunay Triangulations
https://books.google[...]
World Scientific Publishing Company
2013-06-26
[7]
웹archive
Parallelism in Randomized Incremental Algorithms
https://www.cs.cmu.e[...]
2018-04-25
[8]
논문
DeWall: A fast divide and conquer Delaunay triangulation algorithm in Ed
[9]
서적
Computational Geometry: Algorithms and Applications
http://www.cs.uu.nl/[...]
Springer-Verlag
2010-02-23
[10]
논문
Sur la sphère vide
http://mi.mathnet.ru[...]
[11]
서적
Triangulations, Structures for Algorithms and Applications
Springer
[12]
논문
A faster divide-and-conquer algorithm for constructing delaunay triangulations
1987-11
[13]
논문
Incremental Topological Flipping Works for Regular Triangulations
[14]
citation
An ''O''(''n''2 log ''n'') time algorithm for the minmax angle triangulation
http://www.comp.nus.[...]
2017-10-24
[15]
웹사이트
Frequently Asked Questions in Polyhedral Computation
https://www.cs.mcgil[...]
2018-10-29
[16]
논문
Randomized incremental construction of Delaunay and Voronoi diagrams
[17]
논문
Primitives for the manipulation of general subdivisions and the computation of Voronoi
[18]
논문
Flipping Edges in Triangulations
[19]
간행물
Improving Worst-Case Optimal Delaunay Triangulation Algorithms
1992-06
[20]
citation
Interface area, edge length, and number of vertices in crystal aggregates with random nucleation
http://www.extra.res[...]
[21]
웹사이트
COMPUTING CONSTRAINED DELAUNAY TRIANGULATIONS IN THE PLANE
http://www.geom.uiuc[...]
2018-04-25
[22]
논문
The upper bound theorem for polytopes: an easy proof of its asymptotic version
[23]
citation
The stretch factor of the Delaunay triangulation is less than 1.998
본 사이트는 AI가 위키백과와 뉴스 기사,정부 간행물,학술 논문등을 바탕으로 정보를 가공하여 제공하는 백과사전형 서비스입니다.
모든 문서는 AI에 의해 자동 생성되며, CC BY-SA 4.0 라이선스에 따라 이용할 수 있습니다.
하지만, 위키백과나 뉴스 기사 자체에 오류, 부정확한 정보, 또는 가짜 뉴스가 포함될 수 있으며, AI는 이러한 내용을 완벽하게 걸러내지 못할 수 있습니다.
따라서 제공되는 정보에 일부 오류나 편향이 있을 수 있으므로, 중요한 정보는 반드시 다른 출처를 통해 교차 검증하시기 바랍니다.
문의하기 : help@durumis.com