| Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате |
| Форум программистов > Алгоритмы > Вычисления факта столкновения объектов |
| Автор: nerezus 23.12.2006, 23:28 |
| Имеется куча объектов. Они все в 2D пространстве, для простоты положим, что объекты прямоугольные или круглые, хз. И они движутся =) Как легче всего рассчитать, не столкнулся ли объект с другими? Т.е. тупо проверять, не находятся ли их центы в близости друг от друга? Причем для определенного объекта перебирать все другие на наличие "близости"? |
| Автор: maxim1000 24.12.2006, 03:00 |
| слышал как-то об использовании такого подхода (очень приблизительное описание): делим пространство пополам и каждый объект сравниваем только с объектами из его половины это уменьшит работу в среднем в два раза если делить дальше (и по вертикали,и по горизонтали), количество сравнений будет уменьшаться т.е. пространство представляется "в клеточку" для каждой клеточки есть массив объектов в ней, чтобы быстро доступиться к каждому интересующему чтобы разобраться с объектами, близкими к границе, можно добавить в кандидаты на столкновение и объекты соседних клеточек (всё равно суммарная работа получится меньше) название было типа ***-деревья |
| Автор: cardinal 24.12.2006, 03:18 |
| Название сего дела kd-tree (сокращение для k-dimensional tree) . http://en.wikipedia.org/wiki/Kd-tree |