earcut보다 빠른 지도 삼각분할 라이브러리 공개
원제: Faster than earcut: triangulating 3.7M map polygons in 489 ms
왜 중요한가
지도·GIS·게임 등 대규모 폴리곤 처리가 필요한 분야에서 earcut의 드롭인 대안으로 즉시 채택 가능한 성능 개선 선택지가 생겼다.
지도 엔진 개발사 Globus Software가 2026년 10월 16일, 자사 맵 엔진의 폴리곤 삼각분할기를 'earstrip'이라는 오픈소스 라이브러리로 공개했다. C++ 헤더 파일 하나와 npm용 WebAssembly 빌드로 구성되며, 370만 개 폴리곤을 489ms에 처리한다. C++에서 earcut.hpp 대비 14%, 브라우저에서 earcut.js 대비 1.4~2.1배 빠르다.
Globus Software CEO Evgen Bodunov는 자사 오프라인 지도 엔진에서 사용하던 폴리곤 삼각분할기를 'earstrip'이라는 단일 C++ 헤더 라이브러리로 정리해 ISC 라이선스로 공개했다. earcut과 동일한 라이선스, 동일한 인터페이스를 채택해 기존 프로젝트에서 드롭인 교체가 가능하다.
기존 Globus 엔진은 제약 Delaunay 삼각분할기를 사용했다. Masovian Voivodeship(바르샤바 인근) 오프라인 지도의 줌 레벨 13 기준 374만 425개 폴리곤을 처리하는 데 M4 Pro 1코어에서 2.93초가 걸렸다. 이번에 ear clipping 방식으로 교체한 결과 489ms로 단축됐다.
핵심 배경은 GPU의 렌더링 단위가 삼각형뿐이라는 점이다. 지도에는 건물, 공원, 주차장 같은 다각형이 대부분이므로 렌더링 전에 반드시 삼각형으로 분할해야 한다. Delaunay 방식은 시뮬레이션이나 보간에 유리하게 삼각형 품질을 최적화하지만, 단순 평면 채색에는 불필요한 연산이다. 특히 Masovian 데이터의 절반에 가까운 180만 폴리곤은 꼭짓점이 4개 이하인데, 기존 코드는 이런 단순 도형에도 419ms를 소비했다.
earstrip은 ear clipping 알고리즘을 기반으로 여러 최적화를 단계별로 적용하며 속도를 끌어올렸다. Bodunov는 각 아이디어를 커밋 단위로 분리해 동일한 370만 폴리곤 데이터셋에서 반복 벤치마크를 수행한 과정을 블로그에 상세히 공개했다. npm 패키지로도 배포되어 브라우저 환경에서도 바로 사용할 수 있다.