Voronoi Diagram

Voronoi Diagram

• 컴퓨터 과학, 로봇공학 등 다양한 분야에서 널리 사용되는 공간 분할 기법이다.
• 정의
  • 주어진 평면(2D공간)에 여러 개의 점( 생성점 , seed)이 있을때, 각 점에서 가장 가까운 영역(도메인)을 해당점에 할당하는 공간분할이다.
    • 즉, 각 seed에서 자기 자신이 가장 가까운 영역만으로 공간을 나누는 것
    • 각 영역을 보로노이 셀이라고 부른다.

 

---

• 그림 설명
  • 그림에서 4개의 검은점이 2D평면에 배치되어 있다.
  • 이 점들 사이에는 "여러 개의 선분"이 그려져 있는데, 이 선들은 점들 사이의 공간을 분할하고 있다.
  • 이 선들은 점들과 점들 사이의 중간 위치를 기준으로 배치되어 있으며, 각각의 점에서 가까운 영역이 나눠져 있다.
• 각 점들을 seed라고 부른다. ( site라고도 부름 )
• 나눌때는 두 점에서 거리가 같은곳을 연결해서 만들어진다.(즉, 두 점을 잇는 선분에서 수직 이등분선을 그어줌  )

 

---

• 그림 설명
  • 회색은 장애물을 의미.
  • 하얀색은 free-space이다.
• Generalized Voronoi Graph ( GVG )
  • 일반적인 "점"이 아니라, "장애물의 경계"를 기준으로 만든 보로노이 다이어그램이다.
  • 장애물 경계로부터 같은 거리에 있는 점들의 집합이 선분이 된다.

 

---

• 보로노이 다이어그램을 장애물이 있는 2D환경에 적용한 예시이다.