How can I efficiently store a grid of rectangles?

Question

So I was thinking about making a building game with different shaped rectangles instead of just squares, but I can't figure out an efficient way to do this. For example, I don't want to have a grid of tiles like tetris that make up each shape. I want each piece to be one object with a width and height. For example a 2*3 piece wouldn't take up 6 tiles, it would just be a single rectangle. I have to be able to do organize the pieces efficiently and be able to get the piece at a certain coordinate. If I just used a two dimensional array of tiles it would use memory that I don't need.

Answer 1

To get the rectangle at any given coordinate is very expensive on resources no matter how you do it, but probably the most efficient way would be to create a loose grid that the rectangles are not confined to. Whenever a piece moves it will update a two-dimensional array with its reference in all the squares it either fully or partially contains. Whenever given a coordinate, calculate which square in the grid the coordinate is in and then from that you can do more extensive calculations to check if the coordinate is actually inside the rectangle or not.

Answer 2

Meant to post this earlier, I know you've already accepted an answer but you might want to consider the following.

I think I understand what you're asking. You want to check what rectangle a tile belongs to (if any) by checking the rectangle bounds. So to check if the top right tile in this square belongs to any rectangle where any - is a tile that belongs to no rectangle

a a a -
a a a b
a a a b
a a a b

you would check the rectangle a and rectangle b for tile (0,3) and see that it belongs to neither.

The alternative you're trying to avoid is by setting each tile to belong to a rectangle:

(0, 0).parent = 'a'

(0, 1).parent = 'a'

...

(2, 2).parent = 'a'

etc

or something similar to that.

The trade-off for each solution is different"

In the first one, you're going to have to do a ton of comparisons each time you want to find what rectangle a tile belongs to. O(n) comparisons, where you will compare n times in the worst case, 1 in the best case, and n/2 comparisons on average (if each tile has an equal chance of belonging to a rectangle, which isn't true in tetris-like games).

In the second solution, you have to store a parent variable to each tile. This increases memory usage but the time complexity always remains O(1).

Each one might be better depending on how your grid is likely to be set up:

a a a a a a a a a a a b d d d d d d d d
a a a a a a a a a a a b d d d d d d d d
a a a a a a a a a a a b d d d d d d d d
a a a a a a a a a a a b d d d d d d d d
a a a a a a a a a a a b d d d d d d d d
a a a a a a a a a a a b d d d d d d d d
a a a a a a a a a a a - e e e e e e e e
a a a a a a a a a a a c e e e e e e e e
a a a a a a a a a a a c e e e e e e e e
a a a a a a a a a a a c e e e e e e e e

Checking the parent of a specific tile is pretty quick: you just check 5 rectangles, if the tile isn't in any, it has no parent.

Checking if a tile has a parent is just as quick.

However, when you begin to have more and more rectangles...

a b c d e f g h i j k l m n o p q r s t
A B C D E F G H I J K L M N O P Q R S T
u v w x y z U V W X Y Z 1 2 3 4 5 6 7 8
9 0 ...
...

You have to do a LOT of comparisons to find if a specific tile has a parent or not. Instead of pinpointing a coordinate and checking its parent value, you have to check every single rectangle to see if the tile is in any of them.

---

I suggest you simply use an NxN grid and store a parent rectangle value for each tile (first solution) unless you know you're not going to use that many rectangles or the grid is going to be filled mainly with empty spaces.

Answer 3

I would simply create a class Rectangle with Width and Height, then I would use an array of this class' instances.

Answer 4

Do the rectangles overlap? If not, you can use the RectangleGrid class here: https://github.com/eyal0/OctoPrint-Slicer/blob/master/src/RectanglePacker.js#L10

Adding a rectangle is potentially slow but for your use case might work. Querying the rectangle at a given position is O(nlogn).