컴퓨터는 다각형을 삼각형으로 쪼갠다 (feat. Ear Clipping)

 
 

 

 

개요

우리가 눈으로 보는 도형은 사각형, 오각형, 심지어 원이나 구처럼 생겼지만,
컴퓨터 그래픽스의 세계에선 모든 도형이 결국 삼각형으로 쪼개집니다

왜일까요?
삼각형은 항상 평면 위에 존재하고, 수학적으로 안정적이며, GPU가 직접 처리할 수 있는 기본 단위이기 때문입니다.

 
이런 이유로 복잡한 다각형을 삼각형으로 나누는 과정, 즉 삼각화(Triangulation)는
컴퓨터 그래픽스, 게임, CAD, 심지어 로봇의 경로 탐색(Path Planning)까지 다양한 분야에서 사용됩니다.

 
이 글에서는 삼각화 알고리즘 중 하나인 Ear Clipping 알고리즘을 소개하고,
그 원리와 구현 방법, 시각화를 통해 삼각화 과정을 직접 따라가 보겠습니다.
 

그림 1

Ear Clipping 알고리즘을 수행하기 위해서는 폴리곤이 그림1의 simple polygon형태로 정의 되어야 합니다.
 

simple polygon의 정의

• 연속된 꼭짓점(Vertex)들이 서로 연결된 다각형으로, 꼭짓점이 아닌 다른 곳에서 교차하지 않아야 한다.
• 선분은 정렬되어 있어야 한다. (보통 다각형의 정점들이 반시계 방향으로 정렬된 것으로 가정)
• n개의 정점을 가진 다각형은 항상 n-2개의 삼각형으로 분해된다.

---

Ear Clipping

Ear(귀) 정의

• 귀는 연속된 세 정점 $V_{i-1}$, $V_i$, $V_{i+1}$으로 이루어진 삼각형으로, 다음 조건을 만족합니다.
  • 중앙 정점 Vi1V_{i1}Vi1​이 볼록(convex) 정점이어야 합니다.
  • 삼각형 내부에 다각형의 다른 정점이 없어야 합니다.
• 삼각형에서 가운데 있는 정점 $V_{i1}$​을 귀 꼭짓점(ear tip)이라 부르고, 나머지 두 정점을 잇는 선분을 대각선(diagonal)이라 합니다.
• 모든 삼각형은 항상 귀가 하나만 존재합니다(세 정점 중 아무 정점이나 귀 꼭짓점이 될 수 있음).
• 네 개 이상의 변을 가진 다각형은 항상 최소 두 개 이상의 귀를 가집니다.

 

Ear Clipping 기본 아이디어

• 귀를 찾아서 제거하는 과정을 반복하여 다각형을 삼각화합니다.
• 귀를 제거하면 정점 수가 감소하면서 최종적으로 다각형은 모두 삼각형으로 분해됩니다.

 

알고리즘 핵심 아이디어

단순히 모든 정점을 검사하여 귀를 찾는 방법은 O(n³) 시간 복잡도를 가집니다.
그러나 다음 최적화 기법을 통해 O(n²) 시간으로 개선할 수 있습니다.

• 다각형을 이중 연결 리스트(doubly linked list) 형태로 저장하여 귀 꼭짓점 제거 작업을 O(1)에 수행합니다.
• 귀인지 확인할 때 모든 정점이 아니라 반사 꼭짓점(reflex vertex)만 검사합니다.
• 반사 꼭짓점은 내각이 π(180도)보다 큰 정점을 의미합니다.

정점 삭제 후 인접 꼭짓점이 귀인지 다시 검사해야 하며, 이 과정이 최대 O(n²)의 시간 복잡도를 갖게 됩니다.
 

알고리즘 수행 과정

그림 2. 오른쪽 다각형은 왼쪽 다각형에서 ear <2, 3, 4> 를 자른 모습

그림 3. 오른족 다각형은 왼쪽 다각형에서 ear<2, 4, 5>를 자른 모습

그림 4. 오른족 다각형은 왼쪽 다각형에서 ear<2, 5, 6)를 자른 모습

그림 5. 오른족 다각형은 왼쪽 다각형에서 ear<2, 6, 7)를 자른 모습

그림 6. 오른족 다각형은 왼쪽 다각형에서 ear<8, 9, 0)를 자른 모습

그림 7. 오른족 다각형은 왼쪽 다각형에서 ear<8, 0, 1)를 자른 모습

그림 8. 오른족 다각형은 왼쪽 다각형에서 ear<1, 2, 7)를 자른 모습

그림 9. 단순한 다각형을 삼각측량 한 모습

 
위 논문 그대로 정점 [2, 3, 4], [2, 4, 5], [2, 5, 6], [2, 6, 7], [8, 9, 0], [8, 0, 1], [1, 2, 7] 순서대로 삼각화하는 코드다.
실제로 결과가 똑같음을 볼 수 있다.

 
Triangulation by Ear Clipping 6페이지

At this time there is no need to update the reflect or ear lists because we detect that only three vertices remain. The last triangle in the triangulation is T7 = ⟨7, 8, 1⟩. The full triangulation is show in Figure 9.

 

코드 실행결과

코드

import matplotlib.pyplot as plt
from matplotlib.patches import Polygon as MplPolygon
from matplotlib.collections import PatchCollection

# polygon 예제 (반시계 방향 simple polygon)
# https://www.geometrictools.com/Documentation/TriangulationByEarClipping.pdf
# 위 논문 3페이지 참고
vertices = [
    (3, 48),    # V0
    (52, 8),    # V1
    (99, 50),   # V2
    (138, 25),  # V3
    (175, 77),  # V4
    (131, 72),  # V5
    (111, 113), # V6
    (72, 43),   # V7
    (26, 55),   # V8
    (29, 100)   # V9
]

def is_convex(p_prev, p, p_next):
    ax, ay = p_prev
    bx, by = p
    cx, cy = p_next
    cross = (bx - ax)*(cy - ay) - (by - ay)*(cx - ax)
    return cross > 0

def point_in_triangle(p, a, b, c):
    def sign(p1, p2, p3):
        return (p1[0]-p3[0])*(p2[1]-p3[1]) - (p2[0]-p3[0])*(p1[1]-p3[1])
    b1 = sign(p, a, b) < 0.0
    b2 = sign(p, b, c) < 0.0
    b3 = sign(p, c, a) < 0.0
    return b1 == b2 == b3

def is_ear(polygon, i):
    prev = polygon[(i - 1) % len(polygon)]
    curr = polygon[i]
    next = polygon[(i + 1) % len(polygon)]
    if not is_convex(prev, curr, next):
        return False
    triangle = (prev, curr, next)
    for j, p in enumerate(polygon):
        if j in [(i - 1) % len(polygon), i, (i + 1) % len(polygon)]:
            continue
        if point_in_triangle(p, *triangle):
            return False
    return True

def ear_clipping(polygon):
    polygon = polygon.copy()
    triangles = []
    while len(polygon) > 3:
        ear_found = False
        for i in range(len(polygon)):
            if is_ear(polygon, i):
                prev = polygon[(i - 1) % len(polygon)]
                curr = polygon[i]
                next = polygon[(i + 1) % len(polygon)]
                triangles.append([prev, curr, next])
                del polygon[i]
                ear_found = True
                break
        if not ear_found:
            raise ValueError("No ear found. Polygon may be malformed.")
    triangles.append([polygon[0], polygon[1], polygon[2]])
    return triangles

# 삼각화 수행
result_triangles = ear_clipping(vertices)

# 시각화
fig, ax = plt.subplots()
patches = []

for tri in result_triangles:
    poly = MplPolygon(tri, closed=True)
    patches.append(poly)

p = PatchCollection(patches, edgecolor='black', facecolor='skyblue', alpha=0.6)
ax.add_collection(p)

# 외곽선 그리기
x, y = zip(*vertices)
ax.plot(x + (x[0],), y + (y[0],), 'k--', linewidth=1)

# 꼭짓점 라벨링
for i, (px, py) in enumerate(vertices):
    ax.plot(px, py, 'ro')
    ax.text(px + 0.1, py + 0.1, str(i), fontsize=9, color='blue')

ax.set_aspect('equal')
ax.set_title("Ear Clipping Triangulation (Simple Polygon)")
plt.grid(True)
plt.show()

---

 

Polygons with a Hole

Ear Clipping 알고리즘은 구멍(Hole)이 있는 다각형에도 적용할 수 있습니다.
외부 다각형과 내부 다각형 사이에 가상 연결선(biidge)을 만들 해결합니다.

그림 10. 구멍이 있는 다각형

알고리즘 기본 조건

그림 10은외부 다각형(outer polygon 또는 Outer Ring)과 내부 다각형(inner polygon 또는 Inner Ring, 구멍)으로 구성됩니다.
외부 다각형과 내부 다각형은 꼭짓점의 순서(ordering)가 서로 반대여야 합니다.
즉, 외부 다각형이 반시계 방향이라면, 내부 다각형은 시계 방향으로 정렬되어야 합니다.
 

가상 연결선(Bridge) 삽입

 
 

그림 11.

• 외부 다각형과 내부 다각형 간의 연결을 위해 서로 보이는 두 정점(mutually visible vertices)을 연결합니다.
• 이 연결선을 가상 연결선(bridge)이라 부르며, 두 개의 정점$(V_{11},V_{16})$을 양방향으로 연결한 두 선분$(<V_{11},V_{16}>$ , $<V_{16},V_{11}>)$으로 표현됩니다.
• 이 과정에서 외부 다각형과 내부 다각형의 정점 목록은 서로 반대 방향으로 정렬되어 있어야 합니다.

그림 11은 두 개의 가상 연결선을 보여줍니다.
 

가상 연결선으로 변형된 다각형(pseudosimple polygon)

원래 외부 다각형과 내부 다각형의 정점은 다음과 같았습니다.
 

• 외부 다각형: {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14}
• 내부 다각형(구멍): {15, 16, 17}

 
정점 $V_{11}$(외부 다각형)과 정점 $V_{16}$(내부 다각형)을 연결하여 구멍을 제거한 새로운 외부 다각형은 다음과 같습니다.

그림 12. 구멍이 있는 다각형을 삼각측량 한 모습

 

{0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 16, 17, 15, 16, 11, 12, 13, 14}

 
이를 가상 연결선으로 인해 겉보기엔 간단한 다각형과 비슷하나, 두 개의 간선이 같은 위치에서 반대 방향으로 존재하므로 가상 간단 다각형(pseudosimple polygon)이라 칭합니다.
 

구멍이 있는 다각형에서 ear cliping 알고리즘 적용 법 요약

다각형에 구멍이 존재할 때 Ear Clipping 알고리즘을 활용하려면 가상 연결선(bridge)을 추가하여 하나의 가상 간단 다각형(pseudosimple polygon)으로 변형한 뒤, 기존의 귀 자르기 알고리즘으로 삼각화를 수행하면 됩니다.
이 접근 방식은 여러 개의 구멍을 가진 다각형에도 재귀적으로 반복 적용할 수 있습니다.
 

외부링과 내부링 정점 방향을 반대로 해야하는 이유

외부 링(Outer Ring)과 내부 링(Inner Ring, 즉 구멍)의 정점들이 서로 반대 방향으로 정렬되어야 하는 이유는, 다각형 내부와 외부 영역을 정확하게 판단하고 일관되게 처리하기 위해서입니다.
 
Ear Clipping 알고리즘이나 다른 다각형 처리 알고리즘에서는 한 꼭짓점에서 다음 꼭짓점으로의 방향을 기준으로 내부 영역을 정의합니다.
 
일반적으로 다음과 같이 정의합니다.

• 외부 다각형(outer polygon) → 반시계 방향
• 내부 다각형(구멍) → 반대인 시계 방향으로 처리해야 합니다.

예시)

같은 방향으로 내부와 외부 다각형이 정렬되었다면, 내부 다각형(구멍)을 외부 다각형과 연결하여 단일 다각형으로 합치는 과정에서 내부와 외부 영역이 섞이게 됩니다.
 
다음과 같은 상황을 가정하겠습니다.
 

• 손을 종이 위에 놓고 다각형의 꼭짓점 순서대로 반시계 방향으로 따라 그렸다고 상상해 봅시다.
• 그러면 그린 선의 왼쪽이 자연스럽게 닫힌 다각형의 내부가 되고, 오른쪽은 외부(외곽 영역)가 됩니다.

 

왜 하필 '왼쪽'인가?

• 사실상 왼쪽이라는 방향 자체는 임의적으로 정한 규칙(convention)에 불과합니다.
• 컴퓨터 그래픽스 및 기하학 분야에서 널리 쓰이는 표준적인 관례로써, 반시계 방향이 내부를 왼쪽으로 두는 방식으로 널리 통용되고 있습니다.
• 이를 통해 내부·외부 구분을 일관성 있게 유지하고 다양한 알고리즘(Ear clipping 포함)에서 명확히 처리할 수 있도록 약속하는 것입니다.

 

구멍이 있는 경우는 왜 반대로 설정할까?

• 외부 다각형을 반시계 방향으로 설정하면 왼쪽이 내부가 되고, 이 내부에서 다시 구멍(내부 다각형)을 정의하려면 방향을 반대로(시계 방향) 설정하여 명확하게 구멍을 표현합니다.
• 이렇게 하면 내부 다각형은 외부 다각형과 반대 방향으로 진행하기 때문에, 내부 다각형의 왼쪽은 자연스럽게 원래 다각형의 외부가 됩니다. 즉, 구멍 영역임을 명확하게 나타낼 수 있습니다.

 
결국, "왼쪽에 내부 영역이 있다"는 표현은 알고리즘적으로 일관된 처리를 위해 정한 관례로서, 실질적인 처리에 있어서는 다각형의 내부 영역과 외부 영역을 명확하게 구분하여 다룰 수 있도록 돕는 기준입니다.
 

 

작성중

 

---

참고

Triangulation By Ear Clipping
https://sunyelee.blogspot.com/2013/07/triangulation-ear-clipping-algorithm.html