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

From

Nickita A Startcev (2:5030/1039.8)

To

Michael Ryazanov

Date

2002-05-06T03:45:48Z

Area

RU.ALGORITHMS

Привет, Michael !


 05 May 02 , 15:09  Michael Ryazanov писал к Nickita A Startcev:

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

 MR>    Память дополнительную можно использовать?

Да. Задача практическая, точек от 10  до 100 0000.

 NAS>> Есть ли решение более быстрое чем нижеприведенное?
 NAS>> 1) берем расстояние до первого объекта, запоминаем вместе с
 NAS>> номером объекта. 2) перебираем подряд оставшиеся объекты, если
 NAS>> попался более близкий - 'перезапоминаем' расстояние и номер.

 MR>    Если без дополнительной памяти, можно предложить некую оптимизацию
 MR> (если объектов достаточно много и расположены они более-менее
 MR> равномерно).

Не всегда, но как правило.
Пишу некоторый генератор карт 'звуздного неба' и выдачу информации по ближайшему к курсору мыши объекту.

 MR> Надо отсотрировать массив в лексикографическом порядке

Интересная идея. Попробую.

 MR> (x, y). Далее, двоичным (и т.п.) поиском находим элемент с x,
 MR> ближайшим к X0, и бежим по массиву в обе стороны, ищя минимум
 MR> расстояния. Когда |x[i] - X0| станет больше найденного минимального
 MR> расстояния, дальше можно не искать.
 MR>    Если можно использовать дополнительную память, то тут раздолье. :-)

Можно. :)

 MR> Сетку построить, деревья всякие-разные...

Какую именно сетку? Какие именно деревья?

PS: А норма abs(x2-x1)+abs(y2-y1) намного хуже стандартной геометрической или нет? :)
.                                                С уважением, Никита.
... "Начальники и некоторые другие невротизированные люди"
--- GoldED+/LNX 1.1.4.7
 * Origin: Люди Билли не любили... (c) (2:5030/1039.8)