공간 데이터를 다루는 실무에서 점 집합을 삼각형 그물로 잇는 들로네 삼각분할은 지형 표현, 메시 생성, 시각화, 근접 질의 같은 작업의 밑바탕이 된다. Delaunay32는 이 문제를 정수 좌표에 특화해 다시 설계한 C++17 라이브러리다. 픽셀, 래스터 샘플, 복셀 투영, 고정소수점 지오메트리처럼 이미 이산화되어 있거나 균일한 고해상도 양자화를 견딜 수 있는 데이터를 겨냥한다. int32 좌표를 직접 다루면서도 유한한 부동소수점 점을 그대로 받아들일 수 있는데, 이 경우 라이브러리가 내부적으로 좌표를 정수 격자로 양자화하고 출력 인덱스는 원래 좌표를 그대로 가리킨다.
정확한 정수 술어와 분할 정복
삼각분할 알고리즘의 견고성은 세 점의 방향이나 네 점의 공원(cocircular) 여부 같은 기하 판정을 얼마나 정확히 하느냐에 달려 있다. 부동소수점 연산은 반올림 오차 때문에 이런 판정에서 모순된 결과를 내놓을 수 있고, 이는 곧 잘못된 위상이나 무한 루프로 이어진다. Delaunay32는 정수 좌표 위에서 정확한 정수 술어(exact integer predicates)를 사용해 이 문제를 회피한다. 여기에 모턴 순서(Morton order) 기반의 분할 정복 알고리즘, 두 개의 다트로 구성한 조밀한 위상 표현, 선택적 멀티스레딩을 결합했다. 그 결과 같은 입력에 대해 항상 같은 결과를 내는 결정론적이고 견고한 삼각분할기를 얻는다.
성능은 이 라이브러리가 내세우는 핵심이다. 백만 개 점 규모의 릴리스 빌드 벤치마크에서 자동 멀티스레드 모드를 1.0배 기준으로 삼았을 때, delaunator-cpp는 약 10배 이상, Fade2D는 약 4배 느린 것으로 측정됐다고 밝힌다. 다만 이 수치는 의도적으로 근사값이며 측정한 여러 점 분포에 대한 평균을 반올림한 것이고, 기계와 작업 부하에 따라 달라진다는 단서가 붙는다. 저장소에는 delaunator-cpp와 비교하는 상세 벤치마크가 포함돼 있어 직접 실행해 자신의 환경에서 확인하도록 권한다. 대규모 입력에서는 기수 정렬, 독립적인 하위 트리, 병합 단계, 삼각형 내보내기가 유지되는 워커 팀을 공유하고, 작은 입력은 동기화 부담을 피하려고 직렬로 처리한다.
부동소수점 입력의 실무적 타협
실무자가 반드시 짚어야 할 지점은 부동소수점 직접 입력의 한계다. triangulate_float()는 원본 좌표를 건드리지 않고 원래 입력에 대한 인덱스를 돌려주지만, 간선을 결정할 때는 내부적으로 양자화된 정수 좌표를 쓴다. 따라서 결과 메시는 원래 부동소수점 값에서 직접 계산한 것과 대개 매우 가깝지만, 간선이 동일하다는 보장은 없다. 차이는 거의 겹치거나 공선(collinear), 공원인 점들, 즉 기하학적 퇴화 근처에서 가장 나타나기 쉽다. 그래픽, 매핑, 시각화, 일반 메시 생성처럼 정확한 간선 위상이 필수가 아닌 대다수 용도에서는 실용적이지만, 원본 좌표의 정밀한 들로네 위상이 반드시 필요하다면 적응형 정확 삼각분할기를 써야 한다고 명확히 선을 긋는다.
더 세밀한 제어가 필요할 때는 triangulate_float_full()이 양자화 세부 정보, 인접 관계, 볼록 껍질, 대표점 매핑을 함께 제공한다. 이 함수의 양자화 리포트는 격자 간격, 측정된 좌표 오차, 점 충돌 정보를 담는다. QuantizationOptions를 쓰면 서로 다른 배치 사이에서도 안정적인 매핑을 유지할 수 있어, 여러 번에 나눠 처리하는 데이터에 일관된 격자를 적용할 수 있다.
제약 삼각분할과 폴리곤 도메인
Delaunay32는 단순 삼각분할을 넘어 제약 조건을 지원한다. 제약 간선은 같은 정수 점 벡터에 대한 인덱스 쌍으로 전달하며, 결과는 볼록 껍질 전체를 삼각분할하면서 모든 제약을 메시 간선으로, 또는 기존 점이 선분 위에 있을 때는 간선의 연쇄로 보존한다. 기존 점을 지나지 않는 교차는 거부된다. 폴리곤 링 역시 같은 점 벡터의 인덱스로 지정하고, 닫는 간선은 암묵적으로 처리된다. 이 호출은 링 감김 방향을 정규화하고 모든 경계를 제약 간선 연쇄로 복원한 뒤, 외곽 안쪽이자 모든 구멍 바깥에 있는 삼각형만 반환한다. 링은 단순해야 하고 서로 교차하거나 닿을 수 없으며, 구멍은 외곽 안에 엄격히 들어가야 한다. 이 구현은 교차점이나 스타이너 점을 삽입하지 않는다는 점도 분명히 해 둔다.
라이브러리 구조도 실무 통합을 염두에 두고 있다. Triangulator 인스턴스는 호출 사이에 작업 저장소와 워커 스레드를 유지하기 위해 재사용할 수 있지만, 단일 인스턴스를 동시에 호출해서는 안 되며 별도 인스턴스는 서로 독립적이다. 코어 타깃 delaunay32::delaunay32와 선택적 유틸리티인 delaunay32::extras가 분리돼 있고, extras는 코어에 링크하지만 코어는 결코 extras에 의존하지 않는다. extras는 문서화된 지오메트리 JSON 스키마 입출력과 경계를 고려한 블루노이즈 방식 폴리곤 내부 샘플링 같은 재사용 가능한 도구를 제공한다. 벤치마크에 쓰이는 delaunator-cpp는 선택적 서브모듈일 뿐 라이브러리 자체는 이에 의존하지 않는다. 전체는 MIT 라이선스이며, 시맨틱 버저닝을 따르고 CMakeLists.txt의 버전을 단일 진실 원천으로 삼는다. 정리하면 Delaunay32는 모든 상황을 위한 만능 도구가 아니라, 이산 데이터라는 명확한 전제를 받아들이는 대신 속도와 결정론을 얻는 특화된 선택지다.