Какую посоветуете структуру для хранения пространственных данных?
BSP - дерево. Специально для вашей задачи. Кармак и Абраш одобряют.
Если речь о двумерке, то скорее всего это будут
Структура или тупля(в зависимости от языка)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
}