Simplify.js — JavaScript-библиотека для упрощения ломаных линий

    Рад представить вашему вниманию еще одну крохотную, но полезную 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-запросы. Спасибо!

    Similar posts

    Ads
    AdBlock has stolen the banner, but banners are not teeth — they will be back

    More

    Comments 57

      –15
      И каковы возможные применения?
        +15
        Третий абзац, второе предложение.
          –1
          Мне вдруг стало интересно каковы возможные применения помимо картографии. Видимо стоило быть поконкретней.
            +4
            Кардиограммы рисовать в массовом количестве.
              +3
              Ну хотябы те же графики которые отображают реал-тайм данные, и у вас их 30 на странице. Вот и можно добавить hi-low переключатель, который для слабых маши будет уменьшать колличество одновременно отображаемых точек.
                +1
                Рисовалка. Если зажать мышку и долго рисовать линию, то получается очень много точек и со временем она начинает тормозить. Ну и плюс, если библиотека делает из ломаной линию на векторе, то не будет страшных углов.
                  0
                  Не вижу такой возможности в библиотеке. Но я бы сначала упростил линию, а потом её закруглил при помощи подобного алгоритма
                    0
                    У рисовалок часто несколько другой алгоритм. А именно — она сразу рисует точку на канве (слое, если есть возможность отмены), а не запоминает, как вы водите мышкой, а потом отрисовывает точки, именно из-за того, что очень быстро набирается огромное количество точек, которые не получится отрисовывать в режиме реального времени. Хотя в книгах очень как пример для рисовалки, делают именно так.
                    В тех рисовалках, где линия сглаживается автоматически — несколько иной алгоритм. Там много близлежащих точек заменяются одной, и затем все это сглаживается.
                  0
                  Хех, сижу с планшета свайп бесит, а без него бесит скорость ввода. Вспоминаю старую идею прикрутить к андроиду стенограмму гесс или системы александрова. Там как раз обработка кривых
                    0
                    Прикрутите Palm Graffiti или Xerox Unistroke… Вот это действительно круто :)
                    0
                    Медицина: любые приложения и задачи, где врач должен выделить какой-либо контур на каком-либо снимке.
                  +1
                  Визуализация кривых из большого количества точек — карты с векторными данными, динамические графики и т.д. Вот пример реального использования (громадный маршрут на Leaflet-карте): leaflet.cloudmade.com/debug/vector/vector.html
                    0
                    Вы правда не можете придумать применение кривым линиям?
                    Или это троллинг?
                      +2
                      Да ладно вам, случайно пропустил человек предложение в тексте… Давайте жить дружно :)
                        –1
                        Я не могу придумать применение (помимо картографии) огромному массиву точек, визуализацию которого нужно упрощать. Разве подобного рода упрощение не происходит на server-side? Не думаю что имеет смысл гонять кучу данных (координаты точек) от сервера к клиенту для того, чтобы уже на клиенте минимизировать количество визуализированных точек.
                          +2
                          Во-первых ты забыл, что JavaScript теперь активно используется и на сервере. :) Во-вторых передавать полные данные на клиент имеет смысл тогда, когда визуализировать их нужно динамически в зависимости от выбранного масштаба. Скажем, когда пользователь выделяет область на графике, чтобы к ней зазумиться, упрощение нужно пересчитывать (т.к. координаты с изменением масштаба тоже поменяются).
                            0
                            > ты забыл, что JavaScript теперь активно используется и на сервере.
                            я и вправду забыл. все вопросы снимаются)
                            • UFO just landed and posted this here
                            0
                            Финансовые системы
                        +2
                        Интересная библиотека. Смотрел-смотрел код — так и не нашёл к чему придраться :)
                          +1
                          Да, для меня написание подобных библиотек — отличное упражнение в умении писать чистый код. :) В маленьких масштабах это делать намного проще. И JSLint/JSHint помогает, конечно.
                            +2
                            Да уже по аккуратной демке сразу видно человека со вкусом и ясностью мышления :)
                              0
                              А я нашёл ;)

                              Таки функции для 3д можно было бы не спрятать под камментами, а вынести в отдельную библиотеку) Хотя всё равно круто.
                              +2
                              Очень полезная чтука. В свое время делал опять же для карт когда сертификацию гугля проходил.
                                0
                                Не знал, что Гугл проводил сертификацию по своим картам, интересно. :) Получили от этого пользу какую-то?
                                  +5
                                  бумажку, футболку и картинку
                                0
                                Не знаю, как называется алгоритм, но для кривой с более заметными изломами (например, синусоиды) я бы использовал примерно такой алгоритм:
                                есть длина r — минимальная длина прямого участка. Есть точки, идущие по очереди. Мы проходим от первой к последней перебором. Смотрим расстояние от предыдущей до текущей точки. Если оно больше r — идем дальше (получаем ключевую точку), если расстояние меньше — ищем среднюю между ними точку, она становится ключевой. Переходим к следующей точке. Если расстояние от нее до предыдущей (ключевой) точки меньше r — опять объеденяем, иначе мы опять наткнулись на ключевую точку, идем к следующей точке.
                                Преимущества — вероятнее, для синусоид будет быстрее работать. И более предсказуемое число точек получится. Ну и избежим рекурсии
                                  0
                                  Скорость всеже не ахти. Можно от 2х раз быстрее.
                                  Во первых сделайте первый проход через round(с нужной точность)
                                  ведь надо просто грубо отбросить вершины которые и так схлопнутся в одну точку. Зачем нам растояния когда работаем с пикселем?
                                  Во вторых — второй этап используется не правильно.
                                  Фактически у вас на руках мета информация про вероятность включения точки от эпсилон. ее можно расчитать один раз и использовать от зума к зуму.
                                  А это вроде как и не надо.
                                  Посмотрите пример что я выше давал — там эффект тотже, а сложность О(n).
                                    0
                                    Насчёт округления — во-первых, каким образом округление координат ускорит алгоритм? Проходить по всем точкам с O(n) для отсеивания нужно и в одном, и в другом случае, только вместо проверки dx * dx + dy * dy > tolerance (как делается сейчас) будет round(dx) === 0 && round(dy) === 0 (и даже не факт, что с округлением не будет медленнее).

                                    Во-вторых, вершины-то схлопнутся в одну точку, а вот рёбра будут рисоваться по-разному — можете сами проверить на канвасе. От дробной части координат зависит, как будет работать антиалиасинг ребра. И на моём демо это хорошо видно — проследите за тем, как меняется вид кривой в диапазоне tolerance до 1 пикселя.

                                    Насчёт второго этапа — буду очень удивлён, если действительно можно рассчитать такую независимую от порога меру и вы сможете описать такой расчёт. Мне это кажется невозможным, т.к. каждая итерация алгоритма Дугласа-Пекера зависит от выбора точек в предыдущих.

                                    Что касается вашего примера — к сожалению не могу оценить, насколько эффект хорош, т.к. ссылка на демо нерабочая (404). А это вами придуманный алгоритм или есть какая-то статья, его описывающая, с примерами и сравнением? Было бы здорово почитать.
                                      0
                                      шаг 1 — newX = Math.round(x*delta)/delta;
                                      тоесть меняем точность представления.
                                      Если вдруг x,y следуйщей точки совпадает с предыдущей — пропускаем.
                                      Возможно вы правы, и дельту считать будет быстрее(только не честное расстояние, а просто дельта отдельных координат. По сути обычная проверка на пересечение двух AABB. Она не такая точная если эпсилон велик, но там нужно на самом деле максимум 0.25 пикселя.

                                      шаг 2 — если вы в своем алгоритме будете работать правильно, тоесть выбирать точку с просто максимальным отклонением — то этот выбор будет всегда один и тотже.
                                      Отсев производиться потом под конкретный эпсилон.
                                      Примерно так работают полигоны на Яндекс.Картах когда вы их загружаете через YML — выдают массив точек с указанием с какого зума они видны.

                                      Пример у меня не совсем не живой и, конечно же, не такой красивый как у вас.
                                      Я так же, если честно, не совсем уверен что он до конца правильный — с момента публикации этой «чисто-для-гулга» версии прошло около трех лет, но если есть спортивный интерес — могу обновить его до текущей реализации.
                                        0
                                        Думаю, что полигоны и полилайны с KML/YML в Google/Яндекс-картах упрощаются на каждом зуме отдельно — массив точек с минимальным зумом вычисляются не одним общим алгоритмом, а запуском обычного 19-20 раз с разными наборами спроецированных точек.

                                        Общим алгоритмом можно вычислять только в том случае, если он является алгоритмом локальной обработки, т.е. отклонение в каждой точке меряется относительно фиксированных других (например, соседней левой и правой) и не зависит от предыдущих итераций. Но такие алгоритмы, хоть и линейные, насколько я понял из прочитанного в этой научной работе (pdf), очень неточные и производят множество артефактов в разных крайних случаях.

                                        Зато за счёт того, что вы натолкнули меня на более подробное изучение вопроса, нашёл еще два интересных алгоритма — Лэнга и Жао-Сэлфелда, которые обязательно попробую.
                                          0
                                          Еще раз посмотрите на картинку в Википедии
                                          Всегда выбирается точка на максимальном удалении.
                                          Просто когда это удаление становиться меньше нужного — алгоритм прерывается.
                                          Итого чтобы точка была видна на зуме 0 — нужно пойти вглубь готового дерева до тех пор пока дельта больше.
                                          Для zoom=1 — для дельты 0.5
                                          И тд и тп при условии построения данных для зума 0.
                                            0
                                            Я понял, о чём вы говорите. Но это имеет практическую пользу только в случае, если у нас есть в распоряжении громадное количество вычислительного времени, чтобы провести упрощение без предварительного отсеивания точек с минимальным порогом. Там, где нужна быстрая обработка в реальном времени, такой подход не работает.
                                    0
                                    Заметно дрожание, видимо слишком привязано к шагу (четный, нечетный), по мне так должно быть более стабильно. offtop: Нет ли у Вас алгоритма для преобразования (нахождения) дуг/окружностей в массиве точек?
                                      0
                                      Насчёт дрожания — это следствие предварительного отсеивания точек, о котором я писал в статье. Можно сделать без него, но тогда будет работать раз в 10 медленнее, что недопустимо.

                                      Насчёт дуг/окружностей — нет, таким не занимался.
                                        0
                                        Нахождение дуг и окружностей в массиве точек — это уже из серии поиска фигур на изображении. Тут вам поможет преобразование Хафа.
                                          0
                                          Добавил возможность включения режима максимального качества, при котором дрожания нет (можете посмотреть и сравнить потери точности с потерями производительности): mourner.github.com/simplify-js/
                                          0
                                          Спасибо! Жалко что я не знал вашей либы когда чис. методы проходил…
                                          • UFO just landed and posted this here
                                              0
                                              Мне тоже мат. опыта не хватало, но, к счастью, Гугл многое знает по запросу «polyline simplification». :)
                                              0
                                              А если есть несколько полигонов прилегающих друг к другу. Как упростить их границы (состоящие как раз из кривых линий) так, чтобы границы полигонов после этого остались прилегать друг к другу?
                                                0
                                                Хороший вопрос… Если речь идёт об упрощении перед отображением на экране, то при не очень большом пороге разницей на стыках можно пренебречь — ее не будет видно. А вот если серьёзно подходить к вопросу, нужно придумывать алгоритм…

                                                Мне представляется следующий — перебрать каждую точку каждого полигона, храня хэш с ключём по координатам и значением — кол-вом раз, которые точка встретилась. Потом пройтись по каждому полигону и при каждом изменении кол-ва в точке разбивать в этом месте полигон на части (скажем, первые 100 точек встречаются один раз, потом вдруг пошли точки по 2 — разбить на стыке). Потом упрощаем каждую «часть» каждого полигона. Алгоритм упрощения на одинаковых частях будет работать одинаково.
                                                  0
                                                  Хорошая идея, я об этом же подумал… Попробую…
                                                0
                                                Кстати, если исходная кривая будет замкнутая или почти замкнутая (а это как раз случай, если алгоритм применяется для упрощения полигона, вводимого пользователем мышкой), то алгоритм выдаст неверную кривую.
                                                  0
                                                  Почему неверную? Можно самый простой тест-кейс, в котором неправильно срабатывает? По моему опыту, отлично работает и на полигонах.
                                                    0
                                                    Я имел в виду исходный алгоритм Рамера-Дугласа-Пекера без проведения предварительных шагов (отсеивания). Мой опыт показывает, что пользователь может замкнуть контур так, что получится самопересечение. В этом случае алгоритм отработает неправильно. Да и из математики видно, если вдруг координаты первой и последней точек совпадут, то мы и прямой не получим.
                                                      0
                                                      Даже при самопересечении не могу придумать случая, когда алгоритм себя плохо поведёт. :) В случае совпадения первой и последней он поведёт себя правильно засчёт того, что расстояние рассчитывается не к прямой, а к отрезку — если перпендикуляр на него не попадает, то берётся меньшее из двух расстояний к краям.
                                                        0
                                                        Давайте дальше в ЛС прдолжим, чтобы страницу не захламлять.
                                                  0
                                                  Спасибо! Попробовал переписать на ActionScript3 — вроде все работает.
                                                    0
                                                    Не совсем понимаю, зачем использовать выражение

                                                    typeof Uint8Array !== undefined + '' вместо typeof Uint8Array != «undefined».
                                                      0
                                                      Переменная undefined минимизируется в одну букву, получается компактнее. :)
                                                        0
                                                        Да это-то понятно. Я не об этом… почему просто написать

                                                        MarkerArray = Uint8Array || Array;

                                                          0
                                                          Если написать так, то в браузерах, не поддерживающих Uint8Array, выдаст ошибку. Ее можно было бы исправить, написав window.Uint8Array, но учитывая то, что код писался не только под браузеры, но и под node.js и подобные среды, изначальный вариант самый универсальный.
                                                            0
                                                            Так вы же IE вроде не поддерживаете здесь mourner.github.com/simplify-js/ или я что-то путаю.
                                                              0
                                                              Поддерживаю, конечно.
                                                              0
                                                              Да, безусловно нужен контекст, global.Uint8Array.

                                                      Only users with full accounts can post comments. Log in, please.