|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Alex Astafiev 2:5000/228.16 07 May 2002 05:00:00
To : Nickita A Startcev
Subject : "Уточняющее прицеливание"
--------------------------------------------------------------------------------
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)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
