Самое главное — данные добавляются в RTree только один раз, далее идут чтения.
Вставлять в R-дерево пачку элементов разом действительно выгоднее, чем по одному (в библиотеке RBush даже сделан специальный метод для этого).
У нас, правда, на экране обычно отображается очень малая часть от общего числа маркеров: всего их могут быть десятки тысяч, а на экране редко умещается больше пары сотен. Поэтому мы добавляем в дерево только те элементы, которые будут отображены (делая проверку перед каждой вставкой). Несмотря на то, что элементы таким образом приходится добавлять по одному, получается намного быстрее.
Современные браузеры оптимизируют исполнение JS так хорошо, что переход на WASM, как правило, не даёт значительного роста производительности. Выигрыш от правильного выбора алгоритма и структуры данных для решения задачи всегда будет выше.
Мы экспериментировали с asm.js и даже реализовывали на нём генерализацию (писали asm.js-код вручную). Впоследствии отказались от этой технологии ради читаемости кода и переписали всё на обычный JavaScript. Точных чисел не вспомню, но ухудшение производительности было некритичным.
Да, так можно сделать! Помимо количества маркеров, ещё одно важное ограничение такого подхода в том, что не получится хранить пересекающиеся баунды, так как каждый пиксель может хранить только один индекс.
К сожалению, для наших требований к генерализации подписей это критично: у нас есть подписи разных типов, и некоторым типам нужно разрешать пересекаться с другими. Из-за этого при проверке возможности вставки нужно знать полный список пересечений.
Дерево квадрантов одно время мы использовали; конкретную реализацию не вспомню (что-то с npm), но это был обычный (не loose) вариант без каких-либо модификаций. RBush в сравнении с ним показал намного лучшую производительность, поэтому решили перейти на него.
В 2D-карте мы так и делали (вычисляли генерализацию один раз для каждого целочисленного зума), но в 3D, если сильно наклонить карту, маркеры будут всё же сильно наезжать друг на друга — выглядит это не очень.
С нестабильностью боремся несколькими способами:
1. Маркерам, которые в данный момент видны на экране, поднимаем в генерализации приоритет.
2. Маркерам, которые в данный момент не видны на экране, при проверке пересечения расширяем баунд на несколько пикселей.
Эти подходы значительно снижают мерцание и позволяют добиться приемлемой (хоть и неидеальной) стабильности.
У крупных магазинов вроде Икеи или Ашана маркер всегда находится в центре большого помещения, далеко от других иконок; и для того, чтобы его начали скрывать туалеты, нужно очень-очень далеко отзумиться. Так что с их заметностью проблем не бывает.
Просто в Краснодаре пока нет торговых центров с Этажами :( Если у ТЦ имеется поэтажный план, в его карточке появляется специальная кнопка для входа в этот режим.
У нас, правда, на экране обычно отображается очень малая часть от общего числа маркеров: всего их могут быть десятки тысяч, а на экране редко умещается больше пары сотен. Поэтому мы добавляем в дерево только те элементы, которые будут отображены (делая проверку перед каждой вставкой). Несмотря на то, что элементы таким образом приходится добавлять по одному, получается намного быстрее.
Мы экспериментировали с asm.js и даже реализовывали на нём генерализацию (писали asm.js-код вручную). Впоследствии отказались от этой технологии ради читаемости кода и переписали всё на обычный JavaScript. Точных чисел не вспомню, но ухудшение производительности было некритичным.
К сожалению, для наших требований к генерализации подписей это критично: у нас есть подписи разных типов, и некоторым типам нужно разрешать пересекаться с другими. Из-за этого при проверке возможности вставки нужно знать полный список пересечений.
Дерево квадрантов одно время мы использовали; конкретную реализацию не вспомню (что-то с npm), но это был обычный (не loose) вариант без каких-либо модификаций. RBush в сравнении с ним показал намного лучшую производительность, поэтому решили перейти на него.
С нестабильностью боремся несколькими способами:
1. Маркерам, которые в данный момент видны на экране, поднимаем в генерализации приоритет.
2. Маркерам, которые в данный момент не видны на экране, при проверке пересечения расширяем баунд на несколько пикселей.
Эти подходы значительно снижают мерцание и позволяют добиться приемлемой (хоть и неидеальной) стабильности.
Только результат будет скорее похож на заставку «Лабиринт» из Windows 95)
Спасибо за замечания, обязательно будем смотреть и править)