Какую посоветуете структуру для хранения пространственных данных?

Question

[Syxov]

Доброго времени суток.
В рамках курсовой в университете разрабатываю простейшую онлайновую игру а-ля World of Tanks. Встал вопрос о хранении положения игроков в пространстве.
Подскажите, существует ли такие структуры данных, что:
1) Они хранят пространственные данные
2) Позволяют за приемлемое время обновлять данные (т.е. не удалять/добавлять новые значения, а именно обновлять те, что уже есть)
3) Определять коллизии между объектами, являющимися прямоугольниками и, в большинстве своём, повёрнутыми на какой-либо угол
Возможно поможет тот факт, что координаты объектов двумерные.

Если же таких структур нет, то я буду рад, если Вы поделитесь возможными решениями данной проблемы.
Спасибо.

UPD. Прошу меня извинить, но я забыл про ещё одно важное условие
4) Необходимо находить все объекты в некоторой заданной области.

Comments

[Deerenaros]

Может быть меня закидают тапками (уже летит один, сам в себя запустил), но почему-бы не сосредоточиться на функционале, а потом реализовывать велосипеды (иначе по срокам можно не уложиться). В любом случае, рекомендую использовать box2d. Свой box2d можете написать позже.

Answer 1

[Армянское Радио]

BSP - дерево. Специально для вашей задачи. Кармак и Абраш одобряют.

Comments

[Syxov]

Добавил ещё один пункт к требованиям к структуре. Скажите, BSP-tree можно реализовать так, что б оно отвечало ему?

[Армянское Радио]

Александр: Да, оно именно для этого и строится.

Answer 2

[uvelichitel]

Если речь о двумерке, то скорее всего это будут
Структура или тупля(в зависимости от языка)

Point{
abcissa Integer
ordinata Integer
}

Массив или лист(в зависимости от языка)
Contur[Point]
Структура или тупля(в зависимости от языка)

Object{
Position Point //Положение в абсолютных координатах
Contur [Point] //В координатах относительных к положению
Scale Integer //Коэффициент масштабирования
Turn Integer //Угол поворота
}

И как совершенно верно заметил @Армянское Радио - BSP дерево. В двумерке обычно применяют конкретно QuadTree, примерно такое

Quad{
Position Point
Size Point
Objects [Object] //Массив или лист объектов лежащих полностью в четверти Quad 
NordOst *Quad //Четыре дочерних четверти
NordWest *Quad //Это как правило рекурсивная структура
SudOst *Quad
SudWest *Quad
}