Rectangles intersections

Question

I have a list of rectangles and I need to generate a list of rectangles that intersect.
Rectangles are defined using

• Point
• Size
• Boolean whether the rectangle can move
• Boolean whether the rectangle can be removed

No rectangles can be moved but cannot be removed

An intersection is defined using

• Pointer to first rectangle
• Pointer to second rectangle
• List of points of the first rectangle that are in the second
• List of points of the second rectangle that are in the first

I need a container for this, as rectangles can be added, removed or moved. operations that I need:

1. Insert of rectangle
2. Remove of rectangle (only possible for those who are marked for it)
3. Changing position of rectangle (not size, only possible with those who are marked for it)
4. Generating set of intersections.

How would I go about implementing such a container? I can do it easily using cross check method, but that will be far from optimized.
I thought of keeping a map of rectangle -> intersection and then whenever a rectangle is added check if its intersecting anything and add intersection to the map, and when its removed, remove the key from the map, but I don't know how to check if it intersects anything fast, or how to move rectangles without remove and reinsert.
I can use C++11.

Answer 1

Assuming a left-to-right / top-to-bottom coordinate system, the intersection of two rectangles is the rectangle whose top is the bottomest of the tops, bottom is the toppest of the bottoms, left if the rightest of the lefts and right is the leftest of the rights.

You can efficiently run the tests if you can indirectly access the rectangles by containers that are sorted by left, top, right and bottom.

An alternative can be using a key (for the map) that is a x/delta pair with an operator< that consider a<b wherever a.x+a.delta < b.x and same for the y. A raw point is just a rectangle of size 1.

In essence, you need a container for the rectangle themselves (must not reallocate rectangles when modified, hence a std::list can work) and two std::maps (for horz and vert mapping) having a place/size pairs as key and a list iterator (can be a rectangle pointer resulting from &*iter) as value.

Answer 2

My recommendation would be a container vaguely like:

class region {
    typedef std::vector<vector*> subregion;
    std::array<std::array<subregion, 100>, 100> locations;
    std::vector<rectangle> children;
public:
    std::vector<rectangle>::iterator add(rectangle addme);
    void remove(std::vector<rectangle>::iterator deleteme);
    void move(std::vector<rectangle>::iterator moveme, point to);
    void intersect(std::vector<rectangle>::iterator left, 
                   std::vector<rectangle>::iterator right);
};

The children member is merely an iterative list of rectangles in the container. Each subregion is one-onehundredth of the total region that can hold rectangles. When a rectangle is added, pointers to it are added to all sub-regions that the rectangle touches. When a rectangle is removed, it's pointers are removed from all sub-regions that the rectangle touches. A move is effectively a removal, rectangle update, then an add.

Then, to find intersections (depending on how you want them), you simply look at each subregion that contains more than one pointer, and do a simple comparison of each of the rectangles in that subregion.