我创建了一个脚本，该脚本获取大量点，然后根据有限的选定点数组在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）2+（q 3-p3）2）
这给了我距离，我将其与当前最近的距离进行比较，如果它更近，则替换最近的距离，否则继续下一组。
我一直在寻找如何更改它，这样我就不必做那么多计算。我一直在看Voronoi图，然后也许将点放在该图中，然后看看它属于哪个部分。但是，我不知道如何在PHP中实现这样的事情。
知道我如何优化它吗？
只是从臀部快速射击;-）
如果您不将每个点与其他点进行比较，您应该能够获得不错的速度。许多点可以跳过，因为如果您只看其中一个 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 中找到工作代码示例