Jump to content

Brute force square/rectangle packing in non square grids?

Recommended Posts

Currently wondering if it's possible to do something similar to the image below:


I want to be able to pack rectangles and squares into a uneven grid of points, 2x2, 2x4, 1x3, etc.. I'm not sure how to go about this those as it doesn't seem as simple as making a 2d array and checking if a pointer goes out of bounds?

I don't mind if it's brute forced as all the squares don't need to be filled, just most of them. Struggling to find a solution to this though




Edited by Pidgy
Link to comment
Share on other sites

The points in your image still appear to be a regular square grid with irregular edges, so you could probably accomplish what you are looking for using a grid and some VEX to delete prims that you don't want.  I would probably delete them randomly in a while loop, then come up with a check that would be able to detect the patterns.  I will have to noodle on it, though I do have some ideas.  I'm thinking using area vs perimeter to check if a block has become a valid shape since there is a unique set for both that will mean it has the right shape.  That only works if you have a uniform area per prim though.  If you want to use non-uniform, it gets much more complex.  Doing it this way could actually allow you to select any shape, though mirrors would be identical so an L shape could be possible to find, but the other 3 variations of it would pop up as well.  You could also have a half-edge calculation walk around the shape and check the number of corners, so any 4 corner shape would indicate that it is a rectangle, anything more would be ignored.

No matter how you slice it, you are asking about a very interesting Comp Sci/Math problem.

Link to comment
Share on other sites

Unless I'm misunderstanding, this seems to essentially be a shape/object packing problem - there have been threads on that here with a number of example files, so if that is indeed what you're after, I'm sure you'll find a solution previously posted

Plus an entagma tutorial you might find useful:



Edited by ryew
including links to previous posts
Link to comment
Share on other sites

points Grid

vector2 pos = rand (@elemnum)-{.5,.5};
pos *= 10;

int pt = addpoint(0,pos);
vector scale = fit01(rand(@elemnum+0.1),{0.2,0.5,1},{1,1,1});

float pscale = length(set(scale.x,scale.y));

vector nor= {0,0,1};

vector up = fit01(rand(@elemnum*0.2),{-1,-1,0},{1,1,0});
up= normalize(up);



vector avg;
vector scale;
vector pos;
vector dir;
vector up;

int n = len(near_pts);
foreach(int pt; near_pts){
        scale = point(0,"scale",pt);
        pos = point (0,"P",pt);

        dir = @P-pos;
        up = point(0,"up",pt);

                        @up += length(@up-up)*(up-@up)/n;

                if(abs(dot(dir,v@side))<scale.x+@scale.x && abs(dot(dir,@up))<scale.y+@scale.y){
                        avg += 1.2*(@P-pos)/pow(length(@P-pos),4);

                        } else if(n<chi("compactnes")){
                                avg += pow(length(dir),2)*(pos-@P)/n;

@P += 0.008*normalize(avg);


int pts[];
matrix xform = instance(@P,@N,@scale,0,@up);

foreach (vector pos;{{-1,-1},{-1,1},{1,1},{1,-1}}){

         pos *= xform;
         append ( pts,addpoint(0,pos));
int prim = addprim(0,"poly",pts);





Edited by Librarian
  • Like 1
Link to comment
Share on other sites

Join the conversation

You can post now and register later. If you have an account, sign in now to post with your account.
Note: Your post will require moderator approval before it will be visible.

Reply to this topic...

×   Pasted as rich text.   Paste as plain text instead

  Only 75 emoji are allowed.

×   Your link has been automatically embedded.   Display as a link instead

×   Your previous content has been restored.   Clear editor

×   You cannot paste images directly. Upload or insert images from URL.

  • Create New...