Комментарии 17
А для чего вам генерализация именно в плоскости экрана? Почему нельзя генерализовать все маркера один раз в плоскости карты и больше не трогать. Кажется, изменения перспективы не должны драматически портить визуал.
Ну и второй связанный вопрос, если вы постоянно пересчитываете генерализацию, то как решаете и решаете ли проблему её стабильности и отсутствия мерцаний маркеров в окрестностях конфликтующих позиций?
В 2D-карте мы так и делали (вычисляли генерализацию один раз для каждого целочисленного зума), но в 3D, если сильно наклонить карту, маркеры будут всё же сильно наезжать друг на друга — выглядит это не очень.
С нестабильностью боремся несколькими способами:
1. Маркерам, которые в данный момент видны на экране, поднимаем в генерализации приоритет.
2. Маркерам, которые в данный момент не видны на экране, при проверке пересечения расширяем баунд на несколько пикселей.
Эти подходы значительно снижают мерцание и позволяют добиться приемлемой (хоть и неидеальной) стабильности.
С нестабильностью боремся несколькими способами:
1. Маркерам, которые в данный момент видны на экране, поднимаем в генерализации приоритет.
2. Маркерам, которые в данный момент не видны на экране, при проверке пересечения расширяем баунд на несколько пикселей.
Эти подходы значительно снижают мерцание и позволяют добиться приемлемой (хоть и неидеальной) стабильности.
Бета выводит сообщение
Только для больших, но в браузере DuckDuckGo и FireFox Focus отображается нормально. Тормозит меньше, чем текущая карта (кликать только нельзя). Тело BQ x32. Обратите внимание, что расположение окна в подвале не учитывает, что адресная строка браузеров сворачивается, когда листаю карту вниз.
Почему не QuadTree использовался? Есть его волшебная модификация Loose QuadTree. Вот ссылка на чудесное описание — долистайте до заголовка «4. Loose Quadtree».
В вашем случае можно было обойтись и обычным с модифицированной логикой вставки элемента: Если размер области ноды равны ширине двух маркеров и нода собралась делиться, то забить. И там же проверять — если элемент накладывается на соседний, то прервать процесс добавления. Оптимально должно получиться на двух и четырёх элементах до переполнения.
В вашем случае можно было обойтись и обычным с модифицированной логикой вставки элемента: Если размер области ноды равны ширине двух маркеров и нода собралась делиться, то забить. И там же проверять — если элемент накладывается на соседний, то прервать процесс добавления. Оптимально должно получиться на двух и четырёх элементах до переполнения.
Нельзя понять, с чем именно пересекается маркер. Буфер только хранит данные о том, какие пиксели заняты, а какие нет. Следовательно, невозможно реализовать операцию, которая вернёт список маркеров, пересекающихся с данным.
Что если отказаться от оптимизации подхода с буфером и в буфере хранить не 0/1, а индекс элемента в массиве? Соответственно при добавлении нового маркера на карту класть его в массив, а элементы буфера заполнять значением индекса. Если использовать Uint16Array вместо Uint8Array то на карту уместится до 65535 маркеров (хотя при размере маркера 30x50 даже 255 элементов должно всегда хватать).
Да, так можно сделать! Помимо количества маркеров, ещё одно важное ограничение такого подхода в том, что не получится хранить пересекающиеся баунды, так как каждый пиксель может хранить только один индекс.
К сожалению, для наших требований к генерализации подписей это критично: у нас есть подписи разных типов, и некоторым типам нужно разрешать пересекаться с другими. Из-за этого при проверке возможности вставки нужно знать полный список пересечений.
К сожалению, для наших требований к генерализации подписей это критично: у нас есть подписи разных типов, и некоторым типам нужно разрешать пересекаться с другими. Из-за этого при проверке возможности вставки нужно знать полный список пересечений.
Подскажите, не даст ли больший выиграш переход на WASM, вместо таких оптимизаций?
Современные браузеры оптимизируют исполнение JS так хорошо, что переход на WASM, как правило, не даёт значительного роста производительности. Выигрыш от правильного выбора алгоритма и структуры данных для решения задачи всегда будет выше.
Мы экспериментировали с asm.js и даже реализовывали на нём генерализацию (писали asm.js-код вручную). Впоследствии отказались от этой технологии ради читаемости кода и переписали всё на обычный JavaScript. Точных чисел не вспомню, но ухудшение производительности было некритичным.
Мы экспериментировали с asm.js и даже реализовывали на нём генерализацию (писали asm.js-код вручную). Впоследствии отказались от этой технологии ради читаемости кода и переписали всё на обычный JavaScript. Точных чисел не вспомню, но ухудшение производительности было некритичным.
Как я почти решил эту проблему (не было задачи наклонять)
1. Берем github.com/mourner/flatbush
2. Начинаем добавлять точки, только маленького размера
3. Постепенно увеличиваем размер (по сути k-nearest neightbours) — очень важно понять в каком порядке точки друг на друга накладываются, сохраняем указатель на тот маркер, который «самый главный»
4.…
5. делаем выборку по bounding box маркера, прося только один результат (такого метода в flatbush нет), получаем leaderMarkerId, и таким образом формируем список маркеров который надо показать.
Это работает за O(nlogn), где «logn», ака «глубина дерева» обычно не более 10. Самое главное — данные добавляются в RTree только один раз, далее идут чтения.
1. Берем github.com/mourner/flatbush
2. Начинаем добавлять точки, только маленького размера
3. Постепенно увеличиваем размер (по сути k-nearest neightbours) — очень важно понять в каком порядке точки друг на друга накладываются, сохраняем указатель на тот маркер, который «самый главный»
4.…
5. делаем выборку по bounding box маркера, прося только один результат (такого метода в flatbush нет), получаем leaderMarkerId, и таким образом формируем список маркеров который надо показать.
Это работает за O(nlogn), где «logn», ака «глубина дерева» обычно не более 10. Самое главное — данные добавляются в RTree только один раз, далее идут чтения.
Самое главное — данные добавляются в RTree только один раз, далее идут чтения.Вставлять в R-дерево пачку элементов разом действительно выгоднее, чем по одному (в библиотеке RBush даже сделан специальный метод для этого).
У нас, правда, на экране обычно отображается очень малая часть от общего числа маркеров: всего их могут быть десятки тысяч, а на экране редко умещается больше пары сотен. Поэтому мы добавляем в дерево только те элементы, которые будут отображены (делая проверку перед каждой вставкой). Несмотря на то, что элементы таким образом приходится добавлять по одному, получается намного быстрее.
> Вставлять в R-дерево пачку элементов разом действительно выгоднее, чем по одному (в библиотеке RBush даже сделан специальный метод для этого).
А в flatbush другого метода так вообще нет. Но, прочитай алгоритм еще раз,- вставка данных производится __вообще__ один раз.
Далее как не мотай или зум меняй — только чтения.
Плюс можно использовать еще одну библиотеку, опять же от mourner — supercluster , которая сделает что-то типа иерхического z-index, отдаленно напоминащее ваше решение.
Кстати да — если вам добавить «early-z» — будет вообще летать.
А в flatbush другого метода так вообще нет. Но, прочитай алгоритм еще раз,- вставка данных производится __вообще__ один раз.
Далее как не мотай или зум меняй — только чтения.
Плюс можно использовать еще одну библиотеку, опять же от mourner — supercluster , которая сделает что-то типа иерхического z-index, отдаленно напоминащее ваше решение.
Кстати да — если вам добавить «early-z» — будет вообще летать.
Извините за офтоп, но то здание что изображено на КДПВ- бредни дизайнера, или реально существующий объект?
Дмитрий, это технопарк новосибирского Академгородка.
Вот пруф на карте.
Вот пруф на карте.
А что случилось с Dialer? Очень нравилась звонилка.
Скорость работы в Edge вас наверняка удивит )
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Быстрая генерализация маркеров на WebGL-карте