|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Dmitriy Goldobin 2:5020/400 22 Jul 2003 14:12:25
To : Anatoly Saveliev
Subject : Re: Поиск ближайшей точки (сабж слетел),
--------------------------------------------------------------------------------
Hi!
> Кстати, а если себе тот же вопрос задать? - это по поводу (y/K), который
> и есть epsilon - в смысле, что делать, если клетка пустая - "улиткой"
> крутиться?; поэтому обычно все же используют масштабную иерархию
> (несколько уровней с разными K, не обязательно в два раза
> отличающимися), начиная с грубого разбиения, пока не попадется не более
> заданного числа точек - либо все же квадродерево и сливать пустые с
> соседями.
ты немного не так понял - в ячейке регулярной сетки хранятся не ссылки на
точки, входящие в эту ячейку, а ссылки на точки, до которых из этой ячейки
могут быть ближайшее расстояния. Cсылка на одну и ту же точку может быть из
разных ячеек. То есть как бы на диаграмму воронова наложили сетку и вписали
в ее ячейки на какие ячейки диаграммы каждая из них накладывается.
Hо это именно для равномерного распределения. В том же примере с точками по
окружности регулярная сетка выливается в полный перебор, поскольку ячейка
включающая центр окружности содержит ссылки на все точки.
как осуществлять поиск ближайшей за logN по диаграмме воронова или по
kd-tree я честно говоря так и не понял. надо попробовать реализовать, тогда
пойму :)
Bye.
--- ifmail v.2.15dev5
* Origin: Demos online service (2:5020/400)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
