OpenCV 드로네 삼각분할과 보로노이를 이용한 2D 공간 분석 방법

1. Planar Subdivision의 정의

Planar Subdivision은 2차원 평면 위의 점(Point)들을 기반으로 영역을 분할하여, 각 점을 연결하는 구조를 효율적으로 관리하는 기법입니다. OpenCV에서는 이 기능을 Subdiv2D 클래스로 제공하며, 주로 드로네(Delaunay) 삼각분할(Delaunay Triangulation)과 보로노이 다이어그램(Voronoi Diagram) 생성을 위해 사용됩니다.

이 기법을 활용하면, 점 집합을 기반으로 한 공간 분할·거리 계산·지형 분석·메시(mesh) 생성 등 다양한 영상처리 및 컴퓨터 비전 분야 작업을 수행할 수 있습니다.

2. OpenCV Planar Subdivision의 구조와 동작 설명

OpenCV의 Subdiv2D는 Delaunay 삼각분할 알고리즘을 중심으로 설계된 데이터 구조로, 점을 하나씩 삽입하면서 삼각형을 자동으로 갱신해 나가는 방식입니다. 주요 특징은 다음과 같습니다.

(1) Delaunay Triangulation

- 어떤 삼각형도 외접원 안에 다른 점이 포함되지 않는 형태
- 면적이 고르게 유지되고, 복잡한 형태에서도 안정적인 메시 생성
- 컴퓨터 비전, 3D 복원, 지형 예측 등에 널리 사용

(2) Voronoi Diagram

- 각 점을 중심으로 영향 영역을 나누는 구조
- 영역 기반 분석, 거리 기반 분류, 경계 검출 등에 활용
- Subdiv2D 객체에서 자동으로 계산 가능

(3) Subdiv2D 동작 방식

1. 사각형 영역(Rect)을 기준으로 초기화
2. insert()로 점을 하나씩 삽입
3. 내부에서 삼각형 구조, 간선 등이 자동 업데이트
4. getTriangleList() 또는 getVoronoiFacetList()로 결과 추출

(4) 주요 장점

- 점을 연속적으로 추가해도 안정적인 구조 유지
- OpenCV 내부 구현으로 속도와 정확성이 검증됨
- 이미지 기반 분석뿐 아니라 그래프 기반 문제에도 사용 가능

3. 활용 예제 (Python)

예제 1: Delaunay Triangulation 생성

import cv2
import numpy as np

rect = (0, 0, 600, 400)
subdiv = cv2.Subdiv2D(rect)

points = [(50,50), (200,80), (300,200), (150,300), (400,150), (500,350)]
for p in points:
    subdiv.insert(p)

triangles = subdiv.getTriangleList()

img = np.zeros((400, 600, 3), dtype=np.uint8)

for t in triangles:
    pt1 = (int(t[0]), int(t[1]))
    pt2 = (int(t[2]), int(t[3]))
    pt3 = (int(t[4]), int(t[5]))
    cv2.line(img, pt1, pt2, (255,255,255), 1)
    cv2.line(img, pt2, pt3, (255,255,255), 1)
    cv2.line(img, pt3, pt1, (255,255,255), 1)

cv2.imshow("Delaunay Triangulation", img)
cv2.waitKey(0)

예제 2: Voronoi Diagram 추출

facetList, centers = subdiv.getVoronoiFacetList([])

img2 = np.zeros((400, 600, 3), dtype=np.uint8)

for i in range(len(facetList)):
    poly = facetList[i].astype(int)
    cv2.fillConvexPoly(img2, poly, (80, 80, 160))
    cv2.polylines(img2, [poly], True, (255,255,255), 1)
    
    center = centers[i].astype(int)
    cv2.circle(img2, center, 3, (0,255,0), -1)

cv2.imshow("Voronoi Diagram", img2)
cv2.waitKey(0)