Карта с более чем 1 миллионом маркеров, выдача при высоком уровне масштабирования

Question

Контекст:

Google Map с 1 миллионом маркеров (объект с широтой / долготой) для отображения. Мы используем Fluster 2 для кластеризации.

Для уровня масштабирования от 11 до 21 (при условии, что имеется 21 уровень масштабирования, а 21 - ближе всего к земле), время вычислений для кластерных маркеров (создания кластерных маркеров) хорошо.

Проблема, с которой я сталкиваюсь:

Агломерационная кластеризация замедляется после увеличения 11 (когда пользователь уменьшает масштаб от земли). Учитывая количество маркеров, около 1 000 000, мне нужен либо быстрый метод вычисления, либо оборот.

Кстати, меня не интересуют коммерческие решения.

Answer 1

Fluster 2 - это javascript, который является кластеризацией на стороне клиента, верно?

С миллионами точек, которые вы должны рассмотреть, обязательно используйте кластеризацию на стороне сервера или даже предкластерные точки заранее, если это возможно.

Эта тема связана с этим https://stackoverflow.com/questions/986852/clustering-coordinates-on-server-side

С таким количеством точек вы можете сделать простую кластеризацию сетки.Это быстрый метод, как упомянуто google http://code.google.com/intl/da-K/apis/maps/articles/toomanymarkers.html#gridbasedclustering

Я сделал блог о кластерной сетке с примером кода на C # http://kunuk.wordpress.com/2011/09/15/clustering-grid-cluster.

Интересный вопрос :) В книге по разработке алгоритмовДжон Кляйнберг: есть упоминание о том, что подсчет 1.000.000 предметов дает около 1 секунды для O (n) и 20 секунд для O (nlogn).

В некоторых приемах следует использовать только часть данных врасчет, если вы не можете сохранить его O (n).

Answer 2

Вы можете использовать пространственный индекс и уменьшить размерность. Затем вы можете тянуть маркеры отдельно на каждом уровне масштабирования. Я написал PHP-скрипт с множеством кривых заполнения пробелов и квадрик для академических целей. У меня также есть коммерческое решение.

Для начала вы можете прочитать:

• http://blog.notdot.net/2009/11/Damn-Cool-Algorithms-Spatial-indexing-with-Quadtrees-and-Hilbert-Curves
• http://msdn.microsoft.com/en-us/library/bb259689.aspx.

Когда вам нужен более точный поиск, вы все равно можете использовать его для исключения вычисления ближайшего соседа со всеми местоположениями.