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

From

Alex Astafiev (2:5000/228.16)

To

Nickita A Startcev

Date

2002-05-08T20:46:17Z

Area

RU.ALGORITHMS

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

 >>> Пишу некоторый генератор карт 'звуздного неба' и выдачу информации
 >>> по ближайшему к курсору мыши объекту.
 NAS>
 VD>> Во-первых, в такой постановке понятие ближайшести необязательно
 VD>> брать в смысле метрики Евклида: достаточно разбить карту на
 VD>> прямоугольные "созвездия" по одному объекту в каждом,


Есть доказательство, что, например, метрики sqrt(x^2 + y^2) и x^2 + y^2
эквивалентны (работают) хоть и являются разными.

 NAS>
 NAS> Объект - звезда, а не созвездие. А идея побить карту на прямоугольники
 NAS> и рассматривать только 1..4 ближайших - интересна.


А если каждый прямоугольник разбить еще на прямоугольники, то это будет
называться QuadTree. Они бывают с равномерным разбиением и нет.

Я, может, слишком заумно высказался в прошлом письме, но идея проста -
для каждого пиксела экрана хранится ближайшая к нему звезда.
Куда бы ты не тыкнул, тут же получишь ответ - что ближайшее к данному пикселу.
Просто индекс звезды.

Quadtree это вариация на данную тему, позволяющая сэкономить память.


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