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

Question

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

Примечания:

• Код выполняется быстрее всего, когда оператор 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
}

---

UPDATE

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

$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;
    }
}

Answer 1

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

РЕДАКТИРОВАТЬ: Когда я исследовал эту проблему в прошлом году, я нашел некоторые полезные вещи в Википедии - да, это может случиться; -)

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

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

Answer 2

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

Answer 3

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

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 и ее встроенное повышение производительности почти вдвое!

Answer 4

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

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

Answer 5

Простая оптимизация состояла бы в том, чтобы воспользоваться преимуществом, что sqrt (x)

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

Answer 6

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

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

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

Answer 7

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

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

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

Answer 8

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