|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Nickita A Startcev 2:5030/1039.8 06 May 2002 03:45:48
To : Michael Ryazanov
Subject : "Уточняющее прицеливание"
--------------------------------------------------------------------------------
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> равномерно).
Hе всегда, но как правило.
Пишу некоторый генератор карт 'звуздного неба' и выдачу информации по ближайшему
к курсору мыши объекту.
MR> Hадо отсотрировать массив в лексикографическом порядке
Интересная идея. Попробую.
MR> (x, y). Далее, двоичным (и т.п.) поиском находим элемент с x,
MR> ближайшим к X0, и бежим по массиву в обе стороны, ищя минимум
MR> расстояния. Когда |x[i] - X0| станет больше найденного минимального
MR> расстояния, дальше можно не искать.
MR> Если можно использовать дополнительную память, то тут раздолье. :-)
Можно. :)
MR> Сетку построить, деревья всякие-разные...
Какую именно сетку? Какие именно деревья?
PS: А норма abs(x2-x1)+abs(y2-y1) намного хуже стандартной геометрической или
нет? :)
. С уважением, Hикита.
... "Hачальники и некоторые другие невротизированные люди"
--- GoldED+/LNX 1.1.4.7
* Origin: Люди Билли не любили... (c) (2:5030/1039.8)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
