|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Michael Ryazanov 2:5030/1006.64 07 May 2002 00:27:00
To : Nickita A Startcev
Subject : Re: "Уточняющее прицеливание"
--------------------------------------------------------------------------------
NAS>>> Есть одномерный массив элементов (x,y,data), где x,y - координаты
NAS>>> этого псевдоточечного объекта. Диапазон в котором лежат координаты
NAS>>> известен. Можно ли найти ближайший к X0,Y0 объект быстрее, чем за o(n)
NAS>>> ?
<...>
MR>> Сетку построить, деревья всякие-разные...
NAS> Какую именно сетку?
Hу, бьётся всё поле на некоторое количество ячеек (подбирается эмпирически) N
x M. К каждой ячейке привязываются объекты, в неё входящие. Потом, очевидно,
можно перебирать не все подряд объекты, а по ячейкам -- сначала ту, в которую
X0,Y0 попадает, потом, если надо, соседние и т.д.
NAS> Какие именно деревья?
Квадрантное, "двумерное дерево поиска"...
В литме вообще-то давали (покупали) "зелёную книжку" -- Майкл Ласло
"Вычислительная геометрия и компьютерная графика на C++" -- там это дело
описано.
NAS> PS: А норма abs(x2-x1)+abs(y2-y1) намного хуже стандартной
NAS> геометрической или нет? :)
Кому хуже? :-) Человеку непривычному, наверно, хуже. max(|x2-x1|,|y2-y1|) --
немного привычнее.
Только чем такой вопрос вызван? Hа современных процессорах умножение быстро
выполняется, а корень ведь для сравнения извлекать не надо.
|V|uxau/\
--- -- - ъ
* Origin: Ф И З Ф А К - Ч Е М П И О H ! (2:5030/1006.64)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
