|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Andrey Sapozhnikov 2:5020/400 30 Jan 2002 20:46:34
To : Nickita A Startcev
Subject : Re: Поиск ближайшей точки с координатами(x,y).
--------------------------------------------------------------------------------
Nickita A Startcev wrote:
> Привет, Trusov !
>
>
> 21 Jan 02 , 18:38 Trusov Alexey писал к All:
>
> TA> Имеется массив координат точек.
> TA> Трубуется найти ближайшую точку из этого массива (номер элемента) к
> TA> зананной точке (например с координатами x0,y0).
>
> TA> Как это сделать наиболее быстрым способом?
> TA> Интересуют идеи, алгоритмы...
>
> O(N) R=(x_0-x_i)^2+(y_0-y_i)^2;
> Считаем R для первой точки; помним номер точки;
> Перебираем все остальные точки: если R меньше - запоминаем новый R и новый
> номер точки;
Имея массив точек упорядоченый по одной из координат (для примера пусть будет по
x)
, можно оптимизировать поиск. Пусть A[1..N] массив координат всех точек
включая заданную A[i], где 1 <= i <= N. Производим перебор точек в массиве от i
в обе стороны вычисляя расстояние до точек A[i + delta] и A[i - delta] и
запоминая ближайшую из найденых точку и расстояние до нее. Как только
A[i + delta].x - A[i].x становится >= найденого минимального расстояния -
прекращаем поиск в эту сторону. Соответственно как только A[i].x - A[i -
delta].x
становится >= найденого минимального расстояния - прекращаем поиск в другую
сторону. В зависимости от распределения точек на плоскости, это может
дать выигрыш вплоть до нахождения точки на первой же итеррации.
Имея два массива точек A и B упорядоченные по x и y соответственно, можно
двигаться от точки ai (в массиве A) в обе стороны и точки bi (та же исходная
точка в массиве B) в обе стороны по тому же алгоритму. Поиск прекращается
если прекращается поиск в любом из массивов.
Андрей
--- ifmail v.2.15dev5
* Origin: Demos online service (2:5020/400)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
| Тема: |
Автор: |
Дата: |
|
Поиск ближайшей точки с координатами (x,y). |
Trusov Alexey |
21 Jan 2002 19:38:36 |
 Re: Поиск ближайшей точки с координатами (x,y). |
Dennis |
21 Jan 2002 20:09:23 |
 Re: Поиск ближайшей точки с координатами (x,y). |
Yurij Zabelyshynskij |
21 Jan 2002 20:23:43 |
  Re[2]: Поиск ближайшей точки с координатами (x,y). |
Dennis |
21 Jan 2002 21:19:15 |
 Re[3]: Поиск ближайшей точки с координатами (x,y). |
Dennis |
22 Jan 2002 11:59:02 |
|
Re[2]: Поиск ближайшей точки с координатами (x,y). |
Ilia Kantor |
22 Jan 2002 20:56:12 |
|
Re: Re[2]: Поиск ближайшей точки с координатами (x,y). |
Nick Kovaliov |
23 Jan 2002 10:33:22 |
|
Поиск ближайшей точки с координатами (x,y). |
Stanislav Shwartsman |
21 Jan 2002 21:54:53 |
|
Re: Поиск ближайшей точки с координатами (x,y). |
Antony Victoroff |
22 Jan 2002 14:34:29 |
|
Поиск ближайшей точки с координатами (x,y). |
Stanislav Shwartsman |
22 Jan 2002 20:16:25 |
|
Re: Поиск ближайшей точки с координатами (x,y). |
Antony Victoroff |
23 Jan 2002 18:20:49 |
|
Re: Поиск ближайшей точки с координатами (x,y). |
Trusov Alexey |
25 Jan 2002 18:48:37 |
|
Re: Поиск ближайшей точки с координатами (x,y). |
Antony Victoroff |
28 Jan 2002 00:41:00 |
|
Re: Поиск ближайшей точки с координатами (x,y). |
Antony Victoroff |
22 Jan 2002 11:53:35 |
|
Поиск ближайшей точки с координатами (x,y). |
Sergei Shelukhin |
21 Jan 2002 21:45:02 |
|
Поиск ближайшей точки с координатами (x,y). |
Stanislav Shwartsman |
21 Jan 2002 22:57:18 |
|
Re: Поиск ближайшей точки с координатами (x,y). |
Dennis |
22 Jan 2002 10:50:59 |
|
Поиск ближайшей точки с координатами (x,y). |
Stanislav Shwartsman |
22 Jan 2002 19:23:04 |
|
Поиск ближайшей точки с координатами (x,y). |
Ilia Kantor |
23 Jan 2002 20:27:18 |
|
Re: Поиск ближайшей точки с координатами (x,y). |
Antony Victoroff |
22 Jan 2002 15:06:14 |
|
Поиск ближайшей точки с координатами (x,y). |
Nickita A Startcev |
30 Jan 2002 01:34:28 |
|
Re: Поиск ближайшей точки с координатами(x,y). |
Andrey Sapozhnikov |
30 Jan 2002 20:46:34 |
|
|
