Пока я нашел только quadtree's и алгоритм, использующий представление каждого объекта на интервалы по осям
...P.S. пока тему печатал, догадался шапку подфорума посмотреть
щас, по ссылка пойду, но вы все равно пишите | Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате |
| Форум программистов > Алгоритмы > Алгоритмы по определению наличия пересечения |
| Автор: Aldvin 24.9.2006, 23:25 |
| Какие вы знаете скоростные алгоритмы по определению пересечения множества прямоугольников в двумерном пространстве? Надумал я тут движок спрайтовый покодить, вот возникла проблемка, как определять столкновения спрайтов... Пока я нашел только quadtree's и алгоритм, использующий представление каждого объекта на интервалы по осям ...P.S. пока тему печатал, догадался шапку подфорума посмотреть щас, по ссылка пойду, но вы все равно пишите |
| Автор: ILAgent 24.9.2006, 23:37 |
| Ещё есть R-деревья |
| Автор: Silent 3.10.2006, 09:18 |
| У меня была похожая задача, и я сделал ее следующим образом. У нас есть очередь, в которой мы будем хранить обработанные непересекающиеся прямоугольники. Для обработки нового прямоугольника нам нужно пробежаться по очереди, разбивая пересекающиеся прямоугольники на несколько непересекающихся. Могу предоставить исходник на С++ |
| Автор: Aldvin 3.10.2006, 17:27 |
| Silent, было бы неплохо посмотреть твой вариант, а то что-то я не совсем понял... Нашел отличную статью на http://en.wikipedia.org/wiki/Collision_detection |