맵 클러스터링 알고리즘

https://stackoverflow.com/questions/1434222

07-07-2019
|

문제

내 현재 코드는 매우 빠르지 만 더 많은 마커를 수용 할 수 있도록 더 빠르게 만들어야합니다. 제안이 있습니까?

메모:

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.

편집 : 작년 에이 문제를 연구 할 때 Wikipedia에서 유용한 것들을 발견했습니다 - 예, 일어날 수 있습니다 ;-)

나는 또한이 책을 강력히 추천 할 수 있습니다 집단 인텔리전스 프로그래밍 : 스마트 웹 2.0 응용 프로그램 구축 지리적 데이터뿐만 아니라 다른 데이터 분석 영역에도 적용되는 것처럼 깊이로 클러스터링에 들어갑니다.

다른 팁

요한이 말한 것을 확장하면서, 나는 당신이 그 기능을 인라인으로 시도해야한다고 생각합니다. PHP의 기능 호출은 매우 느리기 때문에 그로부터 괜찮은 속도를 얻을 수 있습니다.

그래서 여기에 내가 한 일은 다음과 같습니다. Mercator가 다음 함수를 사용하여 위도 및 경도에 대한 Mercator 변환 값을 사용하여 Markers (Point) 테이블에 두 개의 추가 열을 추가했습니다.

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 변수를 수동으로 증가 또는 감소시켜야합니다. 배열의 크기를 재 계산하는 것은 각 루프가 낭비됩니다.

다음은 성능이 큰 문제가있는 경우에 구현할 수있는 몇 가지 아이디어입니다.

데이터의 차원을 줄입니다: Long/LAT의 2D 데이터가 있습니다. 아마도 같은 것을 사용하여 1D로 투사 할 수 있습니다.다차원 스케일링 (MDS) 원래 공간의 거리를 보존하면서 치수 수를 줄이려고 시도하므로 거리 함수는 두 가지 대신 하나의 기능 만 처리하면됩니다. 대안적인 방법은 사용하는 것입니다 주요 구성 요소 분석 (PCA)
더 빠른 검색: 각 마커까지의 거리를 계산하는 단계는 KD-Trees.

이 두 기술 모두 오프라인 설정에 적용되므로 일반적으로 한 번 계산 한 다음 여러 번 사용됩니다.

간단한 최적화는 sqrt (x) <sqrt (y)가 true iff x <y라는 것을 활용하는 것입니다. 따라서 pixeldistance에서 sqrt를 생략하고 루프 외부에서 제곱 거리를 계산할 수 있습니다. 루프 외부의 21- $ 줌 레벨을 계산할 수도 있습니다. 제곱 값을 비교하면 2를 곱해야합니다. 또 다른 작은 최적화는 10000000으로 스케일링하기 전에 $ x1- $ x2를 수행하여 2 개의 곱셈을 절약하는 것입니다. 그리고 약간 더 많은 경우 델타를 VAR에 저장하고 그 자체로 곱하는 것이 POW 기능보다 빠릅니다. 그리고 더 많은 것을 위해 당신은 pixeldistance 함수를 인화 할 수 있습니다. 이러한 종류의 최적화는 일정한 요인 속도를 산출합니다.

더 빠른 속도를 높이려면 일종의 가속 데이터 스트럭처가 필요합니다. 쉬운 사람은 마커를 원거리 크기의 사각형에 넣는 것입니다. 그런 다음 쓰레기통을 가로 질러 마커의 중심이 어느쪽에 떨어지는 지에 따라 동일한 빈과 3 명의 다른 사람이 선택한 3 명으로 마커를 클러스터 할 수 있습니다. 이로 인해 선형 시간 클러스터링이 발생하여 더 큰 결과 세트를 위해 2 차 알고리즘에 대한 최적화를 이길 수 있습니다.

가능하다면 초기 검색에서 마커를 경도로 정렬하십시오. 그런 다음 마커가 정렬 된 목록의 다음 마커에서 마커 너비 이상이 되 자마자 나머지 마커가 겹치지 않으므로 Foreach 루프를 깨고 수많은 처리 시간을 절약 할 수 있습니다. 나는 이것을 내 자신의 사이트에서 구현했으며 매우 효율적으로 작동합니다.

파이썬에 소스 코드가 있습니다 여기.

라이센스 : CC-BY-SA ~와 함께 속성

제휴하지 않습니다 StackOverflow