Delaunay32: библиотека для триангуляции Делоне быстрее delaunator-cpp более чем в 10 раз
Delaunay32, открытая библиотека на C++17 для точной триангуляции Делоне двумерных наборов точек: пикселей, растровых выборок, проекций вокселей, геометрии с фиксированной точкой и другой уже дискретной или квантуемой пространственной информации. Библиотека принимает знаковые 32-битные целочисленные координаты, включая отрицательные значения и большие смещения. Конечные float-координаты тоже можно передавать напрямую: Delaunay32 квантует их внутри себя, а индексы результата продолжают указывать на исходные, неизменённые координаты.
В основе библиотеки, точные целочисленные предикаты ориентации и принадлежности окружности (orientation и in-circle predicates), разбиение точек по порядку Мортона по схеме «разделяй и властвуй», компактная топология рёбер по схеме two-dart и опциональная многопоточность. По данным README проекта, на больших наборах точек Delaunay32 более чем в 10 раз быстрее библиотеки delaunator-cpp и примерно в 4 раза быстрее Fade2D. Цифры получены на релизной сборке с одним миллионом точек: собственный автоматический многопоточный режим Delaunay32 принят за базовую единицу, 1.0×, а результаты остальных библиотек выражены как кратность этой базы; версия Fade2D в тесте, 2.17.3, с её API пакетной вставки (bulk insertion). delaunator-cpp не поддерживает триангуляцию с ограничениями (constrained Delaunay), поэтому в строке сравнения для такого режима результата для неё нет; сам delaunator-cpp подключён к репозиторию Delaunay32 лишь как подмодуль для опционального бенчмарка и не входит в зависимости библиотеки. В README отдельно оговорено, что приведённые коэффициенты приблизительны и зависят от конкретной машины и нагрузки; для более детального сравнения в репозитории есть отдельный бенчмарк для разных распределений точек.
Из возможностей библиотеки: детерминированная обработка повторяющихся точек; триангуляция с ограничениями для непересекающихся целочисленных отрезков; триангуляция многоугольных областей с отверстиями (кольца границ при этом должны быть простыми, не пересекаться и не касаться друг друга, а точки пересечения или Штейнера библиотека сама не добавляет); индексы треугольников, указывающие на исходные точки против часовой стрелки; опциональные смежность полурёбер, выпуклая оболочка и отображение точек-дублей на точку-представителя; несколько режимов квантования float-координат, автоматический, с фиксированным шагом и с фиксированным масштабом, с настраиваемыми пределами точности и политиками обработки коллизий. Отдельная опциональная цель delaunay32::extras добавляет сэмплирование точек, работу с геометрией в формате JSON, доменные запросы и экспорт в SVG. Библиотека рассчитана на данные, которые уже дискретны или допускают квантование с высоким разрешением: геометрию в пространстве изображений, растровые и высотные карты, проекции вокселей, карты с фиксированной точкой и графику. Прямая передача float-координат годится для большинства задач графики, картографии, визуализации и построения сеток общего назначения, где точное совпадение рёбер с исходной триангуляцией Делоне не требуется: получаемая сетка обычно очень близка к точной, но рёбра не гарантированно совпадают, расхождения наиболее вероятны у почти совпадающих, коллинеарных или коциркулярных точек; когда точная топология критична, в README рекомендуют адаптивно-точный триангулятор.
Библиотека распространяется по лицензии MIT и для обычного использования не имеет внешних зависимостей. Архитектурно Delaunay32 относится к устоявшемуся семейству алгоритмов Делоне по схеме «разделяй и властвуй»: в README она соотносится с работой Л. Гибаса и Дж. Стольфи 1985 года о примитивах для работы с подразделениями и построения диаграмм Вороного, а также со второй процитированной работой Р. А. Дуайера из того же семейства алгоритмов, в доступном тексте её название обрывается на полуслове, полное название и год в источнике не приведены. Ни дата релиза, ни имя автора или организации, ни номер версии самой библиотеки (указана только версия сравниваемого Fade2D) в тексте не названы.
Ключевые факты
- Delaunay32, открытая (MIT) библиотека на C++17 для точной триангуляции Делоне больших наборов 2D-точек по знаковым 32-битным целочисленным координатам; float-координаты тоже принимаются напрямую и квантуются внутри библиотеки.
- По данным README проекта, на релизной сборке с одним миллионом точек Delaunay32 более чем в 10 раз быстрее delaunator-cpp и примерно в 4 раза быстрее Fade2D 2.17.3; собственный многопоточный режим Delaunay32 взят за базовую единицу, 1.0×.
- В основе, точные целочисленные предикаты ориентации и принадлежности окружности, разбиение точек по порядку Мортона по схеме «разделяй и властвуй», компактная топология рёбер (two-dart) и опциональная многопоточность.
- Поддерживает триангуляцию с ограничениями (constrained Delaunay) для непересекающихся отрезков и триангуляцию многоугольных областей с отверстиями; delaunator-cpp таких возможностей не поддерживает и в самой библиотеке используется только как опциональный подмодуль для бенчмарка.
- Для обычного использования у библиотеки нет внешних зависимостей (лицензия MIT); опциональная цель delaunay32::extras добавляет сэмплирование точек, геометрию в JSON и экспорт в SVG.
Почему это важно
Триангуляция Делоне, базовая операция вычислительной геометрии: она нужна при построении сеток для симуляций и графики, в ГИС и картографии, при обработке облаков точек и растровых данных, в процедурной генерации. Многие существующие реализации либо работают с числами с плавающей точкой и точными предикатами ценой скорости, либо жертвуют точностью и детерминированностью ради быстроты. Delaunay32 предлагает третий путь: целочисленные координаты и точные целочисленные предикаты дают детерминированный и устойчивый результат, а разбиение по порядку Мортона вместе с многопоточностью, по данным README проекта, дают скорость более чем в 10 раз выше, чем у delaunator-cpp, и примерно в 4 раза выше, чем у Fade2D. При этом от float-координат отказываться не нужно, библиотека принимает их напрямую и квантует внутри себя.
Кому это важно
В первую очередь, разработчикам на C++, которым нужна быстрая и детерминированная триангуляция Делоне для больших наборов точек: авторам графических движков и приложений, специалистам по ГИС и картографии, инженерам, работающим с растровыми и воксельными данными и построением сеток. Отдельно пригодится тем, кто уже использует delaunator-cpp или Fade2D и упирается в производительность на больших наборах точек: Delaunay32 позиционируется как более быстрая замена с похожим набором сценариев, включая триангуляцию с ограничениями и многоугольные области с отверстиями, которых у delaunator-cpp нет.
Как это применить
Библиотека распространяется по лицензии MIT, для базового использования не требует внешних зависимостей и собирается через CMake: git submodule update --init --recursive, затем cmake -S . -B build -DCMAKE_BUILD_TYPE=Release, cmake --build build и, при желании, ctest для тестов; на Windows используется многоконфигурационный генератор Visual Studio, а собранные файлы лежат в build\Release. В коде библиотека подключается заголовком delaunay32/delaunay.hpp: точки передаются вектором delaunay32::Point (или delaunay32::FloatPoint для float-варианта), а результат даёт вызов triangulate_int() или triangulate_float(); для доступа к смежности рёбер, выпуклой оболочке и отчёту о квантовании есть более полные варианты triangulate_int_full() и triangulate_float_full(). Отдельная опциональная цель delaunay32::extras (заголовки delaunay32/extras/sampling.hpp и delaunay32/extras/svg.hpp) добавляет сэмплирование точек и экспорт результата в SVG, удобно для быстрой визуальной проверки на своих данных. Для сравнения производительности на своём железе в репозитории есть отдельный бенчмарк против delaunator-cpp (подключается опциональным подмодулем) и Fade2D.
Можно ли доверять
Все заявления о скорости, это самоописание проекта из его README на GitHub, без независимого стороннего теста в источнике. При этом сами разработчики прямо оговаривают, что приведённые коэффициенты приблизительны и зависят от конкретной машины и нагрузки, а не выдают их за точное измерение; репозиторий включает тесты (ctest) и собственный набор бенчмарков, а лицензия MIT позволяет перепроверить цифры самостоятельно. Алгоритмическая основа не придумана с нуля: README прямо возводит архитектуру к устоявшемуся семейству алгоритмов Делоне по схеме «разделяй и властвуй», работе Л. Гибаса и Дж. Стольфи 1985 года и второй, не до конца процитированной работе Р. А. Дуайера. В доступном тексте не названы ни дата релиза, ни автор или организация, ни версия самой библиотеки (указана только версия сравниваемого Fade2D, 2.17.3), ни характеристики тестового железа. Публикация на Hacker News пока набрала 39 голосов и всего 5 комментариев, самостоятельного обсуждения или проверки цифр сообществом ещё не было.
Риски и подводные камни
Цифры о скорости, собственные измерения проекта, а не независимый тест: абсолютное время (секунды или миллисекунды) и характеристики тестового стенда в источнике не приведены, сравнивать можно только относительные коэффициенты, и сами разработчики называют их приблизительными. Результат по Fade2D привязан к конкретной версии 2.17.3 и её API пакетной вставки, на других версиях или сценариях вставки соотношение может быть другим. delaunator-cpp вообще не поддерживает триангуляцию с ограничениями, поэтому для такого сценария сравнения для неё нет. Для триангуляции многоугольных областей кольца границ должны быть простыми, не пересекаться и не касаться друг друга, а отверстия, строго внутри внешнего кольца и не перекрываться; точки пересечения или Штейнера библиотека сама не добавляет, поэтому произвольную геометрию «как есть» в неё не передать. При работе с float-координатами точное совпадение рёбер с исходной триангуляцией Делоне не гарантировано, особенно у почти совпадающих, коллинеарных или коциркулярных точек, для таких случаев в README советуют адаптивно-точный триангулятор. Есть и нюанс для многопоточного кода: один экземпляр Triangulator нельзя вызывать из нескольких потоков одновременно, хотя разные независимые экземпляры использовать параллельно можно.