Мы выпустили earstrip — триангулятор полигонов из нашего картографического движка, — как небольшую библиотеку с открытым исходным кодом под лицензией ISC, той же, что используется в earcut. Она состоит из одного заголовочного файла C++ и сборки WebAssembly, опубликованной в npm, которая принимает те же аргументы, что и earcut. В C++ она работает на 14% быстрее earcut.hpp, а в браузере — в 1,4–2,1 раза быстрее earcut.js.
GPU умеет заполнять только треугольники, тогда как карта состоит в основном из полигонов: зданий, парков, парковок и полос травы между трамвайными путями. Прежде чем заполнить любой полигон, его контур нужно разрезать на треугольники. В нашей офлайн-карте Мазовецкого воеводства, региона вокруг Варшавы, на уровне масштабирования 13 содержится 3 740 425 полигонов. На одном ядре M4 Pro ограниченному триангулятору Делоне нашего движка потребовалось 2,93 секунды, чтобы обработать их все.
В октябре мы заменили его отсечением ушей. Триангуляция Делоне избегает вытянутых треугольников и полезна для интерполяции и моделирования, но плоская заливка не требует такого качества, а большая часть работы приходилась на простые фигуры. Почти половина полигонов Мазовии, 1,8 миллиона, имеет четыре вершины или меньше, однако код Делоне тратил 419 мс на построение их триангуляций с нуля. Отсечение ушей удаляет по одному углу за раз, и каждый простой полигон с более чем тремя вершинами имеет как минимум два непересекающихся уха, поэтому всегда найдётся очередной разрез.
Чтобы задокументировать работу, мы переписали отсекатель ушей по одной идее на коммит и замерили каждый шаг на тех же 3,7 миллиона полигонов. Итоговая версия обрабатывает весь набор данных за 489 мс — именно эта цифра вынесена в заголовок.
Источник: Hacker News · Сводку подготовил HeadlinesBriefing