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

From

Sergey Andrianov (2:5020/1507.400)

To

Anton Kozyr

Date

2002-07-31T23:29:38Z

Area

RU.ALGORITHMS

Здравствуй, Anton!

Однажды 28-Jul-02  в 03:34   Anton Kozyr (0:0/4)
написал       All    по поводу
-=-   пересечение прямоугольников на тороидальной поверхности  -=-


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

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

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

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

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

   Вообще-то сотни тысяч при гигагерцовых процессорах - не так уж и много.
   Можно выиграть в скорости за счет памяти: например, разбиваешь свою плоскость (тор) сеткой на ячейки (например, размером со свое окно), заводишь массив соответствующей размерности и в ячейки массива записываешь ссылки на списки объектов, которые хотя бы частично содержатся в ячейке. Очевидно, при анализе надо быдет просмотреть только 4 ячейки, на которые попадает окно. Т.е. в переборе будут участвовать только в 4-5 раз больше объектов, чем будет видно в окне.

                  До свидания,  в  23:24 MSK
                                 Sergey

---
 * Origin: Sergiev Posad (2:5020/1507.400)