Intereting Posts
Как привязать параметры к необработанному запросу БД в Laravel, который используется на модели? График диаграммы Google с датой по оси x Оптимальные методы работы с автозагрузкой Как проверить, если строка php содержит только английские буквы и цифры? Как обеспечить дополнительную безопасность для проверки источника запроса preg_replace non-alpha, оставить одиночные пробелы Как отправить динамическое значение массива в другой файл php с помощью jQuery запрос geoip zip code Разбор списка атрибутов / значений в PHP Запуск тестов PHPUnit в определенном порядке MD5 строки в ActionScript возвращает неверные результаты, когда какой-то hex является частью строки (т. Е. «Abc \ xBF \ x4E») Как очистить весь контент с веб-сайта? Как получить Open Graph Protocol веб-страницы по php? Данные PHP SESSION, потерянные между загрузками страниц с WAMPserver 2.0 на localhost Чего он хочет? – mysqli_num_rows () ожидает, что параметр 1 будет mysqli_result, boolean given

Алгоритм кластеризации карт

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

Заметки:

  • Код работает быстрее всего, когда оператор SQL упорядочен по имени маркера – который сам выполняет очень частичную работу по кластеризации маркеров (имена маркеров в одном месте часто, но не всегда аналогичны).
  • Я не могу предварительно кластеризовать маркеры, потому что их можно динамически искать и фильтровать.
  • Я пробовал grid-based кластеризацию, но результаты часто не очень приятны.
  • Я знаю, что кластеры слегка перекошены на проекции Меркатора.
  • Меня не интересует коммерческая служба кластеризации.

Код:

$singleMarkers = array(); $clusterMarkers = array(); while (count($markers)) { $marker = array_pop($markers); $cluster = array(); // Compare marker against all remaining markers. foreach ($markers as $key => $compareMarker) { // This function returns the distance between two markers, at a defined zoom level. $pixels = pixelDistance($marker['lat'], $marker['lng'], $compareMarker['lat'], $compareMarker['lng'], $zoomLevel); // If two markers are closer than defined distance, remove compareMarker from array and add to cluster. if ($pixels < $distance) { unset($markers[$key]); $cluster[] = $compareMarker; } } // If a marker was added to cluster, also add the marker we were comparing to. if (count($cluster) > 0) { $cluster[] = $marker; $clusterMarkers[] = $cluster; } else { $singleMarkers[] = $marker; } } function pixelDistance($lat1, $lon1, $lat2, $lon2, $zoom) { $x1 = $lon1*10000000; //This is what I did to compensate for using lat/lon values instead of pixels. $y1 = $lat1*10000000; $x2 = $lon2*10000000; $y2 = $lat2*10000000; return sqrt(pow(($x1-$x2),2) + pow(($y1-$y2),2)) >> (21 - $zoom); //21 is the max zoom level } 

ОБНОВИТЬ

Вот текущий код:

 $singleMarkers = array(); $clusterMarkers = array(); // Minimum distance between markers to be included in a cluster, at diff. zoom levels $DISTANCE = (10000000 >> $ZOOM) / 100000; // Loop until all markers have been compared. while (count($markers)) { $marker = array_pop($markers); $cluster = array(); // Compare against all markers which are left. foreach ($markers as $key => $target) { $pixels = abs($marker['lat']-$target['lat']) + abs($marker['lng']-$target['lng']); // If the two markers are closer than given distance remove target marker from array and add it to cluster. if ($pixels < $DISTANCE) { unset($markers[$key]); $cluster[] = $target; } } // If a marker has been added to cluster, add also the one we were comparing to. if (count($cluster) > 0) { $cluster[] = $marker; $clusterMarkers[] = $cluster; } else { $singleMarkers[] = $marker; } } не $singleMarkers = array(); $clusterMarkers = array(); // Minimum distance between markers to be included in a cluster, at diff. zoom levels $DISTANCE = (10000000 >> $ZOOM) / 100000; // Loop until all markers have been compared. while (count($markers)) { $marker = array_pop($markers); $cluster = array(); // Compare against all markers which are left. foreach ($markers as $key => $target) { $pixels = abs($marker['lat']-$target['lat']) + abs($marker['lng']-$target['lng']); // If the two markers are closer than given distance remove target marker from array and add it to cluster. if ($pixels < $DISTANCE) { unset($markers[$key]); $cluster[] = $target; } } // If a marker has been added to cluster, add also the one we were comparing to. if (count($cluster) > 0) { $cluster[] = $marker; $clusterMarkers[] = $cluster; } else { $singleMarkers[] = $marker; } } 

Вам действительно нужно рассчитать евклидову дистанцию ? Если вы просто сравниваете относительные величины расстояний, возможно, вам удастся использовать расстояние Манхэттена , что позволит вам сэкономить два вызова pow() и от одного до sqrt() :

 function pixelDistance($lat1, $lon1, $lat2, $lon2, $zoom) { $x1 = $lon1*10000000; //This is what I did to compensate for using lat/lon values instead of pixels. $y1 = $lat1*10000000; $x2 = $lon2*10000000; $y2 = $lat2*10000000; return ($x1-$x2) + ($y1-$y2) >> (21 - $zoom); } 

Не уверен, если вам понадобится бит >> (21 - $zoom) для ваших вычислений, поэтому я его оставил. Но если вам действительно не нужно использовать рассчитанные значения расстояния в другом месте, вам, вероятно, удастся просто использовать широту / долготу (не нужно умножать на что-либо) и принимая расстояние Манхэттена, предполагая, что вы предварительно рассчитаете $distance чтобы соответствовать этой мере, что будет намного дешевле в вычислительных терминах, чем принуждение всех расстояний, чтобы вписаться в единицы и величина $distance .

EDIT: Когда я изучал эту проблему в прошлом году, я нашел полезный материал в Википедии – да, это может случиться 😉

  • Кластерный анализ
  • Иерархическая кластеризация

Я также могу настоятельно рекомендовать книгу « Программирование коллективного интеллекта: создание приложений Smart Web 2.0», которое происходит в кластеризации с большой глубиной, применительно не только к географическим данным, но и к другим областям анализа данных.

Расширяясь от того, что сказал Джон, я думаю, вы должны попробовать включить эту функцию. Функциональные вызовы в PHP очень медленные, поэтому вы должны получить приличное ускорение от этого.

Итак, вот что я сделал – я добавил два дополнительных столбца в таблицу маркеров (точек) с преобразованными меркатором значениями для широты и долготы, используя следующие функции:

 public static $offset = 268435456; public static $radius = 85445659.44705395; /* $offset / pi(); */ function LonToX($lon) { return round(self::$offset + self::$radius * $lon * pi() / 180); } function LatToY($lat) { return round(self::$offset - self::$radius * log((1 + sin($lat * pi() / 180)) / (1 - sin($lat * pi() / 180))) / 2); } 

Таким образом, я мог бы получить точно размещенные кластеры. Я все еще пытаюсь решить, как избежать использования array_pop и циклического перехода каждый раз. Пока что он довольно эффективен с маркерами под 1000. Я буду публиковать результаты для + 5K и + 10K маркеров позже.

Избегая функции pixelDistance и имея ее встроенный, производительность увеличивается почти вдвое!

Похоже, что ускорение функции pixelDistance () может быть частью вашего решения, поскольку оно выполняется внутри цикла. Это хорошее место для первого взгляда, но вы не включили этот код, поэтому я не могу быть уверен.

Я вижу два возможных улучшения:

  • Можете ли вы просто пройти через маркеры $ с циклом for вместо того, чтобы выталкивать их из массива? Всплывающее вскрытие массива полностью не требуется – вы должны использовать только массивы в виде очередей, если вы одновременно добавляете и удаляете элементы (что вы не делаете, вы просто обрабатываете их, а затем отбрасываете)

  • Вы должны попытаться вычислить count () массивов в начале, а затем вручную увеличить или уменьшить переменную count. Пересчитывая размер массива, каждый цикл является расточительным.

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

  • Уменьшите размерность данных : у вас есть 2d данных long / lat, возможно, вы можете попробовать проецировать ее на 1D, используя что-то вроде многомерного масштабирования (MDS), которое пытается уменьшить количество измерений при сохранении расстояний в исходном пространстве, таким образом, функция расстояния будет иметь дело только с одной функцией вместо двух. Альтернативный способ заключается в использовании анализа основных компонентов (PCA)
  • Более быстрый поиск : шаг вычисления расстояния до каждого маркера может быть улучшен с использованием KD-деревьев .

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

Простая оптимизация заключалась бы в том, чтобы воспользоваться тем, что sqrt (x) <sqrt (y) является true iff x <y, поэтому вы можете опустить sqrt в пикселеDistance и вычислить квадрат $ distance вне цикла. Вы также можете вычислить 21 – $ zoomLevel вне цикла, вам придется умножить его на 2, если вы сравниваете квадрат значений. Еще одна небольшая оптимизация заключалась бы в том, чтобы сохранить 2 умножения, выполнив $ x1- $ x2 до масштабирования на 10000000. И еще немного, хранение дельта в var и его умножение, вероятно, быстрее, чем функция pow. И еще для того, чтобы вы могли встроить функцию сравнения пикселей. Такая оптимизация даст только постоянный коэффициент ускорения.

Для более быстрого ускорения вам понадобится какая-то система ускорения. Легко было бы поместить маркеры на квадраты расстояния. Затем вы можете запускать над бункерами поиск маркеров для кластера с одним и тем же бункером и тремя другими, выбранными в зависимости от того, какая сторона центра бункера помечена маркером. Это приведет к линейной кластеризации времени, которая будет бить любую оптимизацию квадратичного алгоритма для больших результирующих наборов.

Если можно, сортируйте маркеры по долготе при первоначальном поиске; то, как только маркер будет больше ширины маркера от следующего маркера в отсортированном списке, вы определенно знаете, что оставшиеся маркеры не будут перекрываться, поэтому вы можете разбить цикл foreach и сэкономить массу времени обработки. Я реализовал это на своем собственном сайте и работает очень эффективно.

Здесь у меня есть исходный код на Python.