Delaunay32 — это C++17-библиотека для триангуляции Делоне больших дискретных наборов 2D-точек: пикселей, растровых отсчётов, проекций вокселей, fixed-point-геометрии. Внутри она сочетает точные целочисленные предикаты, алгоритм divide-and-conquer с порядком Мортона, компактную топологию two-dart и опциональную многопоточность. Выход детерминированный и очень быстрый. На больших наборах Delaunay32 более чем в 10 раз быстрее delaunator-cpp и примерно в 4 раза быстрее Fade2D. Для constrained-триангуляции она примерно в 4.3 раза быстрее Fade2D; delaunator-cpp такой режим вообще не поддерживает.
Обычные float-координаты можно передавать напрямую. Библиотека сама квантует их во внутреннюю целочисленную сетку, а индексы треугольников ссылаются на исходные координаты. Топология рёбер может немного отличаться от точной триангуляции исходных float, особенно для почти совпадающих, коллинеарных или коциркулярных точек. Для целочисленных входов доступна constrained-триангуляция: можно зафиксировать рёбра и триангулировать многоугольники с дырками. Пересечения рёбер и Steiner-точки не добавляются. API умеет отдавать halfedge-соседей, выпуклую оболочку и маппинг дубликатов.
Реализация опирается на классическую схему divide-and-conquer, в частности на работы Guibas/Stolfi 1985 года и Dwyer 1987 года. Для больших входов используются радикс-сортировка, независимые поддеревья и общий пул рабочих потоков; мелкие входы остаются последовательными, чтобы не тратить время на синхронизацию.
Отдельно подключается модуль delaunay32::extras: генерация точек, экспорт в SVG, чтение и запись схемы Delaunay32 geometry JSON, а также семплинг внутри полигонов в стиле blue-noise. Основное применение — графика, карты, визуализация, растровые и воксельные данные. Сборка через CMake, Visual Studio поддерживается. Библиотека не требует зависимостей и распространяется по лицензии MIT.