[Study] 1. Spatial Tessellation (Delaunay & Voronoi Triangulation)

2020.08.15 Mechanical Design Story 

-1- Delaunay & Voronoi Triangulation

들로네 삼각분할과 보로노이 다이어그램에 관심을 가진 것은 Biomimicry에 관심을 가진 이후다.

기계공학을 전공하며 "제품에 생물적 특성, 자연적 특성을 이용한 생체모방을 적용하고 싶다."는 개인적 욕심이 있었고 이를 이용하여 몇몇 디자인 및 설계 공모전에 참가했다.

다행히도 겉핥기로 공부한 내용을 접목시킨 작품이 좋은 평가를 받았고 나에게는 큰 도움이 되었다.

 

당시 겉핥기로 공부했던 사항들을 하나하나 짚고 넘어갈 필요성을 느꼈고 그 시작을 보로노이 다이어그램으로 정했다.

 

들어가기에 앞서 

https://darkpgmr.tistory.com/96

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

이해가 안가던 부분을 참고한 티스토리 블로그다. 상기 블로그를 먼저 방문하시고 제 글을 읽어주시면 이해가 더 빠를것 같습니다.

 

[배경지식]

1-(1) Convex Hull

컨벡스 헐 알고리즘은 2차원 평면상 여러개의 점이 있을 때 그 점 중에서 일부를 이용하여 볼록 다각형을 만들되 다각형 내부 모든 점을 포함시키는 것을 의미한다.

 

쉽게 말하자면 어떤 점들의 집합에 대한 Convex Hull이란 그 점들을 실로 팽팽하게 둘러쌌을 때 생기는 볼록 다각형이다.

CONVEX HULL 출처 : https://jeffe.cs.illinois.edu/convexhull

 

Suppose we are given a set P of n points in the plane, and we want to compute something called

the convex hull of P.  Intuitively, the convex hull is what you get by driving a nail into the plane at each point and then wrapping a piece of string around the nail.
In short, The convex hull is the smallest convex polygon containing the points.

 

1-(2) Triangulation

출처: Delaunay Triangulations (slides mostly by Glenn Eguchi),https://web-cert.mit.edu/

2차원 실수공간 R^2에 높이가 정해진 점들이 존재한다고 생각해보자.

각각의 점들을 기준으로 영역을 나눈다고 생각하면 자연스럽지 않은 형상이 발생할 수 있는데, 이를 개선하기 위한 방법으로 Triangualtion이 사용된다. (첫번째, 두번째 그림 참조)

 

Determine a triangulation of A in R^2, then raise points to desired height

Triangulation : planar subdivision whose bounded faces are triangles with vertices from A

 

1-(3) BISTELLA FLIP

Bistella flip 출처: Computational Geometry Lecture 13: Delaunay triangulations and Voronoi diagrams,https://youtu.be/7VcuKj1_nHA

 

Delaunay Triangulations (slides mostly by Glenn Eguchi),https://web-cert.mit.edu/

Triangulation에서 중요한 것은 최적의 삼각형을 형성하는 것이다.

네 가지 종류가 있는 것으로 알고있는데, 이 가운데 Triangulation이 (1)Angle optimal, (2) Legal인 경우가 있다.

(1. Triangulation이 angle optimal, 2. legal, 3. Delaunay, 4. Triangulation is the convex hull of lift of points in parabola)

출처:Computational Geometry Lecture 13: Delaunay triangulations and Voronoi diagrams,https://youtu.be/7VcuKj1_nHA

상기 강의자료에 설명된 것 처럼 Legal인 경우를 만들기 위해 Flipping을 사용한다.

굉장히 넙적한 삼각형 한쌍이 마주보고 있는 그림을 생각해보자. (상기 사진의 좌측 도형)

A와 B에 연결된 선 대신, D와 C를 연결하면 우측 삼각형을 만들 수 있다. 이러한 과정이 Flipping이다.

이 과정을 통해서 angle vector를 개선할 수 있고 각 삼각형의 외접원에 하나의 삼각형만이 있어야한다는 들로네 삼각형의 전제조건을 만족시킬 수 있게 된다. 

 

If the smallest of all these vectors in larger than the smallest of all of these vectors

than this was a good by stella flip. The reason why we do Bistella Flip (Flipping) is that improve the angle vector of a triangulation. And do this flipping until you stuck there is no any other flip avail.

 

Imagine, I have a triangle, a pair of triangles that Fig 1. I could just flip this edge, so that instead of connecting A to B, Now I connect C to D

 

2. Voronoi Diagram

 

보로노이 다이어그램

-우크라이나 수학자 보로노이 (Georgy Voronoy)에 의해 정의된 보로노이 다이어그램

보로노이 다이어그램(Voronoi diagram)은 평면을 특정 점까지의 거리가 가장 가까운 점의 집합으로 분할한 그림이다.

[출처: 위키백과] https://ko.wikipedia.org/wiki/%EB%B3%B4%EB%A1%9C%EB%85%B8%EC%9D%B4_%EB%8B%A4%EC%9D%B4%EC%96%B4%EA%B7%B8%EB%9E%A8

보로노이 다이어그램 - 위키백과, 우리 모두의 백과사전

보로노이 다이어그램은 공간 스스로 그것이 속한 환경의 변화에 요구되는 것과 반응 속성을 활발히 소통하는 시스템을 지향한다.

 

보로노이 다이어그램은 마이크로 테크놀로지에 있어서 분자구조의 연산 등에 응용될 뿐만 아니라 기하학적 구조에서 활발하였기 때문에 공간 생성과도 상당한 연관이 있다.

[출처 : 박종진; 전한종. 3 차원 보로노이 다이어그램을 활용한건축 디자인 생성 프로세스에 관한 연구.  한국 CAD/CAM 학회논문집 , 3, 14.5: 306-313.]

 

2-(1) 발생이론

보로노이 다이어그램은 점 데이터 P1.P2...Pn을 기준으로 보로노이 셀인 C(P1) C(P2)..C(Pn)으로 분할되게 된다.

 

임의의 점 Pi를 포함하는 보로노이 셀 C(Pi)영역 내의 점들은 다른 영역의 기준점에서의 거리보다 자신이 속한 영역의 기준까지의 거리가 제일 가ᄁᆞᆸ도록 최단 영역을 찾아내고 알고리즘을 다이어그램으로 표현한 것이다.

FIg 7. 2차원 보로노이 셀의 생성과정 출처 : 박종진; 전한종. 3 차원 보로노이 다이어그램을 활용한건축 디자인 생성 프로세스에 관한 연구.  한국 CAD/CAM 학회논문집 , 3, 14.5: 306-313.

 

2-(2) 하나의 보로노이 셀이 정의되는 5단계 (Ref. Fig.7)

가장 단순한 방법이 점들의 수직 이등분선을 이어서 보로노이 다이어그램을 만들 수 있다.

 

(1) 정점(셀의 정의) : 보로노이 다이어그램의 프로세스를 진행하기 전에 임의의 사각형 형태의 영역 내부에

(2) 하나의 기준점과 다른 정점 사이의 중심점을 이용한 수직이등분선 추출한다.
(3) 하나의 기준선과 다른 정점을 선정하고 이 두 점 사이의 중심점을 지나는 수직 이등분선을 구하는 과정을 진행하고

(4) 영역의 경계선과 수직이등분선과의 교차 여부 분석한다. (수직이등분선을 이용하여 영역 절단)

(5) 상기 (1)-(4) 과정을 반복하여 보로노이 셀을 생성할 수 있다.

 

3. Delaunay Triangualtion

GUIBAS, Leonidas. Basic algorithms and combinatorics in computational geometry. 1994.

Triangle is Delaunoi only if the circumcircle of any T which is in Triangulation.

And this T contains no other points in P(Convex hull).

 

계산기하학에서 평면의 점 집합 P의 델로네 삼각분할(Делоне三角分割, 영어: Delaunay triangulation) DT(P)는 DT(P)에 속하는 모든 삼각형의 외접원 내에 P에 속하는 어떤 점도 속하지 않도록 만든 삼각분할이다. 이 분야에 대한 연구를 했던 보리스 델로네의 이름에서 따왔다. 한, 최대한 정삼각형의 모양과 가깝게 분할한다는 특징이 있다.

[출처 : https://ko.wikipedia.org/wiki/%EB%8D%B8%EB%A1%9C%EB%84%A4_%EC%82%BC%EA%B0%81%EB%B6%84%ED%95%A0]

델로네 삼각분할 - 위키백과, 우리 모두의 백과사전

 

3-(1) Convex Hull of Delaunay Triangulation

GUIBAS, Leonidas. Basic algorithms and combinatorics in computational geometry. 1994.

 

P(x,y,z) : ax + by + cz + d = 0 

(x-x_o)^2 + (y-y_o)^2 -r^2 = 0

Plane : z -2(xx_o + yy_o) + (x_o^2 +y_o^2-r^2) = 0

 

평면에 세 점이 있다고 생각을 해보자. 우리는 이 점들을 포물면으로 투영시킬 수 있고, 투영된 점들이 하나의 반공간을 형성하게 된다. (Half-space : 유클리드 기하. 형상에서 반공간은 평면이 3차원 유클리드 공간을 나누는 두 부분 중 하나.)

그리고 이 세 점은 타원이든 원이든 외접원을 형성하게 되는데, 들로네 삼각형을 형성하지 않는, 즉 외접원 내에 다른 sites가 존재하는지 여부를 이용하여 Good or Bad Triangle을 판단할 수 있다.

 

4. Applications

보로노이 다이어그램과 들로네 삼각형은 효율적인 공간분할 방법으로써 과학, 공학, 건축 등 다양한 분야에 응용되고 있다. 일례로 내장고 내부에 온도센서 배치에 관해 소개할만한 특허기술이 있다.

보로노이 다각형을 이용한 저장고 내부의 센서 배치 방법, 한국식품연구원, 부산대학교 산학협력단, 출원번호 10-2012-0132300

한국식품연구원과 부산대학교 산학협력단에서 출원한 특허 : 보로노이 다각형을 이용한 저장고 내부의 센서 배치 방법은 보로노이 다이어그램을 이용한 좋은 사례라고 생각된다.

 

온도 급변지점과 같은 저장고 내부의 특정 위치에 센서를 배치하고, 이를 기준으로 보로노이 다이어그램을 적용한다.

이 방법으로 센싱 범위의 중첩 영역을 가급적 적게하면서 센서를 확산 배치함으로써 센서를 이동시킬 필요가 없으며 요구되는 센서의 수를 최소화할 수 있는 센서배치방법을 제안한다.

 

출원일자가 2012년인 것으로 보아서는 현재 보로노이 다이어그램을 이용한 기술은 상당히 보급된 것으로 생각된다.

 

5. References

1. https://darkpgmr.tistory.com/96

2. ko.wikipedia.org/wiki/델로네_삼각분할

3. ko.wikipedia.org/wiki/보로노이_다이어그램

4. 보로노이 다각형을 이용한 저장고 내부의 센서 배치 방법, 한국식품연구원, 부산대학교 산학협력단, 출원번호 10-2012-0132300

5. 박종진; 전한종. 3 차원 보로노이 다이어그램을 활용한건축 디자인 생성 프로세스에 관한 연구.  한국 CAD/CAM 학회논문집 , 3, 14.5: 306-313.

6. MIT OCW LECTURE Computational Geometry

7. Computational Geometry Lecture 13: Delaunay triangulations and Voronoi diagrams,https://youtu.be/7VcuKj1_nHA

8. IZMESTIEV, Ivan; KLEE, Steven; NOVIK, Isabella. Simplicial moves on balanced complexes. Advances in Mathematics, 2017, 320: 82-114.

9. Delaunay Triangulations (slides mostly by Glenn Eguchi),https://web-cert.mit.edu/