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

StackOverflow https://stackoverflow.com/questions/1434222

Вопрос

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

Примечания:

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

Код:

$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;
    }
}
Это было полезно?

Решение

Вам действительно нужно рассчитать Евклидово расстояние?Если вы просто сравниваете относительные величины расстояний, вам, вероятно, сойдет с рук использование Расстояние до Манхэттена, что сэкономит вам два звонка в 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.

Редактировать:Когда я исследовал эту проблему в прошлом году, я нашел кое-что полезное в Википедии - да, это может случиться ;-)

Я также могу настоятельно рекомендовать эту книгу Программирование Коллективного Разума:Создание интеллектуальных приложений Web 2.0 который углубляется в кластеризацию применительно не только к географическим данным, но и к другим областям анализа данных.

Другие советы

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

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

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() могло бы быть частью вашего решения, поскольку она выполняется внутри цикла.Это хорошее место, чтобы посмотреть в первую очередь, но вы не включили этот код, поэтому я не могу быть уверен.

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

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

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

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

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

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

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

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

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

У меня есть некоторый исходный код на Python здесь.

Лицензировано под: CC-BY-SA с атрибуция
Не связан с StackOverflow
scroll top