Bowyer-Watson Algorithm : Online Delaunay Triangulation

 

 

 

 

 

1. Introduction

  Delaunay triangulation을 위한 알고리즘 중 가장 쉽고 간단한 것이 Bowyer-Watsom algorithm이다. Bowyer-Watson algorithm은 3차원 이상의 점들에 대해서도 Delaunay triangulation 계산할 수 있다는 장점이 있다. 또, Bowyer-Watson algorithm이 online query를 이용하는 알고리즘이라는 점에서 다른 알고리즘과 차별화된다. 이번 글에서는 이 Bowyer-Watson algorithm에 대해 설명하고 필자의 구현체에 대한 소개할 것이다.

 

2. Algorithm

  Delaunay triangulation은 모든 삼각형의 외접원 내에 어떠한 점도 속하지 않도록 삼각형을 형성하는 것이다. 이는 어떤 점 \(p\)와 삼각형 \(T\)가 있을 때,

 

\(\mathrm{dist}\{p,u\} \le r\) for all \(u \in T\).

 

를 만족한다는 것이다. (\(r\)은 \(T\)의 외접원의 반지름)

 

  Bowyer-Watson algorithm은 이런 부분으로 부터 시작한다. Delaunay triangulation이 이루어진 상태에서 어떤 점 \(p\)를 추가했다고 해보자. Delaunay triangluation에 포함되는 삼각형의 집합을 \(D\)라 하겠다. 만약,

 

\(\mathrm{dist}(p,u) < r\) for all \(u \in T\), \(T \in D\), (\(r\)은 \(T\)의 외접원의 반지름)

 

라면, 이러한 \(T\)는 새로운 Delaunay triangulation \(D'\)에는 없어야 한다.

Bowyer-Watson algorithm에서 그러한 \(T\)를 bad triangle이라고 하며, 새로운 점이 추가될 때 마다 이런 \(T\)를 제거한다.

 

Bad triangle을 모두 제거했다면, \(p\)를 포함하는 새로운 삼각형을 추가해야 한다. 그런 삼각형은 bad triangle을 제거할 때 각 edge가 제거된 횟수를 세는 것으로 알 수 있다. (edge가 제거된 횟수는 그 edge가 몇 개의 bad triangle에 포함되어 있었는지에 관한 것이다.)

만약 edge가 한 번만 제거되었다면, 그 edge를 구성하는 두 점과 \(p\)로 이루어진 삼각형이 새로운 삼각형이 된다. 새로운 삼각형은 2개 이상일 수 있다.

 

*만약 edge가 한 번만 제거되었다면, 그 edge를 가지는 삼각형이 하나 뿐이라는 것이다. 즉, 이 edge와 \(p\)를 이용하여 새로운 삼각형을 만들어도 Delaunay triangulation의 조건을 만족한다.

 

Bowyer-Watson algorithm은 triangulation을 할 점을 모아놓고, 점을 하나씩 추가해가며 마다 위의 과정을 반복한다.

먼저, 모든 점이 포함될 만큼 큰 삼각형을 하나 만드는데, 이를 super-triangle이라고 한다. super triangle 을 형성하고 나서 점을 하나씩 추가하고, 마지막에는 이 super-triangle을 제거해준다.

 

마지막으로, 동적 쿼리를 처리하고 싶다면 , super-triangle을 충분히 크게 만들어준 후, 마지막에도 이를 제거하지만 않아야 한다. 대신 triangulation을 return할 때만 super-triangle을 빼는 방법으로 동적 쿼리를 효율적으로 처리할 수 있다.

3. Implementation

https://github.com/Sora-Sugiyama/Libs/blob/main/Computational-Geometry/BowyerWatson.h

  위 링크에 접속하면 필자의 코드를 읽을 수 있다. 해당 구현에서는 2차원만 고려한다.

Name	Description	Time Complexity	Space Complexity
addPoint(vector<double>p)	점을 추가하는 쿼리	\(O(N \log N)\)	\(O(N \log N)\)
Delaunator()	추가한 모든 점들에 대해서 Delaunay triangulation 계산	\(O(N^2 \log N)\)	\(O(N)\)
Init(vector<vector<double> >P)	주어진 점들을 통해 초기화	\(\Theta(N)\)	\(\Theta(N)\)
CLEAR()	모든 변수들을 초기화 전 상태로 만든다.	\(O(1)\)	\(O(1)\)
lines	Triangulation을 이루는 변들	-	-
triangulation	Triangulation을 이루는 삼각형들	-	-
points	초기화 할때 넣어준 점들	-	-
wasInit	초기화가 되었는가 확인하는 변수	-	-

 

예시코드:

#include "BowyerWatson.h"
#include <random>
#include <ctime>
using namespace std;

BowyerWatson2d Machine;

int main(){
	ios_base::sync_with_stdio(false);cin.tie(NULL);
	int n=10;
	random_device rd;
	mt19937 gen(rd());
	uniform_int_distribution<int>uid(-1000,1000);
	vector<vector<double> >P;
	while(n--){
		double a=uid(gen),b=uid(gen);
		P.push_back({a,b});
		cout<<a<<" "<<b<<"\n";
	}
	cout<<flush;
	Machine.Init(P);
	Machine.Delaunator();
	for(auto it=Machine.lines.begin();it!=Machine.lines.end();it++){
		cout<<"("<<(*it)[0][0]<<", "<<(*it)[0][1]<<") -> "<<"("<<(*it)[1][0]<<", "<<(*it)[1][1]<<")\n";
	}
	cout<<flush;
	return 0;
}

위 실험 코드를 이용한 삼각분할, 시각화는 Geogbra.&nbsp;https://www.geogebra.org/m/hwtjxybh