Search code examples
phparraysalgorithmmathvoronoi

PHP - Optimize finding closest point in an Array

I have created a script which gets a big array of points and then finds the closest point in 3D-space based on a limited array of chosen points. It works great. However, sometimes I get like over 2 Million points to compare to an array of 256 items so it is over 530 million calculations! Which takes a considerable amount of time and power (taking that it will be comparing stuff like that few times a min).

I have a limited group of 3D coordinates like this:

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

Then I have another very large group of, let's say, random 3D coordinates which can vary in size from 2,500 -> ~ 2,000,000+ items. Basically, what I need to do is to iterate through each of those points and find the closest point. To do that I use Euclidean distance:

sq((q1-p1)2+(q2-p2)2+(q3-p3)2)

This gives me the distance and I compare it to the current closest distance, if it is closer, replace the closest, else continue with next set.

I have been looking on how to change it so I don't have to do so many calculations. I have been looking at Voronoi Diagrams then maybe place the points in that diagram, then see which section it belongs to. However, I have no idea how I can implement such a thing in PHP.

Any idea how I can optimize it?

Solution

  • Just a quick shot from the hip ;-)

    You should be able to gain a nice speed up if you dont compare each point to each other point. Many points can be skipped because they are already to far away if you just look at one of the x/y/z coordinates.

    <?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));
}

    A working code example can be found at http://sandbox.onlinephpfunctions.com/code/8cfda8e7cb4d69bf66afa83b2c6168956e63b51e