ru.algorithms

 
 - RU.ALGORITHMS ----------------------------------------------------------------
 From : Antony Victoroff                     2:5030/953.300 22 Jan 2002  14:34:29
 To : Stanislav Shwartsman
 Subject : Re: Поиск ближайшей точки с координатами (x,y).
 -------------------------------------------------------------------------------- 
 

 
  Ответ на письмо Stanislav Shwartsman к Dennis (Понедельник Январь 21 2002
 20:54)
  TA>>> Имеется массив координат точек.
  TA>>> Трубуется найти ближайшую точку из этого массива (номер
  TA>>> элемента)
  TA>>> к зананной точке (например с координатами x0,y0).
  TA>>> Как это сделать наиболее быстрым способом?
 
  D>> Построить  триангуляцию  Делоне  (O(N*logN)), получить по ней
  D>> полигоны
  D>> Вороного  (O(N)?)  /*а можно и не получать?*/, найти полигон,
  D>> которому
  D>> будет принадлежать заданная точка (O(N)). Итого: O(N*logN) ---
  D>> быстрее
  D>> не получится.
 
  SS>  А просто измерить расстояние между заданной точкой и всеми точками
  SS> массива O(N) уже не прокатит ?
 
 это неинтересный подход. ненаучный :) и долгий. а если надо постоянно искать
 ближайших соседей ? :))
 тады можно использовать память O(N), затратив время O(NlogN) на предобработку и 
 потом искать ближайшего соседа за время всего-то O(logN). во как. опять же
 используя триангуляцию и диаграмму вороного. Ж:)
 
                                                 С уважением, Антон.
                                                              /3000.
 
 ... [home:latonita@mail.ru] [work:latonita@star.spb.ru] [ICQ#13382973]
 ---
  * Origin: 2:5030/3000 (2:5030/953.300)
 
 

Вернуться к списку тем, сортированных по: возрастание даты  уменьшение даты  тема  автор 

Тема:    Автор:    Дата:    Поиск ближайшей точки с координатами (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