earcut보다 빠르다: 370만 개 지도 폴리곤을 489ms에 삼각분할
Faster than earcut: triangulating 3.7M map polygons in 489 ms
지도 엔진의 폴리곤 삼각분할기를 ISC 라이선스의 단일 C++ 헤더 라이브러리 earstrip으로 공개했다. 기존 constrained Delaunay 방식이 370만 개 폴리곤에 2.93초 걸리던 작업을 ear clipping으로 바꿔 489ms까지 줄였다. 단순한 귀 자르기에서 시작해 오목점만 검사하기, 볼록 폴리곤 건너뛰기, 지그재그 스트립, 버킷, 분기 제거, 적중 표시 등 개선을 하나씩 쌓아 올린 과정을 커밋 단위로 측정해 보여준다. 브라우저에서는 earcut.js보다 1.4~2.1배 빠르다.
마소비아 주 폴리곤의 거의 절반인 180만 개가 꼭짓점 4개 이하인데, Delaunay 코드는 이들을 위해 매번 삼각분할을 처음부터 새로 만들며 419ms를 쓴다.
HN 토론
35- morishuz
멋지네요. 성능 향상이 인상적입니다!
저는 폴리곤과 홀을 지원하는 constrained delaunay triangulator인 Delaunay32의 작성자입니다. incremental insertion 대신 divide-and-conquer를 사용하기 때문에 여기서의 delaunay 베이스라인과 어떻게 비교될지 궁금하네요.
https://github.com/morishuz/delaunay32
아직 당신의 코퍼스로 벤치마크를 해보지 않았고, 현재 우리의 폴리곤 API는 서로 닿지 않는 홀을 가진 단순한 링만 요구합니다. 데이터셋을 공개해 주셔서 감사합니다. 테스트와 비교에 유용할 것 같아요!
- amelius
모든 삼각분할기의 어머니를 언급해야 합니다:
- mistercow
오랫동안 왜 ear clipping + 최적화가 O(nlog*n) 시간 복잡도를 가지고 홀을 자연스럽게 처리하는 Seidel의 사다리꼴 방법 같은 것보다 삼각분할에서 승리했는지 궁금했습니다. big-O가 전부는 아니라는 걸 알지만, 그것은 본질적으로 선형 대 이차이고, 시간이 지날수록 점점 더 복잡한 폴리곤을 삼각분할하는 데 관심이 있는 것 같습니다.
그냥 삼각형 품질 문제인가요? Seidel이 다루기 힘든 슬리버를 너무 많이 만들어내나요?
- mourner
안녕하세요 Evgen, Earcut 작성자입니다 — 글과 정말 멋진 라이브러리 감사합니다! Earcut의 JS 버전에 차용할 만한 트릭이 있는지 확인해봐야겠네요. :)
한 가지 주목할 점은 번들 크기가 커지지 않도록 라이브러리를 작게 유지하기 위해 일부 잠재적 최적화를 의도적으로 거부해야 했다는 것입니다 — 대부분의 실제 애플리케이션(예: Mapbox GL JS)에서는 이미 충분히 빠르고(4.1k min/gz) 말이죠. Earstrip의 WASM 빌드 크기가 얼마나 되는지 궁금하네요.
C++ 쪽에서는 Mapbox가 이제 작은 폴리곤은 earcut.hpp로 처리하고, 크고 복잡한 폴리곤은 monotone decomposition 기반의 다른 알고리즘으로 전환하는 하이브리드 접근 방식을 사용합니다. 알고리즘 복잡도상 상수가 더 높지만 입력 크기에 따라 훨씬 잘 확장되기 때문입니다.
- stymaar
결과에 매우 길고 매우 얇은 삼각형이 많이 포함되어 있는 것을 봅니다. 그런 것들은 일반적으로 GPU 래스터라이저에게 최악의 시나리오 아닌가요?