Оптимизировать поиск ближайшей точки в массиве

Question

Оптимизировать поиск ближайшей точки в массиве

Я создал скрипт, который получает большой массив точек, а затем находит ближайшую точку в 3D-пространстве на основе ограниченного массива выбранных точек. Работает отлично. Тем не менее, иногда я получаю более 2 миллионов очков, чтобы сравнить с массивом из 256 элементов, так что все кончено 530 миллионов расчетов! Что требует значительного количества времени и сил (если сравнивать такие вещи несколько раз в минуту).

У меня есть ограниченная группа 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

Затем у меня есть еще одна очень большая группа, скажем, случайных трехмерных координат, размер которых может варьироваться от 2 500 до 2 000 000 элементов. По сути, мне нужно перебрать каждую из этих точек и найти ближайшую точку. Для этого я использую евклидово расстояние:

кв ((д₁-п₁)²+(д₂-п₂)²+(д₃-п₃)²)

Это дает мне расстояние, и я сравниваю его с текущим самым близким расстоянием, если оно ближе, заменим самое близкое, иначе продолжу со следующим набором.

Я искал, как это изменить, чтобы мне не пришлось делать так много вычислений. Я смотрел на диаграммы Вороного, затем, возможно, разместил точки на этой диаграмме, а затем посмотрел, к какому разделу она принадлежит. Тем не менее, я понятия не имею, как я могу реализовать такую вещь в PHP.

Есть идеи, как мне это оптимизировать?

1

algorithm arrays math php voronoi

Решение

Другие решения

Других решений пока нет …

Источник

Accepted Answer

Просто быстрый выстрел из бедра 😉

У вас должна получиться хорошая скорость, если вы не сравниваете каждую точку с другой. Многие точки могут быть пропущены, потому что они уже слишком далеко, если вы просто посмотрите на одну из координат 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

1