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₁-p₁)²+(q₂-p₂)²+(q₃-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 找到工作代码示例