пересечение прямоугольников на тороидальной поверхности

From

Anton Kozyr ()

To

All

Date

2002-07-28T03:34:36Z

Area

RU.ALGORITHMS

From: Anton Kozyr <slayer@kot.poltava.ua>

Привет Олл!

Я надеюсь, что здесь можно сабжевые вопросы задавать ;)

Есть квадратная поверхность с замкнутыми краями, говорят, что
называется тороидальной, хотя тор себе такой я слабо представляю.

Участок этой поверхности отображается на экран. На той же поверхности
куча различных объектов, которые характеризуются описывающими их
прямоугольниками (bounding rect - яснее будет).

Всё это мне нужно - быстро отображать. Я могу заранее проиндексировать
что нужно, построить какие-нибудь деревья, чтоб потом быстро искать и
рисовать только те объекты, которые пересекаются с инвалидным
прямоугольником(тем который требуется обновить).

В принципе мозгов для реализации много не нужно. Проблема в скорости,
так как количество объектов на поверхности реально может достигать
десятков тысяч, если не сотен. А мне нужно прорисовать только
некоторые(к примеру при скроллинге).

Кто что подскажет?
Плоские(не тороидальные) решения тоже приветствуются.

Антон
--- ifmail v.2.15dev5
 * Origin: Solver Ltd. site #2 (2:5020/400)