블로그 이미지
앨리삵

앨리삵입니다.

Rss feed Tistory
Graphics Note 2013.10.06 22:28

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
Delaunay triangulation in 2D  (1) 2013.10.06
외곽선 검출  (0) 2013.08.27
perspective projection  (3) 2013.07.19
[Mathematics] rotate model using quaternion  (4) 2013.07.11
  • 들로네 2017.04.22 14:35 신고 ADDR 수정/삭제 답글

    좋은자료 감사합니다 죄송한데 코드부분에서 InCircumcircle이함수안에 쓰인 넓이* 원점과에 거리 왜 쓰신건지 알 수 있을까요?
    넓이에 굳이 선길이를 곱한부분에서 이해를 못하겟습니다

TOTAL 279,217 TODAY 183

티스토리 툴바