Проверьте наложение мест на большой сетке

Я работаю над игрой, в которой вы размещаете здания, соединенные соединителями, на прямоугольной сетке. Ничто не может пересекаться. Здания и соединители не могут измениться, если они находятся в сети; они могут быть уничтожены в любое время. Сетка определена так, что нижний левый угол равен (0,0).

Здания представляют собой прямоугольники, каждый край которых может быть длиной от 1 до 4 единиц; Есть также квадраты 5х5.

Разъемы имеют начальную точку и конечную точку. Они не могут перекрываться и имеют ширину 1 единицу. Они могут идти по прямой линии РЕДАКТИРОВАТЬ: (влево, вправо, вверх и вниз) и сгибаться везде на 90 градусов. Неограниченная длина.

В идеале сетка должна быть достаточно большой (200×200 или более), но это означает, что таких объектов и соединителей может быть много тысяч.

Когда объект создается, мне нужно проверить, перекрывается ли он чем-либо. Если я сделаю сетку битов, ее размер будет чрезмерно большим, чем 300×300. Если бы я составлял список всех объектов, я мог бы искать в пределах определенного предела, но как бы я справился с соединителями?

Просмотр двухмерного массива битов невозможен, я должен проиндексировать все здания и отсортировать их по координатам x, а затем по координатам y. Я мог бы выполнить линейный поиск разъемов, но это было бы очень утомительно и больно.

У кого-нибудь есть предложение?
Постскриптум Я делаю это в C ++