들로네삼각화 | 둥충코딩

이전블로그 내용 백업

들로네 삼각형은 평면위의 점들을 삼각형으로 분할했을때 모든 내각의 합이 최소가 되도록 하는 분할을 말한다. 이에 대한 응용은 여러가지가 있을 것이다. 이는 들로네삼각형를 참조하면 응용에 대해서 자세히 나온다.

이를 자바스크립트로 구현하고자 한다. 참고한 알고리즘은 O(n^2)로 동작하는 알고리즘으로서 세점의 외접원을 이용하는 알고리즘이다. 실제로는 O(n log n) 시간복잡도인 알고리즘도 나와있지만 incremental 방식의 한 종류로서 시각화하기 적당한 알고리즘으로 선택하였다.

간단하게 알고리즘을 기술하면

임의의 점을 기준으로 최소 길이를 지닌 Edge 하나를 찾는다.
선택한 Edge를 CE(후보Edge집합)에 넣는다.
CE에서 Edge 하나를 꺼내 선택한다. 비어있다면 알고리즘 종료
CCW(시계반대방향조건) 만족하는 점 하나를 선택하여 임의의 삼각형을 만든다.
삼각형의 외접원을 구한다.
CCW를 만족하는 다른 점이 원 속에 포함되는지 검사한다. 포함된다면 4번으로 돌아간다.
마지막으로 선택된 점과 선택된Edge의 두점을 잇는 새로운 네개의 Edge가 있다 (시계방향, 시계반대방향)
시계방향의 Edge들은 CE에 넣고 시계반대방향의 Edge들은 DE(완료Edge집합)에 넣는다. 그리고 선택한 Edge도 DE에 넣는다.
선택된 점이 없다면 3번으로 돌아간다.

즉 외접원이 핵심인데 어떠한 점도 외접원안에 포함되지 않는다면 그것이 바로 내각이 최소화 되는 모양일 것이다. DE(완료Edge집합) 가 완성된 들로네 삼각화 그래프이다. 아래는 완성된 모습이다. HTML5 의 canvas tag를 이용하여 만들었다. 보이지 않는다면 크롬 브라우져로 보면 된다. 모든소스는 직접 작성하였으며 풀소스가 궁금하면 소스보기로 보면된다. 라이센스는 따로 표시되어 있지 않으나 MIT License

위 알고리즘은 항상 Convex 하게 만드려고 하기 때문에 바깥쪽에 존재하는 삼각형들은 모양이 길쭉해지는 경향이 있다. 실제 이 알고리즘을 자바스크립트로 작성한 이유는 시각화에 있다. 이 알고리즘은 논문으로만 보면 이해하기 어려운 면이 있으나 애니메이션으로 보면 큰 그림을 이해하는데 좋을 것이다.

위 알고리즘은 Edge 하나를 기준으로 다른 어떤점도 포함되지 않는 외접원을 구하는게 목표이다. 이를 모든 Edge에 대해 수행하면 된다. 알고리즘을 보면 큰 원이 점차 점이 바뀌며 작은 원으로 변하다가 결국 점하나를 찾으면서 Edge를 늘려나가는 식으로 동작하는 것을 알수 있다.

위 알고리즘을 구현하기 위해서는 CCW를 체크하는 것과 외접원을 구할 필요가 있다.

JAVASCRIPT
	// 반시계방향 테스트
	// ccw > 0 : counter clockwise
	// ccw < 0 : clockwise
	// ccw = 0 : on the line
	function ccwTest(x1,y1,x2,y2,x3,y3){
		return (x1*y2 + x2*y3 + x3*y1) - (y1*x2 + y2*x3 + y3*x1);
	}

	// 세점을 지나는 원구하기
	// 1. 두 변을 기준으로 중점을 구한다.
	// 2. 해당변과 수직인 기울기를 구한다.
	// 3. 중점과 기울기를 이용 두 직선을 구한뒤 교점을 구한다.

	var _cx, _cy, _cr; // output!, for performance

	function get3PointCircle(x1,y1,x2,y2,x3,y3){
		_cx = _cy = _cr = 0.0;

		var mx1 = (x2 + x1) / 2; // mid of x1~x2
		var my1 = (y2 + y1) / 2; // mid of y1~y2
		var mx2 = (x2 + x3) / 2;
		var my2 = (y2 + y3) / 2; 

		var deltay_e1 = y2 - y1;
		var deltay_e2 = y2 - y3;
		var d1, d2, yy;


		if(deltay_e1 != 0){
			d1 = (x1 - x2) / deltay_e1;
			yy = my1 - d1 * mx1;
			
			if(deltay_e2 != 0){
				d2 = (x3 - x2) / deltay_e2;
				if( d1 != d2 ){
					_cx = (yy - (my2 - d2 * mx2)) / (d2 - d1);
				}else{
					return ; // exception
				}
			} else if(x3 - x2 == 0){
				return ; // exception	
			} else {
				_cx = mx2;
			}
		}else if(deltay_e2 != 0 && x1 - x2 != 0){
			d1 = (x3 - x2) / deltay_e2;
			yy = my2 - d1 * mx2;
			_cx = mx2;
		}else{
			return ; // exception
		}

		_cy = d1 * _cx + yy;
		_cr = Math.sqrt((x1-_cx)*(x1-_cx) + (y1-_cy)*(y1-_cy));
	
	}

CW 를 체크하는 것에서 알수 있듯이 만들어진 들로네 삼각형 그래프는 DAG(방향성그래프)로서 거의 완성이 된것처럼 보여도 계속 알고리즘이 동작하는 것처럼 보이는 이유이다. 한개의 Edge처럼 보여도 두개의 방향성을 지니고 있어 두개의 Edge라고 해석된다.

실은 이것을 만든 이유는 또다른 알고리즘을 시각화 하기 위해 어떻게 하면 그래프를 적당하고 보기 좋게 모양을 잡을까 연구하다가 찾고 연구한뒤 구현한 것이다. 위 들로네 삼각형은 보로노이 다이어그램과 Dual 관계에 있으므로 이를 구현하면 보로노이 다이어그램은 자연스럽게 따라오게 된다. 이는 나중 연구로 미루며 포스팅 종료