들로네 삼각분할 생성기

들로네 삼각분할 생성기는 모든 2D 점 집합을 가장 작은 내각을 최대화하는 고유한 삼각분할로 변환합니다. 이는 지형 모델링, 유한 요소 메시 생성, 최근접 이웃 보간 및 계산 기하학 수업의 골드 표준(기준)입니다. 좌표를 붙여넣거나 빠른 시작 패턴을 선택하면, 이 도구가 서버 측에서 보이어-왓슨(Bowyer-Watson) 알고리즘을 실행하고 각 삼각형을 품질에 따라 색상으로 구분하며, 필요에 따라 외접원 공백 특성, 볼록 껍질 및 보로노이 쌍대를 보여줍니다.

생성된 메시를 읽는 방법

이 들로네 삼각분할 생성기만의 차별점

들로네 삼각분할이란 무엇인가요?

2D 점 집합이 주어졌을 때, 이들을 삼각분할(겹치거나 빈틈없이 볼록 껍질을 삼각형으로 완전히 채우는 것)하는 방법은 대개 여러 가지가 있습니다. 러시아 수학자 보리스 들로네(Boris Delaunay, 1934)의 이름을 딴 들로네 삼각분할은 외접원 공백 특성(empty-circumcircle property)을 만족하는 분할입니다. 즉, 메시의 모든 삼각형에 대해 세 꼭짓점을 지나는 원 내부에는 다른 입력 점이 포함되지 않습니다. 이 고유한 특성은 놀라운 결과를 가져옵니다. 동일한 점 집합의 모든 삼각분할 중에서 들로네 삼각분할이 가장 작은 내각을 최대화합니다. 쉽게 말해, 가능한 한 가장 '통통하고' '균형 잡힌' 삼각형을 만들어냅니다.

보이어-왓슨 알고리즘 작동 방식

1. 모든 입력 점을 아우르는 매우 큰 초삼각형(super-triangle)을 둘러쌉니다.
2. 입력 점을 한 번에 하나씩 삽입합니다. 새로운 점마다 해당 점을 외접원 내부에 포함하는 모든 기존 삼각형을 찾습니다. 이들이 '잘못된' 삼각형입니다.
3. 잘못된 삼각형을 제거합니다. 삼각형들이 사라진 자리는 다각형 경계를 가진 구멍이 됩니다.
4. 새로운 점과 그 경계의 모든 가장자리를 연결하여 새로운 삼각형을 형성합니다.
5. 모든 점이 삽입된 후, 초삼각형 꼭짓점과 여전히 접하고 있는 삼각형들을 제거합니다. 남은 구조가 원본 점 집합의 들로네 삼각분할입니다.

들로네 삼각분할의 활용 분야

• 지형 모델링 (GIS): 고도 표본(일반적으로 지형 관측소와 같이 불규칙한 간격)을 수치 표고 모델인 불규칙 삼각망(TIN)으로 연결하여 고도 조회, 음영 기복 및 3D 시각화에 사용합니다.
• 유한 요소 해석 (FEA): 형태가 좋은 들로네 삼각형은 역학, 열전달, 전자기학의 편미분 방정식에 대해 안정적인 수치해를 제공합니다.
• 컴퓨터 그래픽스: 렌더링, 캐릭터 리깅, 절차적 지형을 위한 메시 생성에 활용됩니다. 들로네 분할의 '좁고 긴 삼각형 배제' 보장은 텍스처 늘어남 현상(아티팩트)을 방지합니다.
• 자연 이웃 보간 (Natural-neighbor interpolation): 보로노이 쌍대를 통해 각 쿼리 점의 자연 이웃을 계산함으로써, 흩어진 표본 데이터로부터 매끄러운 표면을 복원합니다.
• 계산 기하학 수업: 볼록 껍질, 보로노이 다이어그램, 점 위치 찾기, 분할 정복 등과 깊은 연관이 있는 정석적인 알고리즘입니다.
• 3D 프린팅 슬라이서 및 CNC 툴패스: 2D 들로네(및 3D 변형인 들로네 사면체 분할)는 많은 슬라이싱 및 채우기(infill) 전략의 기반이 됩니다.

들로네 대 보로노이: 동전의 양면

보로노이 다이어그램은 평면을 입력 점당 하나의 셀로 분할하며, 각 셀은 다른 어떤 점보다 해당 점에 더 가까운 영역을 포함합니다. 경계를 공유하는 셀들의 점들을 연결하면 정확히 들로네 삼각분할을 얻을 수 있습니다. Conversely, the circumcenters of adjacent Delaunay triangles, joined by line segments, form the Voronoi edges. Toggle "Voronoi dual" on this tool to see the orange dashed lines overlaid on the same chart — every Delaunay edge crosses exactly one Voronoi edge at right angles.

품질, 좁고 긴 삼각형 및 메시 정밀화

들로네 분할은 전역적인 최소 내각을 최대화하지만, 근본적으로 불량한 점 분포를 해결할 수는 없습니다. 입력 점들이 거의 일직선상에 있거나, 한곳에 몰려 있거나, 큰 빈 공간을 남겨두는 경우 일부 삼각형은 여전히 좁고 길게 형성됩니다(최소 내각 20° 미만). 이를 해결하는 방법은 스타이너 점 삽입(Steiner-point insertion)입니다. 루퍼트(Ruppert) 알고리즘이나 추(Chew)의 두 번째 알고리즘과 같은 알고리즘은 좁고 긴 삼각형의 외심에 새로운 점을 반복적으로 추가하고 매번 재삼각분할을 수행하여, 모든 삼각형이 목표 품질 기준을 충족할 때까지 정밀화합니다. 이 생성기는 어떤 삼각형이 좁고 긴지 보여주므로, 더 정밀한 메시를 원할 때 스타이너 점을 어디에 추가해야 할지 알 수 있습니다.

실행 예시

"원 + 중심축(Circle + hub)" 사전 설정을 클릭해 보세요. 이 도구는 원 둘레에 18개의 점을 배치하고 중심에 1개의 점을 배치한 후 삼각분할을 수행합니다. 그 결과 중심축에서 만나는 18개의 완벽한 이등변 삼각형 부채꼴이 만들어집니다. 각 삼각형은 테두리에서 10°, 중심축에서 80°–80°의 각도를 가집니다. 최악의 최소 내각은 10°이며, 모든 삼각형이 좁고 긴 형태로 분류되고, 히스토그램은 모든 삼각형이 0°–10° 구간에 있음을 보여줍니다. 이 예시는 훌륭한 교육 사례입니다. 입력 데이터가 강제하는 구조 내에서는 들로네 최적 삼각분할조차도 좁고 긴 삼각형을 가질 수 있음을 보여줍니다. 이제 "무작위 클라우드(Random cloud)"를 클릭해 보면, 점들이 고르게 분포되어 동일한 알고리즘으로도 좋은 형태의 삼각형이 생성되며 히스토그램이 오른쪽으로 이동하는 것을 확인할 수 있습니다.

흔한 오해들

• "들로네 삼각분할은 고유하다": 보통은 그렇지만, 네 개의 입력 점이 동일 선상의 원 위에 있는 경우(공원점), 해당 그룹에 대해 두 가지 유효한 들로네 삼각분할이 존재할 수 있습니다. 이 생성기는 일관되게 그 중 하나를 선택합니다.
• "점이 많을수록 항상 품질이 좋아진다": 위치가 좋지 않은 점을 추가하면 오히려 새로운 좁고 긴 삼각형이 생길 수 있습니다. 스타이너 점 알고리즘은 외심 위치를 고려하여 새로운 점을 신중하게 배치하므로 품질 향상이 보장됩니다.
• "들로네 분할은 볼록 껍질과 같다": 아닙니다. 볼록 껍질은 가장 바깥쪽 경계이며, 들로네 삼각분할은 그 내부를 삼각형으로 가득 채우는 것입니다.
• "모든 삼각분할은 다 비슷해 보인다": 차이는 매우 극적입니다. 들로네 가장자리에서 대각선 뒤집기(flip) 한 번으로 25° 삼각형이 5° 삼각형으로 바뀔 수 있습니다. 이 도구의 품질 히트맵은 이러한 차이를 시각적으로 명확하게 보여줍니다.

자주 묻는 질문 (FAQ)