Триангуляция 3,7 млн полигонов карты за 489 мс — быстрее, чем earcut
Faster than earcut: triangulating 3.7M map polygons in 489 ms
Globus Software открыла исходный код триангулятора из своего картографического движка — библиотеки earstrip на C++ и WebAssembly под лицензией ISC. В C++ она на 14% быстрее earcut.hpp, в браузере — в 1,4–2,1 раза быстрее earcut.js. Автор по шагам разбирает, как отсечение ушей обогнало триангуляцию Делоне: отказ от лишних проверок, работа только с вогнутыми вершинами, пропуск выпуклых полигонов и другие оптимизации сократили время с 2,93 с до 489 мс.
Почти половина полигонов Мазовецкого воеводства — 1,8 млн — имеет четыре вершины или меньше. Треугольнику вообще не нужно отсечение, а выпуклый четырёхугольник — это два треугольника, и всё же код Делоне тратит на них 419 мс, строя каждую триангуляцию с нуля.
- morishuz
Круто. Улучшения производительности выглядят впечатляюще!
Я автор Delaunay32, триангулятора Делоне с ограничениями и поддержкой полигонов и отверстий. Он использует разделяй и властвуй, а не инкрементальную вставку, так что мне интересно, как он сравнится с базовым delaunay здесь.
https://github.com/morishuz/delaunay32
Я ещё не проводил бенчмарки на вашем корпусе, и наш текущий API для полигонов требует простых колец с непересекающимися отверстиями. Спасибо за публикацию наборов данных, они выглядят полезными для тестирования и сравнения!
- amelius
Стоит упомянуть мать всех триангуляторов:
- mistercow
Я давно задавался вопросом, почему отсечение ушей (ear clipping) с оптимизациями победило в триангуляции по сравнению с такими методами, как трапециевидный метод Сейделя, который имеет сложность O(n log* n) и естественно обрабатывает отверстия. Я знаю, что big-O — это не всё, но это по сути линейная сложность против квадратичной, и кажется, что мы заботимся о триангуляции всё более сложных полигонов со временем.
Это просто вопрос качества треугольников? Приводит ли Сейдель к слишком большому количеству сложных в обработке «щепок»?
- mourner
Привет, Евгений, здесь автор Earcut — спасибо за статью и действительно крутую библиотеку! Мне нужно посмотреть, есть ли какие-нибудь трюки, которые можно позаимствовать для JS-версии Earcut. :)
Стоит отметить, что я сознательно отказался от некоторых потенциальных оптимизаций, чтобы библиотека оставалась маленькой и размер бандла не раздувался — для большинства практических приложений (например, Mapbox GL JS) она уже достаточно быстра (и весит 4.1k min/gz). Интересно, насколько велика WASM-сборка Earstrip.
На стороне C++ Mapbox теперь использует гибридный подход: маленькие полигоны обрабатываются с помощью earcut.hpp, а большие и сложные полигоны переключаются на другой алгоритм, основанный на монотонной декомпозиции, потому что, хотя у него выше константы в алгоритмической сложности, он гораздо лучше масштабируется с размером входных данных.
- stymaar
Я вижу, что результат содержит множество очень длинных, очень тонких треугольников. Разве они обычно не являются худшим случаем для растризатора на GPU?