들로네 삼각분할(Delaunay triangulation) & 보로노이 다이어그램(Voronoi diagram)

영상처리 2013.09.09 12:02

들로네 삼각분할(Delaunay Triangulation)과 보로노이 다이어그램(Voronoi diagram)이 무엇인지? 어디에 쓰이는지? 그리고 어떻게 구하는지에 대한 글입니다.



1. 참고 문헌(자료)


참고한 주요 자료들입니다.


[1] 위키피디아(Wikipedia): Delaunay triangulation, Voronoi diagram

[2] Steve Oudot의 그래픽스 강의자료: Delaunay Triangulation I & II (강추)

[3] O'Reilly, Learning OpenCV



2. 용어


Delaunay triangulation은 들로네 삼각분할, 들로네 삼각망, 들로네 삼각형 등으로 불리며 Voronoi diagram(보로노이 다이어그램)은 Voronoi tessellation(보로노이 테셀레이션), Voronoi decomposition, Voronoi partition라고도 불립니다.



3. 들로네 삼각분할(Delaunay triangulation)이란?


들로네 삼각분할은 평면위의 점들을 삼각형으로 연결하여 공간을 분할할 때, 이 삼각형들의 내각의 최소값이 최대가 되도록 하는 분할을 말합니다.



<그림 1>


예를 들어, 위 그림 (a)와 같이 점들이 있을 때 이 점들을 연결하여 삼각형을 만드는 방법은 (b), (c)와 같이 다양합니다. 들로네 삼각분할은 이러한 여러 삼각분할 중에서 (b)와 같이 각각의 삼각형들이 최대한 정삼각형에 가까운 즉, (c)와 같이 길쭉하고 홀쭉한 삼각형이 나오지 않도록 하는 분할을 말합니다.


들로네 삼각분할의 가장 중요한 특징중 하나는, "어떤 삼각형의 외접원도 그 삼각형의 세 꼭지점을 제외한 다른 어떤 점도 포함하지 않는다" 입니다 (이를 empty circumcircle property라고 부릅니다). 삼각형이 홀쭉하고 길수록 외접원도 커짐을 생각하면 됩니다. 위 그림에서 (b)는 이 조건을 만족하고 (c)는 만족하지 않음을 쉽게 확인할 수 있습니다.



4. 보로노이 다이어그램(Voronoi Diagram)이란?


보로노이 다이어그램은 어떤 시드 점(seed point)들과의 거리에 따라서 평면을 분할한 그림으로서, 평면위에 주어진 시드 점 p1, p2, ..., pn에 대한 보로노이 다이어그램은 평면위의 점들이 어떤 pi와 가장 가까운지에 따라서 영역을 분할한 다이어그램을 말합니다.


예를 들어, 아래 왼쪽 그림과 같은 사각형 공간에 10개의 시드 점 (검은색 점들)을 주면 오른쪽 그림과 같은 보로노이 다이어그램이 나옵니다.


<그림 2> 그림출처: 위키피디아[1]


쉽게 생각하면 어떤 주어진 땅이 있고 그 땅 위에 있는 10개의 국가간의 국경선을 나눈다고 했을 때, 각 지역이 어떤 나라와 가장 가까운지에 따라서 영토를 나눈 것이 보로노이 다이어그램입니다. 이러한 관점에서 보면 각각의 보로노이 영역은 각 시드 점의 세력권을 나타낸다고 볼 수 있으며 그 경계선은 힘과 힘의, 세력과 세력의 균형점을 나타낸다고 볼 수 있습니다.



5. 들로네 삼각분할과 보로노이 다이어그램의 관계


들로네 삼각분할과 보로노이 다이어그램은 서로 듀얼 이미지(dual image) 관계에 있으며 어느 하나를 알면 다른 하나도 곧바로 구할 수 있습니다.


[들로네->보로노이]

보로노이 다이어그램의 각 seed 점들을 가지고 들로네 삼각분할을 구한 후에, 구해진 삼각형들의 외접원들의 중심을 연결하면 보로노이 다이어그램이 나옵니다.


좀더 상세하게 말하면, 어떤 점을 공통의 꼭지점으로 하는 들로네 삼각형들의 외접원들의 중심을 순서대로 연결하면 이 공통점을 seed로 하는 보로노이 영역이 나옵니다.


[보로노이->들로네]

서로 인접한 보로노이 영역들간의 seed 점들을 연결하면 이 seed 점들에 대한 들로네 삼각분할이 얻어집니다.


<그림 3> 그림출처: 참고문헌 [3]


이와 같이 Delaunay triangulation과 Voronoi diagram은 서로 dual 관계에 있으며 어느 하나를 알면 다른 하나를 곧바로 구할 수 있기에 그 응용이나 계산 알고리즘도 거의 같은 거라고 생각하면 됩니다.


보로노이 다이어그램을 정의한 Voronoi와 들로네 삼각형을 고안한(1934) Delaunay 두 사람 모두 러시아 수학자입니다. 



<그림 4> 그림출처: 참고문헌 [2]



6. 자연에 존재하는 Delaunay triangulation / Voronoi diagram 예



<그림 5> 그림출처: 참고문헌 [2]



7. 응용


[데이터 클러스터링]

주어진 데이터 분포에서 유의미한 클러스터(cluster)를 뽑아내는 것은 data mining, classification 등에서 매우 어려운 문제 중 하나입니다 (특히 클러스터의 개수를 모르고 있을 때).


<그림 6> 그림출처: "an adaptive spatial clustering algorithm based on delaunay triangulation", CEUS 2011.


들로네 triangulation을 이용하면 이러한 클러스터링을 효과적으로 할 수 있는데, 먼저 데이터 점들을 Delaunay triangulation으로 연결한 후에 일정한 길이 이상의 긴 변들을 제거하고 남은 연결된 성분들을 구하면 됩니다.


[데이터 분포 밀도]

평면에 흩뿌려진 점들의 밀도를 수치화하는 용도로 사용되는 경우


<그림 7> DTFE(그림출처: 위키피디아[1])


그 방법은 어떤 점 p에서의 밀도를 점 p를 꼭지점으로 하는 주변 Delaunay 삼각형들의 면적의 합의 역수(밀도 = c/(s1+s2+...+sk))로 정의합니다. 그리고 이들 점에서의 밀도값을 보간(interpolation)함으로써 또한 공간 전체에서 밀도를 수치화하는 것입니다. 이러한 분포 밀도 수치화 방법을 Delaunay tessellation field estimator (DTFE)라고 하며, 주 응용은 우주 천체를 분석하는 용도라 합니다만 자세한 건 잘 모릅니다.

구체적인 예는 떠오르지 않지만 컴퓨터 비전에서도 나름 유용하게 활용될 수 있을 거라는 느낌이 듭니다.


[도로망 설계]

도시와 도시를 연결하는 도로망을 설계할 때, Delaunay triangulation이 하나의 참조모델로 활용될 수 있습니다.


<그림 8> 고대 로마의 도로망 (그림출처: 네이버 지식백과)


만일 n개의 도시가 있을 때 모든 도시와 도시를 직접 직선도로로 연결할 경우에는 총 nC2 = n(n-1)/2개의 도로가 필요합니다. 하지만, 모든 도시를 서로서로 직접 연결하는 것은 너무 비효율적이기 때문에 실제로는 일부 도로만을 연결하여 전체 도시들이 연결되도록 해야 할 것입니다.


이 경우 도시 A에서 도시 B로 이동할 때 직접 연결된 도로가 없다면 다른 도시들을 우회해서 이동해야 할 것입니다. 그런데, 이 때 중요한 점은 도시 A에서 도시 B로 이동하기 위해 이동한(우회한) 총 이동거리가 A-B 사이의 직선거리에 비해 최소화되도록 도로망을 설계하는 것일 것입니다.


만일 삼각분할 형태로 도로망을 설계한다고 했을 때, 들로네 삼각화를 이용하여 도로를 연결하면 우회에 따른 이동거리의 증가를 최소화할 수 있습니다.


[Minimum Spanning Tree(MST)]

Minimum Spanning Tree (MST)는 n개의 지점을 모든 점들이 서로 도달 가능하면서 전체 거리의 합이 최소가 되도록 연결한 트리 구조의 그래프입니다. MST는 주어진 지점들을 연결하는 최소 비용의 네트워크 회선망이나 파이프 망을 찾을 때 활용될 수 있습니다. 또한 잘 알려진 TSP (Traveling Salesman Problem 즉, n개의 도시를 최단 거리로 순회할 수 있는 방문 경로를 찾는 문제)도 MST를 활용하면 최적해 길이의 2배 이내에서의 근사해를 찾을 수 있습니다.


<그림 9> MST (그림출처: 위키피디아[1])


MST를 구하는데 들로네 triangulation을 활용하는 방법은, 먼저 주어진 점들에 대한 들로네 triangulation을 구하고 그 결과 그래프를 MST 구하는 알고리즘의 입력으로 사용하는 것입니다. 이렇게 하면 fully linked graph에서 직접 MST를 구하는 것보다 훨씬 효율적으로 MST를 구할 수 있게 됩니다. 단, 이는 들로네 triangulation이 항상 MST를 포함함을 전제로 하고 있는데 그 증명은 위키피디아를 참조하시기 바랍니다.


[Convex Hull 구하기]

어떤 점들의 집합에 대한 Convex Hull 이란 쉽게 생각하면 그 점들을 실로 팽팽하게 둘러쌌을 때 생기는 볼록(convex) 다각형입니다 (아래 그림에서 주황색 도형).


<그림 10>


Delaunay triangulation을 이용해서 convex hull을 구하는 방법은, 원래의 점들의 집합에 외부의 점 3개를 추가하여 들로네 삼각분할을 구한 후 어떤 점들이 새로 추가된 외부의 점과 삼각형을 이루었는지를 조사하면 됩니다. 그래서 새로 추가한 외부의 점과 삼각형을 형성한 점들을 연결하면 원래 점들에 대한 convex hull이 나옵니다. 단, 외부의 점을 잡을 때에는 원래 점들이 외부 점들을 잊는 삼각형에 모두 포함될 수 있도록 멀리 떨어진 점들로 잡아야 합니다.


[Nearest Neighbor 구하기]

어떤 점들의 집합에 대한 들로네 삼각분할이 있으면 nearest neighbor를 곧바로 구할 수 있게 됩니다. 예를 들어, 아래 그림에서 p의 nearest neighbor를 구하고 싶으면 점 p와 연결된 edge들만 조사하면 이들 중에 nearest neighbor가 존재하게 됩니다.


<그림 11> 그림출처: 참고문헌[2]


즉, 원래는 모든 점들과 일일히 거리를 비교해 봐야 하겠지만 들로네 삼각분할이 있으면 그 점과 연결된 점들과의 거리만 조사하면 된다는 의미입니다.


또한 k-nearest neighbor를 구할 때에도 들로네 삼각망에서 직접 연결된 점들로부터 시작해서 tree 형태로 점차 탐색범위를 확장해가면 됩니다.


[Reconstruction]

포인트 클라우드(point cloud)로부터 물체의 3D 입체를 모델링하여 복원할 때에도 Delaunay triangulation이 활용될 수 있습니다. 하지만 이 경우에는 삼각형은 사면체로, 원은 구로 확장된 버전의 Delaunay triangulation을 이용해야 합니다.


<그림 12> 그림출처: 참고문헌 [2]



[물체에 대한 polygon mesh 생성]

들로네 삼각분할의 본연(?)의 응용이라 볼 수 있습니다. 3D 입체 물체의 표면을 폴리곤으로 모델링할 때 들로네 triangulation을 이용하면 표면위의 점들의 집합으로부터 nice(?)한 폴리곤 메쉬를 얻을 수 있습니다. 3D 입체 표면을 폴리곤으로 모델링하는 이유는 빠른 랜더링(rendering)이 가능하기 때문입니다.


<그림 13> 그림출처: N. Aghdaii et. al., "5-6-7 Meshes," Proc. of Graphics Interface, 2012.


[3D 일러스트레이션]

Jonathan Puckey라는 사람이 2008년도에 개발한 방법으로 Delaunay Raster라는 그래픽 툴이 있습니다. 이 기법은 Delaunay triangulation을 이용하여 입력 사진으로부터 입체감을 갖는 3D 일러스트를 생성하는 것으로서, 사용자가 사진위에 입력한 점들로부터 들로네 삼각분할을 이용한 폴리곤 메쉬를 생성하고 그 색상값을 삼각형 내의 평균 색상으로 설정하는 방법입니다 (관련 URL: http://jonathanpuckey.com/projects/delaunay-raster/)


<그림 14> 그림출처: http://jonathanpuckey.com/projects/delaunay-raster/


[로봇 네비게이션]

로봇이 길을 찾고 목적지까지 이동할 때, 주변 장애물과 부딪히지 않고 안전한 길을 찾는 것이 무엇보다도 중요합니다. 보로노이 다이어그램을 이용하여 이동경로를 생성하면 공간의 가장 빈 곳을 따라서 이동하기 때문에 안전성을 확보할 수 있습니다.


<그림 15> 그림출처: 참고문헌 [2]



8. 들로네 삼각분할 알고리즘


들로네 삼각분할을 구하는 알고리즘은 크게 incremental 알고리즘과 divide and conquer 알고리즘으로 나눌 수 있습니다. 두 알고리즘의 속도는 O(n log n)이라고 합니다.


Incremental 알고리즘은 점들을 하나씩 추가해 가면서 점진적으로 분할을 완성하는 방식이고, divide & conquer 방식은 입력 점들을 recursive하게 두 그룹으로 나누고 각각의 그룹에 대한 들로네 삼각분할을 얻은 후에 다시 두 그룹을 합치는 방식입니다.


Divide & conquer 방식이 들로네 삼각분할 알고리즘 중 가장 빠른 방식이라고 합니다. 하지만 사용자와 인터렉티브하게 mesh 작업을 할 때에는 incremental 방식이 보다 적합할 것입니다.


8.1 Incremental 알고리즘


incremental 알고리즘을 이해하기 위해서는 먼저 flipping에 대해 알아야 합니다. 어떤 사각형을 대각선을 따라 두개의 삼각형으로 나누는 방법은 2가지가 있습니다. 이 때, 만일 어느 한 분할이 Delaunay 조건을 만족하지 않는다면 다른 대각선 방향으로의 분할은 반드시 Delaunay 조건을 만족하게 됩니다. 이와 같이 분할 방향을 바꾸어서 Delaunay 조건을 만족시켜 나가는 것을 flipping이라고 합니다.


<그림 16> 그림출처: 위키피디아[1]


가장 기본적인 incremental 알고리즘은 앞서 설명한 Convex Hull 구하기 응용에서처럼 먼저 원래 점들로부터 무한히 멀리 떨어진 외부의 3 점(아래 그림의 녹색 점들)을 설정한 후에, 하나씩 원래 점들을 추가하면서 Delaunay triangulation 조건을 만족하도록 삼각분할을 조정하는 형식으로 진행합니다.


<그림 16>


먼저, 현재 새로 추가된 점을 포함하는 삼각형의 세 꼭지점과 새로 추가된 점을 연결하여 새로운 분할을 만듭니다 (그림의 오렌지 색). 이후 새로 추가된 삼각형들과 맞닿은 삼각형들에 대해 차례로 flip 알고리즘을 적용하여 모든 삼각형들이 Delaunay 조건을 만족하도록 합니다 (empty circumcircle condition). 예를 들어, 위 그림에서 ABCD에 대해 조건을 검사해서 만족하지 않는다면 분할 방향을 BD에서 AC로 바꾸어 줍니다. 분할 방향이 변경된 경우에만 변경된 삼각형들과 인접한 삼각형들에 대해서 flipping 검사가 전파됩니다.


8.2 Divide and Conquer 알고리즘


Divide and conquer 방식은 원래의 입력 점들을 하나의 직선을 경계로 두 그룹으로 나누고, 각각의 그룹은 또 다른 직선으로 다시 세부 그룹으로 나누는 방식으로 recursive하게 그룹을 나누되, 각 그룹에 속한 점의 개수가 3개 이하일 때까지 분항을 진행합니다.


<그림 17> 그림출처: 참고문헌 [2]


이후, 각 그룹에서 들로네 삼각분할을 구한 후, 그룹들을 다시 합쳐나가면서 전체적으로 들로네 조건을 만족하도록 분할을 구하는 방식입니다. 두 그룹의 Delaunay 삼각분할을 합치는 세부적인 내용에 대해서는 관련 논문 등을 참고하시기 바랍니다.


☞ 참고로 저는 그래픽스 쪽 전공이 아니며 이 글에 있는 내용 이상은 잘 알지 못합니다. 한 방문자분의 요청의 의해 작성한 글로서 관련 내용이 흥미로운 점이 많아서 저도 같이 공부를 할 겸해서 작성한 글입니다.


by 다크 프로그래머


저작자 표시 비영리 변경 금지
신고
  • 이전 댓글 더보기
  • 성도 2015.05.11 17:41 신고 ADDR 수정/삭제 답글

    고등학생입니다.. 특강시간에 보로노이 다이어그램에 대하여 세미논문을 쓰는데 퍼가도 될까요?..인터넷을 찾아봐도 이만한 곳이 없네요..

    • BlogIcon 다크pgmr 2015.05.12 06:42 신고 수정/삭제

      네, 출처를 밝히고 인용하시면 됩니다. 하지만 논문이라고 한다면 자신의 언어로 자신이 이해한 내용을 적는 것이 좀더 의미가 있을 것 같습니다.

  • 비젼 2015.05.27 00:11 신고 ADDR 수정/삭제 답글

    안녕하세요 다크님.
    매번 이곳에서 많은 정보를 얻는데, 이번 이 글을 통해서도 좋은 글 얻네요ㅠㅠ 고맙습니다ㅠ
    다름이 아니라, Algorithm 파트에서 두 가지를 설명해주셨는데,
    속도는 n log n으로 같은데, 왜... Divide & Conquer 방식이 더 빠른지 알 수 있을까요??

    • BlogIcon 다크pgmr 2015.05.27 07:45 신고 수정/삭제

      안녕하세요. 저도 명확한 설명은 드리지 못합니다. 다만, 어떤 알고리즘의 속도가 O(nlogn)라는 말은 문제의 크기(n)에 따라 알고리즘 실행속도가 nlogn에 비례(상수배)하여 증가한다는 의미입니다. 따라서, 같은 O(nlogn) 알고리즘이라 하더라도 실제 실행속도는 큰 차이가 있을 수 있습니다 (실행속도가 cnlogn + k인 알고리즘을 모두 O(nlogn) 알고리즘이라고 함. c, k는 상수).

    • 비젼 2015.05.27 12:43 신고 수정/삭제

      감사합니다! 그런데 다른 곳에서는 속도라고 하기보다는 복잡도(Time Complexity)라는 말을 쓰기도 하더라고요. 그래서 개념을 잘 이해를 못하고 있었네요. 다크님 설명 들으니 이제 좀 이해가 갑니다! ㅋㅋ

      생각해보면, 같은 방식이라도 사용하는 용도와 데이터에 따라, 속도의 차이가 있을 수도 있겠다는 생각도 드네요.;;

      무튼 좋은 답변 감사합니다!

    • BlogIcon 다크pgmr 2015.05.27 14:25 신고 수정/삭제

      네, 시간 복잡도가 맞는 말인데 제가 표현상 그냥 속도라고 했습니다 ^^;

  • 안녕하세요 2015.06.27 23:16 신고 ADDR 수정/삭제 답글

    들로네 triangulation을 이용해 MST구하는 법을 조금 더 자세히 설명 해 주실 수 있으신가요???ㅠㅠ

    • BlogIcon 다크pgmr 2015.06.29 09:32 신고 수정/삭제

      안녕하세요. 본문 글에서 설명한 바 그대로입니다. 주어진 점들이 있을 때, 먼저 들로네 삼각분할을 실행합니다. 들로네 삼각분할의 결과로 나오는 점과 점 사이의 연결관계는 하나의 그래프로 볼 수 있습니다. 이 그래프를 일반적인 MST 알고리즘의 입력으로 사용하여 이 연결관계 내에서만 MST를 찾는 방식입니다.

  • 대학생 2015.07.27 16:34 신고 ADDR 수정/삭제 답글

    혹시 들로네 삼각분할이나 보로노이 다이어그램을 실행해볼 수 있는 예제코드 같은거 없을까요..?C로 구현되어 있는걸 찾아볼수가 없네요 ㅠㅠ

    • BlogIcon 다크pgmr 2015.07.27 18:10 신고 수정/삭제

      저도 직접 돌려본 것은 아니라서 코드는 잘 모르겠습니다.

  • rewqrewqrt@gmail.com 2015.08.08 02:27 신고 ADDR 수정/삭제 답글

    설명과 참고자료 모두 정말 잘 읽었습니다.

    많은 예시가 이해에 큰 도움이 되었습니다.

    감사드립니다.

  • triangulation찢어발기리 2016.01.06 09:34 신고 ADDR 수정/삭제 답글

    이 글을 읽는 순간 천국에 온듯하였다. 모든 의문이 풀리고 나를 다시 돌아보게 되었다.
    수학과 알고리즘 사이의 작은 틈 마저 메꿔버린 정리이지 않았나 생각한다.
    openGL ES에서 Tessellation 기능이 막히면서 저와 같은 많은 이들이 Triangulation 에 대해 공부하지만 쉽사리 다가갈 수 없는 넘사벽에 가로막혔는데, 이 글을 읽고 많은 공부가 되었습니다. 감사합니다. tistory 가 아니라 naver blog 였다면 당신을 서이추하여 매일 인사드리러 왔을 것입니다.

  • Jamie H. 2016.01.31 00:14 신고 ADDR 수정/삭제 답글

    보로노이 다이어그램과 들로네 삼각분할에 대해서 이해가 안 되는 부분이 많이 있었는데, 이 글 덕분에 도움이 많이 된 것 같습니다.
    감사합니다^^

  • vpd2003 2016.03.03 20:19 신고 ADDR 수정/삭제 답글

    와.. 오늘 처음 들어와봤는데 진짜 좋은 글이네요.. 덧글이 쓰고 싶어지게 합니다! 좋은 정보 감사합니다!

  • 갱해이 2016.03.17 18:33 신고 ADDR 수정/삭제 답글

    안녕하세요. 다크pgmr님. 정말 글 잘 읽었습니다.
    글 중에 [물체에 대한 Polygon Mesh 생성]에 대해 여쭤보려고합니다.
    저는 3D스캐너를 제작중인 학부생입니다. 레이저 - 웹캠으로 만들고 있는데 현재는 OpenCV에서 좌표값을 얻었습니다.
    제가 생각하는 렌더링 과정은 OpenCV를 이용해서 물체에 비춰진 레이저라인을 검출하여 좌표값들을 추출하였고, 그 좌표값들을 glVertex3f(x,y,z); 함수에 x,y는 그대로 대입하여 주고, z값은 일정값을 증가시켜 각도로 표현하면 되지않나 싶습니다.
    제가 궁금한 것은 위에 방법처럼 좌표값을 glVertex3f(x,y,z);에 계속 넣어줘서 z가 0~360도 이렇게 되면 들로네삼각법(?)을 이용해 점들을 삼각형으로 연결하여 하나의 폴리곤을 생성하고 싶은데요.
    어떻게 하는건지 자세히 좀 알려주실 수 있으신가요?
    어떤 함수를 이용하는지.. 예제도 잘 안나오더라구요.. 위 과정을.. 조금만 더 자세히 알고 싶은데 어떻게 하면 될까요..ㅜㅜ

  • 충대생 2016.03.18 11:40 신고 ADDR 수정/삭제 답글

    정말 멋진 글입니다.

    많은 배움 얻고갑니다.

  • 밴드 2016.09.13 16:05 신고 ADDR 수정/삭제 답글

    좋은 자료 잘 보고 갑니다. 제가 보로노이다이어그램과 관련한 논문을 쓰는데, 사진자료가 많이 부족해서 수록해도 괜찮을까요? 참고문헌에는 반드시 넣겠습니다. 자료 정리하신걸 보니 대단하다는 생각이 듭니다~^^

  • 염소 2017.04.17 17:20 신고 ADDR 수정/삭제 답글

    좋은 자료 감사합니다.. 한번 읽어선 잘 이해가 안되어서.. 앞으로 몇번 더 읽어 봐야겠네요.

  • 초보 2017.04.22 15:06 신고 ADDR 수정/삭제 답글

    매번 좋은 자료 감사합니다. 덕분에 많이 배워갑니다.
    그런데 제가 들로네 삼각형 알고리즘 코드를 구했는데
    InCircumcircle()함수를 쓰는데 여기서 기존에 존재하는 삼각형의 점3개와 내부에 새로 추가된 점을 이용해서
    V1(삼각형의1번점),V2(삼각형의1번점),V3(삼각형의1번점),Vx(새로추가된점)
    해서 (V1*V1)*(V2,V3,Vx를 이용한 원의 넓이)-(V2*V2)*(V3,V1,V를 이용한 원의넓이)+
    (V3*V3)*(V1,V2,Vx를 이용한원의 넓이) -(Vx*Vx)(V1,V2,V3을 이용한 원의 넓이) 한값이 >0크면 참을 아니면 거짓을 리턴해주는데 이게 무슨 의미가 있는 지 도저히 모르겠는데 혹시 도움 주실수 있나요?

    • 초보 2017.04.22 15:08 신고 수정/삭제

      느낌상 3점과 새로 내부에 추가된 점들을 기준으로 삼각형을 나눌때 외접원을 비교하는거 같긴한데 +-+- 의 더하는 순서는 어디서 나오고 원의 넓이와 원점과의 선의 길이를 곱하는 이유를 모르겟습니다

    • BlogIcon 다크pgmr 2017.04.22 23:36 신고 수정/삭제

      수식은 잘 모르겠지만 InCircumcircle() 함수는 어느 한 점이 나머지 세 점에 의해 형성되는 원의 내부에 포함되는지 여부를 판단하는 함수로 보입니다.

    • 초보 2017.04.23 09:43 신고 수정/삭제

      답변감사합니다

  • ㅁㄴㅇ 2017.05.13 23:47 신고 ADDR 수정/삭제 답글

    세상에 마상에... 들로네 삼각분할 응용이 끝이 없군요

  • 창현 2017.08.10 14:39 신고 ADDR 수정/삭제 답글

    정말 감사합니다! 비전 공부할때마다 들르는데 정말 지식 이해의 깊이에 감탄합니다. !

  • 이진우 2017.09.16 03:29 신고 ADDR 수정/삭제 답글

    보로노이 다이어그램을 인터넷에 치면 로봇이나 GPS의 최단 경로를 찾는데 활용한다고 나옵니다. 또 로봇네이게이션에서 최단경로가 아닌 길을 선택 한 것 같아 보여서 작성하신 도로망 설계와 로봇 네이게이션을 결합했을때 최단경로를 찾을 수 있는건가요?
    또 이것이 도로의 자동차에 보로노이 다이어그램을 연관지어 설계할 ㅅ수 있을까요?

    • BlogIcon 다크pgmr 2017.09.18 12:07 신고 수정/삭제

      저도 아는 건 글에 적은게 다라서.. 구체적인 사례에 대해서는 따로 공부를 하셔야 할 것 같습니다. 다만 제가 알기로 많은 기하학적 계산 문제들을 보로노이 이론을 이용하여 굉장히 효율적으로 구현할 수 있는 것으로 알고 있습니다.

    • 2017.10.09 01:26 수정/삭제

      비밀댓글입니다

  • 2017.10.09 01:24 ADDR 수정/삭제 답글

    비밀댓글입니다

    • BlogIcon 다크pgmr 2017.10.09 15:19 신고 수정/삭제

      네, 메일 주소는 옆에 블로그 매 그림 위쪽에 표기되어 있습니다. ^^

  • 이진우 2017.10.09 23:01 신고 ADDR 수정/삭제 답글


    데이터 클러스터링



    '들로네 triangulation을 이용하면 이러한 클러스터링을 효과적으로 할 수 있는데,

    ​먼저 데이터 점들을 Delaunay triangulation으로 연결한 후에 일정한 길이 이상의 긴 변들을 제거하고 남은 연결된 성분들을 구하면 됩니다.'

    ​데이터에 숨겨진 규칙이나 패턴을 찾아낼때 사용하는 걸로 아는데



    ​어떤식으로 효과적 이다는 것 인지 알 수 있을까요?



    ​도로망 설계



    ​만일 삼각분할 형태로 도로망을 설계한다고 했을 때, 들로네 삼각화를 이용하여 도로를 연결하면 우회에 따른 이동거리의 증가를 최소화할 수 있습니다.
    왜 델로이 삼각형을 이용하면 이동거리의 증가를 최소로 유지하나요?

    • BlogIcon 다크pgmr 2017.10.10 09:13 신고 수정/삭제

      저는 이쪽 분야 전공자가 아니라서 자세한 것은 모릅니다. 필요하신 내용에 대해서는 직접 깊게 공부하시기 바랍니다. 보통 효율적이라는 의미는 연산시간이 빠르거나 메모리 사용량이 적다는 것을 의미합니다. 보로노이 다이어그램은 거의 선형시간에 계산이 가능하니(n log n) 어떤 문제를 보로노이 다이어그램 문제로 치환해서 풀 수 있다면 효율적인 구현이 가능한 셈입니다.

  • CV 2017.10.16 22:38 신고 ADDR 수정/삭제 답글

    역시 영어로 설명된 글들을 보다가 한글로 보니 이해가 빠르네요. 정리해주신 덕분에 쉽게 배워 갑니다. 고맙습니다.

  • Opt 2017.11.01 11:13 신고 ADDR 수정/삭제 답글

    한글로 친절하게 설명된 글 잘 배워갑니다. 감사합니다