<img src="https://t1.daumcdn.net/cfile/tistory/192D454E50A1215329" height="240" width="320">
http://img835.imageshack.us/img835/6489/bbo2.gif
|
<img src="https://t1.daumcdn.net/cfile/tistory/192D454E50A1215329" height="240" width="320">
http://img835.imageshack.us/img835/6489/bbo2.gif
<img src="https://t1.daumcdn.net/cfile/tistory/18141A4E50A1183737" height="240" width="320">
http://img708.imageshack.us/img708/6695/bbo1.gif
출처 : http://quadflask.tistory.com/253
요약 :
------------------------------------------------------------------------------------------------------
알고리즘에 관심이 가게 되서 그중 제일 유명한것 같던 보로노이 다이어그램이 뭔지 알아보았다.
출처 : http://blog.naver.com/vector3?Redirect=Log&logNo=60023938785
이 알고리즘은 어따가 써먹냐 하면, 3D 폴리곤을 조금더 세분화? 또는 디자인 구조에 많이들 적용한다.
왜 써먹을까? 바로 이 구조가 자연에서 쉽게 볼 수 있는 구조란 것이다.
예를들어, 잠자리 날개를 자세히 보면 어느정도 규칙성을 가지고 있다는걸 볼 수 있다.
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