earcut보다 빠르게: 지도 폴리곤 370만 개를 489ms에 삼각분할하기

지도 엔진의 삼각분할기를 귀 자르기(ear clipping) 기반 earstrip으로 교체해, M4 Pro 단일 코어에서 폴리곤 374만 개의 처리 시간을 기존 제약 Delaunay 방식의 2,931ms에서 489ms로 줄임 지도 영역을 단색으로 채우는 작업에는 삼각형 모양의 품질이 중요하지 않으므로, 오목 꼭짓점만 검사하고 볼록 폴리곤은 검사를 생략하는 방식으로 불필요한 기하 연산을 줄임 삼각형 스트립 출력, 공간 버킷, 분기 없는 검사와 비트 마스크를 결합해 인덱스 수와 꼭짓점 검사 비용을 낮춤 귀를 찾지 못하거나 결과 면적이 맞지 않는 폴리곤, 구멍이 매우 많은 폴리곤에는 제약 Delaunay 대체 경로를 유지하며, 라이브러리가 이를 내부에서 처리함 ISC 라이선스의 단일 C++ 헤더와 npm WebAssembly 패키지로 공개됐으며, 제공된 벤치마크에서 호출 방식에 따라 earcut.js보다 1.4~2.1배 빨랐음 지도 렌더링에 맞춘 삼각분할 GPU로 지도 영역을 채우려면 건물, 공원, 주차장 등의 폴리곤을 삼각형으로 분할해야 함 바르샤바 Śródmieście의 예시 구역은 폴리곤 331개, 꼭짓점 5,151개로 구성되며 삼각형 4,514개가 됨 바르샤바 주변 Masovian Voivodeship 오프라인 지도의 줌 레벨 13에는 폴리곤 3,740,425개가 있음 M4 Pro 단일 코어에서 기존 제약 Delaunay 삼각분할기는 전체 처리에 2.93초가 걸림 귀 자르기 구현을 아이디어별 커밋으로 재구성하고 동일한 데이터로 각 단계를 측정함 Delaunay의 품질 보장이 불필요한 경우 Delaunay 삼각분할은 각 삼각형의 외접원 안에 다른 점이 없도록 구성하며, 같은 점 집합의 삼각분할 중 최소 각도를 최대화함 인접 삼각형의 공유 변을 뒤집는 국소 수정으로 조건을 복구함 제약 Delaunay에서는 원래 폴리곤의 변을 반드시 유지하므로, 일부 변은 외접원 조건에 따라 뒤집을 수 없음 기존 구현은 꼭짓점을 하나씩 삽입하고, 해당 점이 들어갈 삼각형을 찾아 분할한 뒤 주변 변을 뒤집음 폴리곤 경계도 강제로 삽입하고, 마지막에 폴리곤 내부이면서 구멍 바깥인 삼각형만 남김 좋은 모양의 삼각형은 보간과 시뮬레이션에는 중요하지만, 단색 채우기에서는 가늘고 긴 삼각형도 GPU가 정확하게 채움 전체의 거의 절반인 180만 개는 꼭짓점이 4개 이하임 삼각형은 분할이 필요 없고 볼록 사각형은 두 삼각형이면 되지만, 기존 코...