본문 바로가기

Graphics Note

Delaunay triangulation in 2D

들로네 삼각분할(delaunay triangulation). 삼각분할(triangulation) 기법 중 하나로 보로노이 다이어그램(voronoi diagram)과 듀얼이미지인 그래프를 그리게된다.

 

들로네 삼각분할은 다음 조건을 만족하는 삼각형들의 집합으로 설명할 수 있다.

* simplex로 이루어져있다

* 모든 simplex의 가장 작은 내각이 최대값을 가진다.

* simplex로 이루어지는 circumcircle (3d 라면 circumsphere, 4d 라면...)의 내부에

   simplex 포인트 외의 다른 포인트가 존재하지 않는다.

 

[그림출처: http://en.wikipedia.org/wiki/Delaunay_triangulation]

 

위 그림으로 쉽게 이해할 수 있을것이다.

 

2차원 들로네 삼각분할한 그래프에서 삼각형 외접원의 중심을 이으면 보로노이 다이어그램이 된다고한다. 그래서 듀얼이미지..

 

  

[그림출처(역시 위키..): http://en.wikipedia.org/wiki/Delaunay_triangulation]

 

들로네 삼각분할은 incremental 알고리즘과 divide and conquer 알고리즘으로 구분할 수 있는데, 난 incremental algorithm을 작성해보았다. 둘 다 최대수행비용은 비슷한듯?

 

OpenGL로 삼각형을 표시하게 했고, 핵심 클래스는 DelaunayTriangulation 을 보면 된다.

 

 

super triangle의 크기를 재설정하는 부분이 조금 이상해서 처음 삼각형 밖에 점을 찍으면 프로그램이 오작동한다. 귀찮으므로 패스...

 

들로네 삼각분할을 재밌게 설명한 글이 있다. http://darkpgmr.tistory.com/96 

이게 어디에 쓰일 수 있는지 볼수있다.

'Graphics Note' 카테고리의 다른 글

Vector/Matrix class  (0) 2013.12.02
glRotatef+glTranslatef VS gluLookAt for View transformation  (4) 2013.12.02
외곽선 검출  (0) 2013.08.27
perspective projection  (3) 2013.07.19
[Mathematics] rotate model using quaternion  (4) 2013.07.11