How do I represent used space in 2d?

Question

I have fixed area 2d space filled with rectangles. I'd like to move the rectangles around, add new ones, remove some, but not allow them to overlap. If all of the rects are the same height and width (50x50px), what data structure should I use to store their position and what space they are using and what lookup method should I use against that structure when adding new rects to the scene?

Answer 1

I'm not sure I fully understand your environment but you could consider using a 2-dimensional array which is essentially a matrix. Each spot would represent one of your squares in your 2D space.

Answer 2

This is the easy part of the classic collision detection problem. Mostly AABB Trees (not sure if that's the best link, but that's the name, anyway) are used to solve it efficiently, but look up anything collision detection algorithms use for bounding box collision detection. An AABB (Axis Aligned Bounding Box) Tree is for rectangles that are "aligned"-- that is, rectangles that cannot be rotated.

For non-aligned rectangles, just take the smallest axis-aligned rectangle that contains your rotated rectangle. Indeed an AABB tree is used to speed up collision detection for arbitrary polygons, by taking their bounding boxes. In the case of where an axis-aligned bounding box is equal to all your objects, it's even better.

However, if you don't mind performance, using a flat list of rectangles and doing an O(n²) search would really be easier: in pseudocode:

function intersection_free(rectangles)
    for rect in rectangles
        for rect2 in rectangles
            if intersects(rect, rect2)
                return false;

    return true;

Simplicity is a wonderful thing, isn't it?

Answer 3

In general, you should use a multidimensional data structure when dealing with these kind of problems. kd-tree and R-tree are good starting point to learn the subject. Since these structures are relatively complex, consider using it only if you need to deal with 1000's of rectangles / do fast calculations.

However, in your specific case - And if the plane size is limited - you can use a grid (let's say 100x100) of cells, that divides the plane, and store a list of rectangles in each cell, according to the top-left corrdinates of each rectangle. When searching for collision, search in the relevant cell and it's neighbours only. Since your rectangles size is constant, this may be the best solution for you. Note that you can store the 2D array in a 1D array where each grid-cell index is 100X+Y. Now, you can store grid-cells in a map to save memory.

If you are dealing with a small/slow scale problem, Just store the rectangles in a list and walk over the list to search for a collision.