들로네 삼각분할 계산기
점 좌표를 넣으면 어떤 삼각형의 외접원도 다른 점을 담지 않는 들로네 삼각분할을 구해, 볼록 껍질 경계 위에 겹쳐 보여 줍니다.
한 줄에 「x y」씩. 3개 이상, 60개까지.
삼각형 개수
4개
점 5개(볼록 껍질 4개 포함), 변플립 1회
계산 방법
- 1점 좌표를 한 줄에 하나씩 「x y」로 넣습니다. 3개 이상, 한 직선 위에 있지 않아야 합니다.
- 2볼록 껍질 경계 위에 그려진 삼각형 그물을 확인합니다.
- 3오일러 공식·넓이 합·빈 외접원 조건 세 가지 검증 결과를 확인합니다.
자주 묻는 질문
점들을 삼각형으로 채우되, 어떤 삼각형을 그려도 그 삼각형의 외접원 안에 다른 점이 들어오지 않게 만든 것입니다. 이 조건이 가늘고 긴 삼각형을 피해 가능한 한 뭉툭한 삼각형들로 채우게 만들어, 지형 메싱이나 유한요소법에서 표준으로 씁니다.
아닙니다. 처음엔 교과서에 흔한 「가상의 슈퍼삼각형으로 시작해 점을 하나씩 넣는」보위어-왓슨 방식으로 만들었는데, 무작위 점 2000세트로 대조해 보니 볼록 껍질 경계 근처에서 0.3% 확률로 삼각형이 하나씩 빠졌습니다. 슈퍼삼각형을 아무리 키우거나 정확 산술(BigInt)을 써도 똑같이 실패해 — 가상의 점으로 무한을 흉내 내는 방식 자체의 한계라는 결론을 내고, 볼록 껍질을 부채꼴로 나눈 뒤 로슨 변플립(Lawson flip)으로 다듬는 방식으로 바꿨습니다. 실좌표만 쓰는 방식이라 같은 2000세트를 전부 통과합니다.
아무 삼각분할(꼭 들로네가 아니어도 되는)에서 시작해, 두 삼각형이 맞닿은 변마다 마주보는 꼭짓점이 상대 삼각형의 외접원 안에 있으면 그 변을 반대 대각선으로 뒤집는 것입니다. 더 뒤집을 게 없을 때까지 반복하면 들로네 삼각분할이 됩니다. 1977년 로슨이 유한한 점 집합에서는 이 과정이 항상 끝난다는 것을 증명했습니다.
세 가지를 확인합니다. ① 어떤 삼각형의 외접원도 다른 점을 담지 않는지(들로네의 정의 그 자체) 모든 삼각형×모든 점을 무차별 대조합니다. ② 삼각형 넓이의 합이 볼록 껍질 넓이와 같은지(빠지거나 겹친 곳이 없는지) 봅니다. ③ 삼각형 개수가 오일러 공식(2×점개수−볼록껍질점개수−2)과 맞는지 확인합니다.
서로 쌍대(dual) 관계입니다. 보로노이 다이어그램은 평면을 「어느 점에 가장 가까운가」로 나눈 셀들이고, 들로네 삼각분할은 그 셀들이 서로 맞닿은 두 점을 이은 것입니다. edu/voronoi-cell은 쿼리 좌표가 어느 사이트에 속하는지만 보여 주고, 이 계산기는 그 쌍대 관계의 다른 절반 — 삼각분할 자체(변 목록, 외접원 조건) — 을 보여 줍니다.
전송되지 않습니다. 모든 계산은 브라우저 안에서 이뤄지고, 입력값은 이 기기에만 남습니다.
알아두면 좋은 점
- 알고리즘: 볼록 껍질(edu/convex-hull 재사용)을 부채꼴로 삼각분할한 뒤 안쪽 점을 하나씩 넣어(그 점이 든 삼각형을 3개로 쪼개) 유효한 삼각분할을 만들고, 로슨 변플립으로 들로네 조건까지 다듬습니다.
- 처음 구현(가상의 슈퍼삼각형을 쓰는 보위어-왓슨)은 무작위 점 2000세트 대조에서 볼록 껍질 경계 근처 0.3%에서 삼각형을 하나 빠뜨리는 것을 발견했습니다. 슈퍼삼각형 크기를 20배~10⁹배까지 키워도, 부동소수점 대신 BigInt 정확 산술을 써도 똑같이 실패해 크기·정밀도 문제가 아니라는 것을 확인했고, 가상의 점을 아예 쓰지 않는 지금 방식으로 바꿔 같은 2000세트를 전부 통과시켰습니다.
- 로슨 변플립 구현에서 한 회차에 여러 변을 한꺼번에 고치면(직전 플립으로 이미 바뀐 삼각형을 옛 정보로 다시 건드리게 되어) 위상이 깨지는 버그를 테스트로 잡았습니다. 지금은 회차마다 변 하나만 고치고 처음부터 다시 훑습니다.
- 점 60개까지 다룹니다. 4개 이상의 점이 정확히 한 원 위에 있는(동일원, cocyclic) 경우 어느 대각선을 쓸지 애매해지는데, 이때도 넓이 합·오일러 공식은 성립하지만 어느 쪽 대각선이 나올지는 부동소수점 오차에 따라 달라질 수 있습니다.
함께 보면 좋은 도구
마지막 검증: 2026년 9월 3일 · 결과는 참고용 추정치입니다.