Рад представить вашему вниманию еще одну крохотную, но полезную open-source-утилиту своего авторства — Simplify.js.Simplify.js — очень быстрая реализация упрощения ломаных линий на JavaScript. Изначально написав ее для Leaflet (библиотеки для интерактивных карт), после небольшого эксперимента по оптимизации захотелось выпустить ее в качестве отдельной библиотеки без зависимостей, которую можно использовать как в браузере, так и на серверных платформах, таких, как Node.js, и применять и для 2D, и для 3D-точек.
Подобное упрощение позволяет на несколько порядков уменьшить количество точек в ломаной линии (например, представляющей длинный маршрут на карте или график), при этом максимально сохранив ее очертания (с заданной точностью). Соответственно резко уменьшается занимаемый линией размер памяти и время, требуемое для ее обработки.Благодаря этому можно, например, рисовать кривые из десятков и даже сотен тысяч точек в браузере с помощью SVG или Canvas без особых тормозов. Убедиться в этом можно, посмотрев демонстрацию на сайте и соответствущий тест на JSPerf.
Использование тривиально:
var points = [{x: 23, y: 53}, …];
…
var simplified = simplify(points, 1.0);
Simplify.js использует алгоритм Дугласа-Пекера, применяемый к массиву точек, предварительно отсеянному на основе близости точек друг к другу (что за счёт незначительной потери точности ускоряет применение алгоритма примерно в десять раз), не использует дорогих операций, таких, как копирование и сортировка массивов, и применяет типизированные массивы в браузерах, которые это поддерживают.
Сайт библиотеки: mourner.github.com/simplify-js/
Код на GitHub: github.com/mourner/simplify-js/
Пакет NPM: simplify-js
Лицензия: BSD
Если придумаете, как это оптимизировать еще сильнее — буду рад видеть ваши pull-запросы. Спасибо!
