Поиск ближайшей точки? , подскажите формулу для нахождения ближайшей точки

Приветствую!

Если не сложно подскажите формулу для вычисления ближайшей точки.
Т.е. есть некоторое множество точек на плоскости, среди них нужно найти ближайшую к заданной точке.

Входные параметры,
N кол-во точек с координатами (x, y)
Заданная точка S (x, y).
Нужно найти ближайшую к S точку.

Мне б формулу этого дела.
А то искал в сети - ничего понятного не нашел, одни какие-то абстракции, теории...

Спасибо!

Имхо стоит упорядочить точки по параметру (x + y). Тогда искать нужно будет только в окрестностях данной точки.

Возможно сам критерий (x + y) ошибочен, но извлечение квадратного корня использовать нельзя. Есть еще алгоритмы быстрой оценки расстояния...

Сообщение отредактировано: Der_Meister - 08.01.09, 23:51

Цитата Der_Meister @ 08.01.09, 23:50

Имхо стоит упорядочить точки по параметру (x + y). Тогда искать нужно будет только в окрестностях данной точки.

Что в окрестности искать надо - это точно, но вот только проблема раз: в метрике l₁ ближайшая точка может не совпадать с ближайшей в метрике l₂ (т.е. придется всё равно перебирать всё элементы множества заданных точек), и проблема два: только само по себе упорядочивание займет больше времени, чем поиск в лоб.

Цитата Der_Meister @ 08.01.09, 23:50

но извлечение квадратного корня использовать нельзя

Кто сказал?

Цитата @POLL @ 08.01.09, 23:41

Мне б формулу этого дела.

Если тебя интересует именно формула, то её можно записать, например, так (в T_EX нотации):

T = \argmin_{x \in P }{\rho(x, S)} 

P - множество заданных точек, T - ответ, искомая точка, а ρ - метрика, естественно.

Цитата albom @ 09.01.09, 00:29

Кто сказал?

Я ретроград и привык, что операция извлечения квадратного корня крайне медленна.

А я и не утверждаю обратное, но тем не менее мне совершенно непонятно как скорость извлечения корня может быть связана вот с этим утвержением:

Цитата Der_Meister @ 08.01.09, 23:50

извлечение квадратного корня использовать нельзя

>операция извлечения квадратного корня крайне медленна
необязательно извлекать корень, при нахождении минимального евклидова расстояния достаточно сравнения суммы квадратов


@POLL
Операцию нужно выполнить один раз или много раз находить ближайшие к заданным точкам?

Цитата albom @ 09.01.09, 00:29

Цитата @POLL @ 08.01.09, 23:41

Мне б формулу этого дела.

Если тебя интересует именно формула, то её можно записать, например, так (в T_EX нотации):

T = \argmin_{x \in P }{\rho(x, S)} 

P - множество заданных точек, T - ответ, искомая точка, а ρ - метрика, естественно.

Ой, а можно эту формулу немного подробнее описать, как получить метрики каждой точки, что такое rho, argmin_
Я не особо был силен в высшей математике, а счас тем более мало что припомню.

-Added 09.01.09, 08:59

Цитата MBo @ 09.01.09, 06:08

@POLL
Операцию нужно выполнить один раз или много раз находить ближайшие к заданным точкам?

Один раз.

Вообще, я думал решить задачу как-то так.
Брать заданную точку (x, y) за центр/ось.
Вокруг этой оси "рисовать" окружность радиусом 1. И смотреть попадают в неё точки или нет.
Если попадает одна точка => это искомая ближайшая точка.
Если попадает несколько точек => считаем расстояние от каждой точки до оси, у точки которой меньшее расстояние - искомая.
Если в получившейся окружности точек нет, увеличиваем радиус окружности - 2, 3, 4 и т.д. И снова пробегаем по циклу.

Правда я не уверен, что такой цикл лучше/производительнее представленной выше формул с метриками.

Этот алгоритм мне нужен для моего веб-приложения прогноза погоды.
Там так. Пользователь заходит на сайт, при этом определяется его географическая привязка, координаты (широта/долгота т.е. x, y).
По этим координатам пользователю выдается прогноз погоды его города. При этом возможны 2 ситуации.
1) Для его координат есть прогноз
2) Для его координат прогноза нет.
Вот, во втором случае мне и нужно определить ближайшую точку. Есть точка пользователя (S) и есть точки с погодой (P). Среди P нужно найти ближайшую.

Вот, как-то так.

Посмотри здесь, в пятой главе то, что нужно.

Цитата Konigsberg @ 09.01.09, 09:38

@POLL, это жесть...
Вам нужно написать один простой цикл пробегающий по всем точкам в котором из координат вашей точки вычесть координаты каждой точки в цикле, возвести их в квадрат, сложить и найти меньшее значение это величины

(x0, y0) //ваша точка
min = MAX_VALUE; // заведомо очень большое значение
(xs, ys) //искомая точка
for each ((x, y) in points) {
    distance = (x0 - x)^2 + (y0 - y)^2;
    if (distance < min) {
        min = distance;
        xs = x;
        ys = y;
    }
}

Ой, спасибо ОООгромное - как все просто и главное работает

Конечно, для производительности было б неплохо использовать какие-нить расчетные индексы, но это мне нужно теорию почитать

Вот для теста можно поюзать. $sx, $sy - заданная точка, $px и $py - искомая.

Цитата

<?php
$sx = 80;
$sy = -40;
$min = 1000;

$px = 0;
$py = 0;

$points = array(
array(0, 0),
array(-100, 50),
array(90, 100),
array(50, 50),
array(70, -30),
array(10, 10)
);

foreach ($points as $point) {
$d1 = pow(($sx - $point[0]), 2);
$d2 = pow(($sy - $point[1]), 2);
$distance = $d1 + $d2;
if ($distance < $min) {
$min = $distance;
$px = $point[0];
$py = $point[1];
}
}

echo '<hr>' . $px . ' : ' . $py;
?>
?>

-Added 09.01.09, 11:47

Цитата OpenGL @ 09.01.09, 10:12

Посмотри здесь, в пятой главе то, что нужно.

Спасибо за ссылку!,
там интересные способы описаны,
правда там больше теоретическая часть и мало практических примеров.

Почитаю, мож чего пойму