CODEWITHSUNDEEP
c++algorithm
nervousDev
nervousDev

Reputation: 72

2 dimension geometric layout of objects

so I have this class:

class Piece{
  int width;
  int height;
}

my problem is that I need to make a container type class that somehow can save the layout of multiple and different size "Piece" objects (note that Piece can only represent rectangles).

Example:

________
| t     |
| t  jj |
| t  jj |
_________

My goal with this is to be able to "fill" a empty rectangle with multiple "Piece" objects but with the ability to know if the "Piece" can fit in.

I'm developing this in C++. I started with the most logic solution I think that was to use a "matrix" of vectors (vector< vector< Piece * > > mat) but that doesn't work because as I said "Piece" objects can have different sizes.

I hope you can give some hints on how to get a solution for this or if it exists some lib or open-sorce project links.

Thank you.

EDIT

I forgot this:I know beforehand the dimensions of the container and the insertion (after validation) is sequential (Piece after Piece) with no predefined orientation.

Upvotes: 0

Views: 64

Answers (1)

thefunkyjunky
thefunkyjunky

Reputation: 522

You can use Piece p[width][height] and use memset to make all zeros or use a std::vector if you don't know the size of the grid beforehand. Then you can check(while adding a new Piece at some position (x, y)) if on any of its subsquares there is some other Piece already.

Edit: You can use a matrix char mem[sqrt(width)][sqrt(height)]; and a one vector of Pieces. Then using the matrix if there will be a probable collision and if not, just add the Piece. Else you iterate through all the existing ones and check for a collision.

If you want to make the procedure faster( this one is reasonable only with small grids ), then you will need to use more "advanced" data structures. What I suggest you is to learn about 2D BIT(or fenwick) trees(there are a lot of resources on google). You can also use 2D segment trees. Then when adding a new Piece at position (x, y) check the sum of all squares in it(e.g from (x, y) to (x + width, y + height)). If that sum is zero then the new Piece won't collide with previous ones and you then update the grid as you add 1 to all squares in your Piece(I mean to the corresponding values in the 2D segment tree). Else if the sum is greater than zero it means that there will be some overlap and you must then discard the new Piece.

Upvotes: 1

Related Questions