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

From

Alex Astafiev (2:5000/228.16)

To

Nickita A Startcev

Date

2002-05-07T05:00Z

Area

RU.ALGORITHMS

Здравствуй Nickita, ничего, если я тут на диванчик прилягу?

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

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

Если диапазон координат известен, то
 Quadtree. Далее, выбор каждого листа дерева - хэш-функция от положения
мыши внутри квадрата. и так - до конкретной точки.

В простейшем случае, один прямой хэш из одной lookup-table:

void int get_point_index()
{
 return point_indexes[mouse.y][mouse.x];
}

только lookup табличка point_indexes[][] будет великовата. В аккурат по
величине экрана, X*Y.

это o(n) или быстрее?  >8-E)

---
 * Origin: Alex Raider/ Flash inc. 1992-2002 (2:5000/228.16)