Check for placement overlap on large grid

Question

I am working on a game where you place buildings linked by connectors on a rectangular grid. Nothing can overlap. Buildings and connectors cannot change once they are on the grid; they can be destroyed any time. The grid is defined such that the bottom left corner is (0,0).

The buildings are rectangles, where each edge can be 1 - 4 units long; there are also a 5x5 squares.

Connectors have a start point and an end point. They cannot overlap, and are 1 unit wide. They can go in straight lines EDIT:(left, right, up and down) and bend wherever at 90 degrees. Unlimited length.

The grid would ideally be quite large (200x200 or greater) but that means there can be many thousands of these objects and connectors.

When an object gets built, I need to check whether or not it overlaps with anything. If I make a grid of bits, its size would be prohibitively large beyond 300x300. If I make a list of all objects, I could search within some limit, but how would I deal with connectors?

Seeing as a 2-D array of bits is not possible, I must index all buildings, and sort them by x coordinates, then by y coordinates. I could do a linear search for connectors, but that would be very tedious and painful.

Does anyone have a suggestion? P.S. I am doing this in C++

Answer 1

Apart that 300x300 is not large, and if you really wanted you could pack your boolean values in bits within a byte (but I don not suggest that for speed reasons) you can check if connectors intersect with a simple function: https://stackoverflow.com/a/565282/2436175

Assuming that you have already checked that your new building does not intersect with any other building, what is left to check is that the side of your new building (segment) do not intersect with any of the connectors you have already in place.