我当前的代码非常快，但我需要让它更快，以便我们可以容纳更多标记。有什么建议吗？

注意事项:

• 当 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;
    }
}

最佳答案

你真的需要计算Euclidean distance ?如果您只是比较距离的相对大小，则可以使用 Manhattan distance ，这将为您节省两次对 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 上发现了一些有用的东西 - 是的，它可能会发生 ;-)

• Cluster analysis
• Hierarchical clustering

我也强烈推荐这本书 Programming Collective Intelligence: Building Smart Web 2.0 Applications 深入聚类，不仅适用于地理数据，还适用于其他数据分析领域。

关于php - map 聚类算法，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/1434222/