Re: "Уточняющее прицеливание"

From

Michael Ryazanov (2:5030/1006.64)

To

Nickita A Startcev

Date

2002-05-07T00:27Z

Area

RU.ALGORITHMS

▐┤E╚°' Nickita!

 NAS>>> Есть одномерный массив элементов (x,y,data), где x,y - координаты
 NAS>>> этого псевдоточечного объекта. Диапазон в котором лежат координаты
 NAS>>> известен. Можно ли найти ближайший к X0,Y0 объект быстрее, чем за o(n)
 NAS>>> ?
<...>
 MR>> Сетку построить, деревья всякие-разные...
 NAS> Какую именно сетку?

   Ну, бьётся всё поле на некоторое количество ячеек (подбирается эмпирически) N x M. К каждой ячейке привязываются объекты, в неё входящие. Потом, очевидно, можно перебирать не все подряд объекты, а по ячейкам -- сначала ту, в которую X0,Y0 попадает, потом, если надо, соседние и т.д.

 NAS> Какие именно деревья?

   Квадрантное, "двумерное дерево поиска"...
   В литме вообще-то давали (покупали) "зелёную книжку" -- Майкл Ласло "Вычислительная геометрия и компьютерная графика на C++" -- там это дело описано.

 NAS> PS: А норма abs(x2-x1)+abs(y2-y1) намного хуже стандартной
 NAS> геометрической или нет? :)

   Кому хуже? :-) Человеку непривычному, наверно, хуже. max(|x2-x1|,|y2-y1|) -- немного привычнее.
   Только чем такой вопрос вызван? На современных процессорах умножение быстро выполняется, а корень ведь для сравнения извлекать не надо.

                                                                      |V|uxau/\
--- -- - ·
 * Origin:             Ф И З Ф А К - Ч Е М П И О H !           (2:5030/1006.64)