'Delaunay triangulation'에 해당되는 글 1건

  1. 2011.12.05 Voronoi diagram (1)
2011.12.05 20:58
[Voronoi diagram]

알고리즘에 관심이 가게 되서 그중 제일 유명한것 같던 보로노이 다이어그램이 뭔지 알아보았다. 

 

출처 : http://blog.naver.com/vector3?Redirect=Log&logNo=60023938785 

이 알고리즘은 어따가 써먹냐 하면, 3D 폴리곤을 조금더 세분화? 또는 디자인 구조에 많이들 적용한다.

왜 써먹을까? 바로 이 구조가 자연에서 쉽게 볼 수 있는 구조란 것이다.

예를들어, 잠자리 날개를 자세히 보면 어느정도 규칙성을 가지고 있다는걸 볼 수 있다.


출처 : http://blog.naver.com/againkaizak?Redirect=Log&logNo=60125630051
SAMSUNG TECHWIN CO., LTD. | VLUU L83T/ Samsung L83T | Normal program | Spot | 1/20sec | F/4.0 | 0.00 EV | 11.1mm | ISO-100 | Flash did not fire | 2008:03:26 13:17:29

출처 : http://blog.naver.com/seunggo12?Redirect=Log&logNo=50048154171


보면, 상당히 구조가 규칙성을 가지고 잘 정돈되어 있고(?) 크고(엥?) 아름답다는걸 알 수 있다.ㅎ

 이걸 적용한 보트, 집등등 있던데 예쁘긴 하다.

일단, 이 알고리즘의 개념을 위키에서 찾아 보았다. (한국어판엔 없어서 영문판에서...-_-) 

In mathematics, a Voronoi diagram is a special kind of decomposition of a given space, e.g., a metric space, determined by distances to a specified family of objects (subsets) in the space. These objects are usually called the sites or the generators (but other names such as "seeds" are in use) and to each such an object one associates a corresponding Voronoi cell, namely the set of all points in the given space whose distance to the given object is not greater than their distance to the other objects. It is named after Georgy Voronoi, and is also called a Voronoi tessellation, a Voronoi decomposition, or a Dirichlet tessellation(after Lejeune Dirichlet). Voronoi diagrams can be found in a large number of fields in science and technology, even in art, and they have found numerous practical and theoretical applications [1][2]. 


 수학에서 보로노이 다이어그램은 어떠한 공간을 특정 집합에 있는 오브젝트간의 거리에 의해서 나누는 방법중 하나입니다.
이 오브젝트(이하 시드)는  보통 사이트 또는 제너레이터라고 부르고(하지만 시드라고도 부릅니다.) 각 
시드는 보로노이 셀과 관련되어 상호작용합니다.

나머지 내용은 다음시간(?)에..쿨럭..


차라리 다른 블로그에 있던 내용을 인용하는게 편하겠다. 

두 점 p와 q 사이의 유클리안 거리를 dist(p, q)라 하자.

한 평면상에 n개의 분리된 점들의 집합 P를 P={p1, p2, p3, ..., pn}이라고 하자.

P의 Voronoi Diagram은 그 평면을 n개의 cell로 나누는 것이다. P에 있는 각각의 점에 대해서
만일, dist(pi, q) < dist(pj, q) 를 만족하면 q는 p1 cell에 포함된다.
평면상의 점들은 P에 있는 점들 중 가장 가까운 점이 속한 cell에 포함된다. 이런식으로 한 평면을 분할하는 방법을 Voronoi Diagram이라 한다.


// 여기서 q는 뭐지? 아마 DT를 구한뒤, DT의 각 삼각형의 외심을 가리키는게 아닐까,,, 


출처 : http://blog.naver.com/vector3?Redirect=Log&logNo=60023938785


여기서 DT가 무엇일까?

DT란, Delaunay Triangulation인데, 어떤 점 집합을 삼각화 한 것이다. 
File:Delaunay Voronoi.png
(출처 : 위키)

이 그림을 보면, 각 검은색 점(시드)들을이었는데 이 이어논 삼각형들을 DT라 부른다. 
또 이 DT를 가지고 빨간점을 만들었는데, 이 빨간점이 해당 삼각형의 외심이다.
그리고 각 외심을 이어 만든 공간분할이 보로노이 다이어그램이다. 

이렇게 보로노이 알고리즘을 그려보면 DT와 다이어그램이 서로 관련이 있다. 그러니깐 DT가 있으면 보로노이 다이어그램을 그릴 수 있고, 다이어그램이 있으면 DT를 구할 수 있다.

그렇다면, 구현을 하기 위해선 어떤 점 집합이 있어야 하고 이 집합의 DT를 구한뒤, DT를 가지고 보로노이 다이어 그램을 그리면 된다.

여기서 DT를 구하는 방법은 여러가지가 있다.

많이 쓰는 걸론, IDT(Incremental) 가 있다. 
(Fortune's algorithm도 있지만, 이 알고리즘은 이해하기도,,, 소스도 너무 길어서 패스....ㅠㅠ)



그리고,,,,부대에서 연구(?ㅋ) 했을땐 궁금했었던게 있었다.

바로 시드가 4개가 있을때의 문제이다. 이 시드가 마름모 꼴로 되어 있는데, 중간에 그을 선을 가로로 할지 아니면 세로로 할지에 대한문제,,

그래서 위키에서 찾아보니,,,,
 File:Delaunay geometry.png
알파+감마의 합이 180이 넘지 않으면 A와 C를 이으면된다. 이 그림은 180이 넘으므로, B와 D를 이어주었다.
저작자 표시 비영리 변경 금지
신고
크리에이티브 커먼즈 라이선스
Creative Commons License

'Math/Pahycis/Algorithm' 카테고리의 다른 글

[알고리즘] 카프-라빈 알고리즘 구현해보기  (2) 2012.02.09
Shortest Path Algorithm  (1) 2011.12.05
Voronoi diagram  (1) 2011.12.05
Trackback 0 Comment 1
  1. Favicon of http://estellenotes.tistory.com BlogIcon 에스텔시아 2011.12.11 00:20 신고 address edit & del reply

    우리가 영어권이었으면 번역이라는 번거로운 과정따윈 생략했을텐데...항상 언어영역이 문제란 말이야..



티스토리 툴바