지도 폴리곤 삼각분할 6배 가속, earstrip 공개

핵심 요약

• 지도 엔진의 폴리곤 삼각분할 라이브러리 earstrip을 ISC 라이선스로 공개했으며, C++ 헤더 파일과 WebAssembly npm 빌드를 제공한다.
• C++에서는 earcut.hpp보다 14% 빠르고, 브라우저 환경에서는 earcut.js보다 1.4~2.1배 빠르다.
• GPU는 삼각형만 그리므로 건물·공원 등 다각형 지도 요소들을 먼저 삼각형으로 잘라야 한다.
• 기존 방식은 Delaunay 삼각분할을 사용했는데, 폴란드 마조비아 지역 지도의 370만 개 폴리곤 처리에 2.93초가 걸렸다.
• 개선된 귀 깎기(ear clipping) 알고리즘으로 다단계 최적화를 적용했다: 움푹한 꼭짓점(dent)만 검사, 볼록 폴리곤 단축, 삼각형 스트립 작성, 버킷 정렬, 분기 제거, 표시된 움푹점 검사 등이다.
• 최종적으로 동일 폴리곤 처리를 489ms로 단축했으며, Delaunay 대비 6배 빠르다.
• 구멍이 있는 폴리곤은 브리지로 외곽과 연결하는데, 다각형이 단순하지 않은 경우(그리드 반올림으로 자기 자신과 교차)는 Delaunay로 폴백한다.
• 마조비아 데이터에서 76개 폴리곤이 귀가 없어 폴백되었으나, 맵 생성기가 GEOS의 스냅 반올림을 적용하면 모든 폴리곤을 귀 깎기로 처리 가능하다.
• 구멍이 128개 이상인 폴리곤(세계 지도에서 구멍 11,675개인 사례)은 Delaunay가 더 빠르므로 해당 임계값 이상은 Delaubay로 보낸다.
• WebAssembly 컴파일 시 earstrip은 V8에서 23% 느려지지만, 폴리곤당 호출 오버헤드를 포함한 npm 패키지 형태로는 earcut.js보다 여전히 1.4배 빠르다.
• 직접 호출 방식(모든 폴리곤을 한 번에 메모리로 전달)으로는 earcut.js보다 1.7~2.1배 빠르며, earstrip 저장소에 테스트 폴리곤과 벤치마크 코드가 공개되어 있다.