How can I effectively store a grid of rectangles?

Question

So, I was thinking of creating a game with different rectangular rectangles instead of squares, but I cannot find an effective way to do this. For example, I do not want to have a grid of tiles, such as Tetris, which make up each figure. I want each piece to be one object with a width and a height. For example, 2 * 3 pieces do not occupy 6 tiles, it will be just one rectangle. I must be able to effectively organize the figures and be able to get the work at a specific coordinate. If I used a two-dimensional array of plates, it would use memory that I do not need.

Answer 1

To get a rectangle at any given coordinate, resources are very expensive no matter how you do it, but probably the most efficient way would be to create a free grid in which the rectangles are not limited. Whenever a piece moves, it updates a two-dimensional array with its reference in all the squares that it contains in whole or in part. Whenever a coordinate is specified, calculate which square the coordinate is in the grid, and then from it you can perform more extensive calculations to check whether the coordinate is actually inside the rectangle or not.

Answer 2

To post this earlier, I know you already accepted the answer, but you can consider the following.

, , . , ( ), . , , , - ,

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

a b tile (0,3) , .

, , :

(0, 0).parent = 'a'

(0, 1).parent = 'a'

...

(2, 2).parent = 'a'

..

- .

"

, , . O(n), n , 1 n/2 ( , isn ' t - ).

. , O(1).

, :

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

: 5 , , .

, , .

, ...

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 ...
...

, , . , , , , .

---

NxN ( ), , .

Answer 3

Rectangle , .

Answer 4

Do 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 might work for your use case. The query for the rectangle at the given position is O (nlogn).