보우어-왓슨 알고리즘

계산 기하학에서 Bowyer-Watson 알고리즘은 임의의 치수에서 유한한 점 집합의 Delaunay 삼각측량을 계산하는 방법이다.이 알고리즘은 또한 Delaunay 삼각측량의 이중 그래프인 점의 보로노이 도표를 얻는 데 사용될 수 있다.

설명

Bowyer-Watson 알고리즘은 증분 알고리즘이다.원하는 점의 하위 집합의 유효한 델라나이 삼각 측정에 점들을 한 번에 하나씩 추가함으로써 작동한다.삽입할 때마다 원주에 새 점이 들어 있는 삼각형이 모두 삭제되어 별 모양의 다각형 구멍이 남게 되며, 이 구멍은 새 점을 사용하여 다시 트리앵글된다.삼각측량 연결을 사용하여 제거할 삼각형을 효율적으로 찾음으로써, 알고리즘은 이것이 O(N²)까지 올라가는 특별한 변질 사례가 존재하지만, N 포인트를 삼각측량하는 O(N 로그 N) 연산을 취할 수 있다.^[1]

• 

  첫 번째 단계: "super"-triangle을 둘러싸는 곳에 노드 삽입

• 

  두 번째 노드 삽입

• 

  세 번째 노드 삽입

• 

  네 번째 노드 삽입

• 

  다섯 번째(마지막) 노드 삽입

• 

  초삼각형에서 극한 모서리 제거

역사

이 알고리즘은 때때로 보우어 알고리즘이나 왓슨 알고리즘으로 알려져 있다.Adrian Bowyer와 David Watson은 동시에 독립적으로 그것을 고안해 냈고, 각각 The Computer Journal(아래 참조) 같은 호에 그것에 관한 논문을 발표했다.

가성음

다음의 유사 노드는 Bowyer-Watson 알고리즘의 기본 구현을 설명한다.그것의 시간 복잡성은 $O{\displaystyle }$( ${\displaystyle {}^{}}$ $){\displaystyle O (n^{2})$이다$.$ 효율성은 여러 가지 방법으로 향상될 수 있다.예를 들어, 삼각형 연결은 모든 삼각형을 확인할 필요 없이 원곡선에 새로운 점을 포함하는 삼각형을 찾는 데 사용될 수 있다. 그렇게 함으로써 시간 $복잡성$을${\displaystyle }$O (${\displaystyle n}$ log$){\displaystyle O$ ($n\log$ n$)}$까지 줄일 수 있다$.$ 원곡선을 미리 계산하면 추가 나를 희생시키면서 시간을 절약할 수 있다.무어적 관습그리고 점이 균일하게 분포되어 있는 경우 삽입하기 전에 힐버트 곡선을 채우는 공간을 따라 점들을 정렬할 수도 있다.^[2]

기능을 하다 보이어왓슨 (포인트 리스트)    // pointList는 삼각측량할 점을 정의하는 좌표 집합이다.    삼각 측량 := 텅 빈 삼각형의 메쉬 자료 구조화하다    덧셈을 잘 하는 군요-삼각형의 로 삼각 측량 // pointList의 모든 포인트를 완전히 포함할 수 있을 만큼 충분히 커야 함    을 위해 각각 점을 찍다 에 포인트 리스트 하다 // 모든 점을 삼각 측정에 한 번에 하나씩 추가       배드트리앙글스 := 텅 빈 세트       을 위해 각각 삼각형의 에 삼각 측량 하다 // 먼저 삽입으로 인해 더 이상 유효하지 않은 모든 삼각형을 찾으십시오.          만일 점을 찍다 이다 안쪽에 원을 그리며 돌다 의 삼각형의             덧셈을 삼각형의 로 배드트리앙글스       다각형 := 텅 빈 세트       을 위해 각각 삼각형의 에 배드트리앙글스 하다 // 다각형 구멍의 경계 찾기          을 위해 각각 가장자리를 잡다 에 삼각형의 하다             만일 가장자리를 잡다 이다 아닌 공유했습니다. 에 의해 아무 것이나 타사의 삼각형 에 배드트리앙글스                덧셈을 가장자리를 잡다 로 다각형       을 위해 각각 삼각형의 에 배드트리앙글스 하다 // 데이터 구조에서 제거          제거하다 삼각형의 로부터 삼각 측량       을 위해 각각 가장자리를 잡다 에 다각형 하다 // 다각형 구멍 재조정          뉴트리 := 형체를 이루다 a 삼각형의 로부터 가장자리를 잡다 로 점을 찍다          덧셈을 뉴트리 로 삼각 측량    을 위해 각각 삼각형의 에 삼각 측량 // 포인트 삽입 완료, 이제 정리       만일 삼각형의 포함하다 a 꼭지점 로부터 독창적인 잘 하는 군요-삼각형의          제거하다 삼각형의 로부터 삼각 측량    돌아오다 삼각 측량 

참조

추가 읽기

• Bowyer, Adrian (1981). "Computing Dirichlet tessellations". Comput. J. 24 (2): 162–166. doi:10.1093/comjnl/24.2.162.
• Watson, David F. (1981). "Computing the n-dimensional Delaunay tessellation with application to Voronoi polytopes". Comput. J. 24 (2): 167–172. doi:10.1093/comjnl/24.2.167.
• 효율적인 삼각측량 알고리즘 몇 가지 언어로 된 소스 코드 예제를 포함한 지형 모델링 일반 설명에 적합

외부 링크

• pyDelaunay2D : Bowyer-Watson 알고리즘의 교훈적인 Python 구현.
• Bl4ckb0ne/delaunay-triangulation : Bowyer-Watson 알고리즘의 C++ 구현