Проблема с огромными объектами в четырехугольном дереве

Question

Допустим, у меня есть круглые объекты.Каждый объект имеет диаметр 64 пикселя.

Ячейки моего четырехугольного дерева, скажем, 96х96 пикселей.

Все будет хорошо и будет работать хорошо, когда я проверяю столкновение с ячейкой, кругнаходится в + всех соседних ячейках.

НО, что если у меня есть один круг диаметром 512 пикселей?Это будет охватывать много ячеек, и, таким образом, это будет проблемой при проверке только соседних ячеек.Но я не могу изменить размер моей четырехугольной сетки каждый раз, когда в дерево вставляется гораздо больший объект ...

Answer 1

Вместо того, чтобы помещать объекты в одну ячейку, поместите их во все ячейки, с которыми они сталкиваются. Таким образом, вы можете просто проверить каждую ячейку в отдельности. Используйте указатели на объект, чтобы не создавать копии. Также вам нужно делать это только с заквасками, поэтому нет необходимости объединять данные, содержащиеся в более высоких узлах, с более низкими.

Answer 2

Это интересная проблема.Может быть, вы можете расширить узел или ячейку с информацией о высоте дерева?Если у вас есть объект больше, чем самая маленькая клетка, вложите его в высоту дерева.Это то, что делает приложение карты, такое как Google или Bing Maps.

Вот ссылка на похожее решение: http://www.gamedev.net/topic/588426-2d-quadtree-collision---variety-in-size. Я путал экран с деревом квадрантов.Вы можете проверить столкновение с помощью простого отвода.