|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Dmitriy Goldobin 2:5020/400 21 Jul 2003 19:46:22
To : Anatoly Saveliev
Subject : Поиск ближайшей точки (сабж слетел)
--------------------------------------------------------------------------------
Hi!
> ну зачем так строго - товарищ просто хотел упорядочить точки по их
> проекции на ось X, что вполне разумно и работает, если число точек имеет
> порядок 100 000.
... и они распределены равномерно по плоскости. Hо в этом случае гораздо
эффективнее регулярная сетка.
> Точно так же сортируются (по левому краю) и проекции
> всех отрезков на ось X. Это позволяет при поиске сразу "отсечь" точки и
> линии, не попадающие в проекцию, после чего использовать
> последовательный поиск - среднее число кандидатов при котором десятки.
> Работает все это много лет (больше десяти), и не намного медленнее, чем
> всякие квадродеревья и прочие премудрости.
а вот в более сложных случаях, чем описано выше, это может привести к
затратам большим, чем даже простой перебор. Как мы будем искать при такой
сортировке? Ищем бинарным поиском ближайшую по X точку к искомой, вычисляем
расстояние до нее, ограничиваем дальнейший поиск по X с двух сторон этим
расстоянием. Берем следующую ближайшую по X, если расстояние до нее меньше,
то еще ограничиваем поиск. А теперь представь - точки расположены по
окружности, а искомая неподалеку от центра. Hикакого ограничения по X мы не
добьемся и получим полный перебор ПЛЮС бинарный поиск по X в начале.
Bye.
--- ifmail v.2.15dev5
* Origin: Demos online service (2:5020/400)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
