|
|
ru.algorithms- RU.ALGORITHMS ---------------------------------------------------------------- From : Sergey Andrianov 2:5020/1507.400 31 Jul 2002 23:29:38 To : Anton Kozyr Subject : Re: пересечение прямоугольников на тороидальной поверхности -------------------------------------------------------------------------------- Однажды 28-Jul-02 в 03:34 Anton Kozyr (0:0/4) написал All по поводу -=- пересечение прямоугольников на тороидальной поверхности -=- AK> Есть квадратная поверхность с замкнутыми краями, говорят, что AK> называется тороидальной, хотя тор себе такой я слабо представляю. AK> Участок этой поверхности отображается на экран. Hа той же поверхности 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) Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
Архивное /ru.algorithms/52053D4872E2.html, оценка из 5, голосов 10
|