Комментарии 57
И каковы возможные применения?
Третий абзац, второе предложение.
Мне вдруг стало интересно каковы возможные применения помимо картографии. Видимо стоило быть поконкретней.
Кардиограммы рисовать в массовом количестве.
Ну хотябы те же графики которые отображают реал-тайм данные, и у вас их 30 на странице. Вот и можно добавить hi-low переключатель, который для слабых маши будет уменьшать колличество одновременно отображаемых точек.
Рисовалка. Если зажать мышку и долго рисовать линию, то получается очень много точек и со временем она начинает тормозить. Ну и плюс, если библиотека делает из ломаной линию на векторе, то не будет страшных углов.
Не вижу такой возможности в библиотеке. Но я бы сначала упростил линию, а потом её закруглил при помощи подобного алгоритма
У рисовалок часто несколько другой алгоритм. А именно — она сразу рисует точку на канве (слое, если есть возможность отмены), а не запоминает, как вы водите мышкой, а потом отрисовывает точки, именно из-за того, что очень быстро набирается огромное количество точек, которые не получится отрисовывать в режиме реального времени. Хотя в книгах очень как пример для рисовалки, делают именно так.
В тех рисовалках, где линия сглаживается автоматически — несколько иной алгоритм. Там много близлежащих точек заменяются одной, и затем все это сглаживается.
В тех рисовалках, где линия сглаживается автоматически — несколько иной алгоритм. Там много близлежащих точек заменяются одной, и затем все это сглаживается.
Ну да, я в одном из топиков в комментах приводил пример работы в Гимпе.
Хех, сижу с планшета свайп бесит, а без него бесит скорость ввода. Вспоминаю старую идею прикрутить к андроиду стенограмму гесс или системы александрова. Там как раз обработка кривых
Медицина: любые приложения и задачи, где врач должен выделить какой-либо контур на каком-либо снимке.
Визуализация кривых из большого количества точек — карты с векторными данными, динамические графики и т.д. Вот пример реального использования (громадный маршрут на Leaflet-карте): leaflet.cloudmade.com/debug/vector/vector.html
Вы правда не можете придумать применение кривым линиям?
Или это троллинг?
Или это троллинг?
Да ладно вам, случайно пропустил человек предложение в тексте… Давайте жить дружно :)
Я не могу придумать применение (помимо картографии) огромному массиву точек, визуализацию которого нужно упрощать. Разве подобного рода упрощение не происходит на server-side? Не думаю что имеет смысл гонять кучу данных (координаты точек) от сервера к клиенту для того, чтобы уже на клиенте минимизировать количество визуализированных точек.
Во-первых ты забыл, что JavaScript теперь активно используется и на сервере. :) Во-вторых передавать полные данные на клиент имеет смысл тогда, когда визуализировать их нужно динамически в зависимости от выбранного масштаба. Скажем, когда пользователь выделяет область на графике, чтобы к ней зазумиться, упрощение нужно пересчитывать (т.к. координаты с изменением масштаба тоже поменяются).
Финансовые системы
Интересная библиотека. Смотрел-смотрел код — так и не нашёл к чему придраться :)
Да, для меня написание подобных библиотек — отличное упражнение в умении писать чистый код. :) В маленьких масштабах это делать намного проще. И JSLint/JSHint помогает, конечно.
Да уже по аккуратной демке сразу видно человека со вкусом и ясностью мышления :)
А я нашёл ;)
Таки функции для 3д можно было бы не спрятать под камментами, а вынести в отдельную библиотеку) Хотя всё равно круто.
Таки функции для 3д можно было бы не спрятать под камментами, а вынести в отдельную библиотеку) Хотя всё равно круто.
Очень полезная чтука. В свое время делал опять же для карт когда сертификацию гугля проходил.
Не знаю, как называется алгоритм, но для кривой с более заметными изломами (например, синусоиды) я бы использовал примерно такой алгоритм:
есть длина r — минимальная длина прямого участка. Есть точки, идущие по очереди. Мы проходим от первой к последней перебором. Смотрим расстояние от предыдущей до текущей точки. Если оно больше r — идем дальше (получаем ключевую точку), если расстояние меньше — ищем среднюю между ними точку, она становится ключевой. Переходим к следующей точке. Если расстояние от нее до предыдущей (ключевой) точки меньше r — опять объеденяем, иначе мы опять наткнулись на ключевую точку, идем к следующей точке.
Преимущества — вероятнее, для синусоид будет быстрее работать. И более предсказуемое число точек получится. Ну и избежим рекурсии
есть длина r — минимальная длина прямого участка. Есть точки, идущие по очереди. Мы проходим от первой к последней перебором. Смотрим расстояние от предыдущей до текущей точки. Если оно больше r — идем дальше (получаем ключевую точку), если расстояние меньше — ищем среднюю между ними точку, она становится ключевой. Переходим к следующей точке. Если расстояние от нее до предыдущей (ключевой) точки меньше r — опять объеденяем, иначе мы опять наткнулись на ключевую точку, идем к следующей точке.
Преимущества — вероятнее, для синусоид будет быстрее работать. И более предсказуемое число точек получится. Ну и избежим рекурсии
Скорость всеже не ахти. Можно от 2х раз быстрее.
Во первых сделайте первый проход через round(с нужной точность)
ведь надо просто грубо отбросить вершины которые и так схлопнутся в одну точку. Зачем нам растояния когда работаем с пикселем?
Во вторых — второй этап используется не правильно.
Фактически у вас на руках мета информация про вероятность включения точки от эпсилон. ее можно расчитать один раз и использовать от зума к зуму.
А это вроде как и не надо.
Посмотрите пример что я выше давал — там эффект тотже, а сложность О(n).
Во первых сделайте первый проход через round(с нужной точность)
ведь надо просто грубо отбросить вершины которые и так схлопнутся в одну точку. Зачем нам растояния когда работаем с пикселем?
Во вторых — второй этап используется не правильно.
Фактически у вас на руках мета информация про вероятность включения точки от эпсилон. ее можно расчитать один раз и использовать от зума к зуму.
А это вроде как и не надо.
Посмотрите пример что я выше давал — там эффект тотже, а сложность О(n).
Насчёт округления — во-первых, каким образом округление координат ускорит алгоритм? Проходить по всем точкам с O(n) для отсеивания нужно и в одном, и в другом случае, только вместо проверки dx * dx + dy * dy > tolerance (как делается сейчас) будет round(dx) === 0 && round(dy) === 0 (и даже не факт, что с округлением не будет медленнее).
Во-вторых, вершины-то схлопнутся в одну точку, а вот рёбра будут рисоваться по-разному — можете сами проверить на канвасе. От дробной части координат зависит, как будет работать антиалиасинг ребра. И на моём демо это хорошо видно — проследите за тем, как меняется вид кривой в диапазоне tolerance до 1 пикселя.
Насчёт второго этапа — буду очень удивлён, если действительно можно рассчитать такую независимую от порога меру и вы сможете описать такой расчёт. Мне это кажется невозможным, т.к. каждая итерация алгоритма Дугласа-Пекера зависит от выбора точек в предыдущих.
Что касается вашего примера — к сожалению не могу оценить, насколько эффект хорош, т.к. ссылка на демо нерабочая (404). А это вами придуманный алгоритм или есть какая-то статья, его описывающая, с примерами и сравнением? Было бы здорово почитать.
Во-вторых, вершины-то схлопнутся в одну точку, а вот рёбра будут рисоваться по-разному — можете сами проверить на канвасе. От дробной части координат зависит, как будет работать антиалиасинг ребра. И на моём демо это хорошо видно — проследите за тем, как меняется вид кривой в диапазоне tolerance до 1 пикселя.
Насчёт второго этапа — буду очень удивлён, если действительно можно рассчитать такую независимую от порога меру и вы сможете описать такой расчёт. Мне это кажется невозможным, т.к. каждая итерация алгоритма Дугласа-Пекера зависит от выбора точек в предыдущих.
Что касается вашего примера — к сожалению не могу оценить, насколько эффект хорош, т.к. ссылка на демо нерабочая (404). А это вами придуманный алгоритм или есть какая-то статья, его описывающая, с примерами и сравнением? Было бы здорово почитать.
шаг 1 — newX = Math.round(x*delta)/delta;
тоесть меняем точность представления.
Если вдруг x,y следуйщей точки совпадает с предыдущей — пропускаем.
Возможно вы правы, и дельту считать будет быстрее(только не честное расстояние, а просто дельта отдельных координат. По сути обычная проверка на пересечение двух AABB. Она не такая точная если эпсилон велик, но там нужно на самом деле максимум 0.25 пикселя.
шаг 2 — если вы в своем алгоритме будете работать правильно, тоесть выбирать точку с просто максимальным отклонением — то этот выбор будет всегда один и тотже.
Отсев производиться потом под конкретный эпсилон.
Примерно так работают полигоны на Яндекс.Картах когда вы их загружаете через YML — выдают массив точек с указанием с какого зума они видны.
Пример у меня не совсем не живой и, конечно же, не такой красивый как у вас.
Я так же, если честно, не совсем уверен что он до конца правильный — с момента публикации этой «чисто-для-гулга» версии прошло около трех лет, но если есть спортивный интерес — могу обновить его до текущей реализации.
тоесть меняем точность представления.
Если вдруг x,y следуйщей точки совпадает с предыдущей — пропускаем.
Возможно вы правы, и дельту считать будет быстрее(только не честное расстояние, а просто дельта отдельных координат. По сути обычная проверка на пересечение двух AABB. Она не такая точная если эпсилон велик, но там нужно на самом деле максимум 0.25 пикселя.
шаг 2 — если вы в своем алгоритме будете работать правильно, тоесть выбирать точку с просто максимальным отклонением — то этот выбор будет всегда один и тотже.
Отсев производиться потом под конкретный эпсилон.
Примерно так работают полигоны на Яндекс.Картах когда вы их загружаете через YML — выдают массив точек с указанием с какого зума они видны.
Пример у меня не совсем не живой и, конечно же, не такой красивый как у вас.
Я так же, если честно, не совсем уверен что он до конца правильный — с момента публикации этой «чисто-для-гулга» версии прошло около трех лет, но если есть спортивный интерес — могу обновить его до текущей реализации.
Думаю, что полигоны и полилайны с KML/YML в Google/Яндекс-картах упрощаются на каждом зуме отдельно — массив точек с минимальным зумом вычисляются не одним общим алгоритмом, а запуском обычного 19-20 раз с разными наборами спроецированных точек.
Общим алгоритмом можно вычислять только в том случае, если он является алгоритмом локальной обработки, т.е. отклонение в каждой точке меряется относительно фиксированных других (например, соседней левой и правой) и не зависит от предыдущих итераций. Но такие алгоритмы, хоть и линейные, насколько я понял из прочитанного в этой научной работе (pdf), очень неточные и производят множество артефактов в разных крайних случаях.
Зато за счёт того, что вы натолкнули меня на более подробное изучение вопроса, нашёл еще два интересных алгоритма — Лэнга и Жао-Сэлфелда, которые обязательно попробую.
Общим алгоритмом можно вычислять только в том случае, если он является алгоритмом локальной обработки, т.е. отклонение в каждой точке меряется относительно фиксированных других (например, соседней левой и правой) и не зависит от предыдущих итераций. Но такие алгоритмы, хоть и линейные, насколько я понял из прочитанного в этой научной работе (pdf), очень неточные и производят множество артефактов в разных крайних случаях.
Зато за счёт того, что вы натолкнули меня на более подробное изучение вопроса, нашёл еще два интересных алгоритма — Лэнга и Жао-Сэлфелда, которые обязательно попробую.
Еще раз посмотрите на картинку в Википедии
Всегда выбирается точка на максимальном удалении.
Просто когда это удаление становиться меньше нужного — алгоритм прерывается.
Итого чтобы точка была видна на зуме 0 — нужно пойти вглубь готового дерева до тех пор пока дельта больше.
Для zoom=1 — для дельты 0.5
И тд и тп при условии построения данных для зума 0.
Всегда выбирается точка на максимальном удалении.
Просто когда это удаление становиться меньше нужного — алгоритм прерывается.
Итого чтобы точка была видна на зуме 0 — нужно пойти вглубь готового дерева до тех пор пока дельта больше.
Для zoom=1 — для дельты 0.5
И тд и тп при условии построения данных для зума 0.
Я понял, о чём вы говорите. Но это имеет практическую пользу только в случае, если у нас есть в распоряжении громадное количество вычислительного времени, чтобы провести упрощение без предварительного отсеивания точек с минимальным порогом. Там, где нужна быстрая обработка в реальном времени, такой подход не работает.
Заметно дрожание, видимо слишком привязано к шагу (четный, нечетный), по мне так должно быть более стабильно. offtop: Нет ли у Вас алгоритма для преобразования (нахождения) дуг/окружностей в массиве точек?
Насчёт дрожания — это следствие предварительного отсеивания точек, о котором я писал в статье. Можно сделать без него, но тогда будет работать раз в 10 медленнее, что недопустимо.
Насчёт дуг/окружностей — нет, таким не занимался.
Насчёт дуг/окружностей — нет, таким не занимался.
Нахождение дуг и окружностей в массиве точек — это уже из серии поиска фигур на изображении. Тут вам поможет преобразование Хафа.
Добавил возможность включения режима максимального качества, при котором дрожания нет (можете посмотреть и сравнить потери точности с потерями производительности): mourner.github.com/simplify-js/
Спасибо! Жалко что я не знал вашей либы когда чис. методы проходил…
НЛО прилетело и опубликовало эту надпись здесь
А если есть несколько полигонов прилегающих друг к другу. Как упростить их границы (состоящие как раз из кривых линий) так, чтобы границы полигонов после этого остались прилегать друг к другу?
Хороший вопрос… Если речь идёт об упрощении перед отображением на экране, то при не очень большом пороге разницей на стыках можно пренебречь — ее не будет видно. А вот если серьёзно подходить к вопросу, нужно придумывать алгоритм…
Мне представляется следующий — перебрать каждую точку каждого полигона, храня хэш с ключём по координатам и значением — кол-вом раз, которые точка встретилась. Потом пройтись по каждому полигону и при каждом изменении кол-ва в точке разбивать в этом месте полигон на части (скажем, первые 100 точек встречаются один раз, потом вдруг пошли точки по 2 — разбить на стыке). Потом упрощаем каждую «часть» каждого полигона. Алгоритм упрощения на одинаковых частях будет работать одинаково.
Мне представляется следующий — перебрать каждую точку каждого полигона, храня хэш с ключём по координатам и значением — кол-вом раз, которые точка встретилась. Потом пройтись по каждому полигону и при каждом изменении кол-ва в точке разбивать в этом месте полигон на части (скажем, первые 100 точек встречаются один раз, потом вдруг пошли точки по 2 — разбить на стыке). Потом упрощаем каждую «часть» каждого полигона. Алгоритм упрощения на одинаковых частях будет работать одинаково.
Кстати, если исходная кривая будет замкнутая или почти замкнутая (а это как раз случай, если алгоритм применяется для упрощения полигона, вводимого пользователем мышкой), то алгоритм выдаст неверную кривую.
Почему неверную? Можно самый простой тест-кейс, в котором неправильно срабатывает? По моему опыту, отлично работает и на полигонах.
Я имел в виду исходный алгоритм Рамера-Дугласа-Пекера без проведения предварительных шагов (отсеивания). Мой опыт показывает, что пользователь может замкнуть контур так, что получится самопересечение. В этом случае алгоритм отработает неправильно. Да и из математики видно, если вдруг координаты первой и последней точек совпадут, то мы и прямой не получим.
Даже при самопересечении не могу придумать случая, когда алгоритм себя плохо поведёт. :) В случае совпадения первой и последней он поведёт себя правильно засчёт того, что расстояние рассчитывается не к прямой, а к отрезку — если перпендикуляр на него не попадает, то берётся меньшее из двух расстояний к краям.
Спасибо! Попробовал переписать на ActionScript3 — вроде все работает.
Не совсем понимаю, зачем использовать выражение
typeof Uint8Array !== undefined + '' вместо typeof Uint8Array != «undefined».
typeof Uint8Array !== undefined + '' вместо typeof Uint8Array != «undefined».
Переменная undefined минимизируется в одну букву, получается компактнее. :)
Да это-то понятно. Я не об этом… почему просто написать
MarkerArray = Uint8Array || Array;
MarkerArray = Uint8Array || Array;
Если написать так, то в браузерах, не поддерживающих Uint8Array, выдаст ошибку. Ее можно было бы исправить, написав window.Uint8Array, но учитывая то, что код писался не только под браузеры, но и под node.js и подобные среды, изначальный вариант самый универсальный.
Так вы же IE вроде не поддерживаете здесь mourner.github.com/simplify-js/ или я что-то путаю.
Да, безусловно нужен контекст, global.Uint8Array.
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Simplify.js — JavaScript-библиотека для упрощения ломаных линий