PHP - 优化在数组中查找最近点

Question

我创建了一个脚本，该脚本获取大量点，然后根据有限的选定点数组在3D空间中找到最近的点。效果很好。但是，有时我会得到超过 200 万点与 256 个项目的数组进行比较，因此计算超过 5.3 亿次！这需要大量的时间和精力（考虑到它将每分钟比较几次这样的东西）。

我有一组有限的 3D 坐标，如下所示：

array (size=XXX) 
0 => 10, 20, 30
1 => 200, 20, 13
2 => 36, 215, 150
3 => ...
4 => ...
... // this is limited to max 256 items

然后我还有另一个非常大的组，比方说，随机3D坐标，其大小可以从2,500 ->~2,000,000 +项目不等。基本上，我需要做的是遍历这些点中的每一个并找到最近的点。为此，我使用欧几里得距离：

sq（（q 1-p 1）2+（q 2-p 2）

²+（q 3-p₃）₂）

这给了我距离，我将其与当前最近的距离进行比较，如果它更近，则替换最近的距离，否则继续下一组。

我一直在寻找如何更改它，这样我就不必做那么多计算。我一直在看Voronoi图，然后也许将点放在该图中，然后看看它属于哪个部分。但是，我不知道如何在PHP中实现这样的事情。

知道我如何优化它吗？

Answer 1

只是从臀部快速射击;-）

如果您不将每个点与其他点进行比较，您应该能够获得不错的速度。许多点可以跳过，因为如果您只看其中一个 x/y/z 坐标，它们已经很远了。

<?php
$coord = array(18,200,15);
$points = array(
    array(10,20,30),
    array(200,20,13),
    array(36,215,150)   
);

$closestPoint = $closestDistance= false;;
foreach($points as $point) {
    list($x,$y,$z) = $point;
    // Not compared yet, use first poit as closest
    if($closestDistance === false) {
        $closestPoint = $point;
        $closestDistance = distance($x,$y,$z,$coord[0],$coord[1],$coord[2]);
        continue;
    }
    // If distance in any direction (x/y/z) is bigger than closest distance so far: skip point
    if(abs($coord[0] - $x) > $closestDistance) continue;
    if(abs($coord[1] - $y) > $closestDistance) continue;
    if(abs($coord[2] - $z) > $closestDistance) continue;
    $newDistance = distance($x,$y,$z,$coord[0],$coord[1],$coord[2]);
    if($newDistance < $closestDistance) {
        $closestPoint = $point;
        $closestDistance = distance($x,$y,$z,$coord[0],$coord[1],$coord[2]);
    }       
}
var_dump($closestPoint);
function distance($x1,$y1,$z1,$x2,$y2,$z2) {
    return sqrt(pow($x1-$x2,2) + pow($y1 - $y2,2) + pow($z1 - $z2,2));
}

可以在 http://sandbox.onlinephpfunctions.com/code/8cfda8e7cb4d69bf66afa83b2c6168956e63b51e 中找到工作代码示例