8

Given a collection of say, 50, images with various widths and heights, how would one go about programmatically arranging them in an interesting* abstract way? (see image below)

enter image description here

  • By interesting I mean, no large gaps, and no easily distinguishable rows or columns (negative space forms a lot of T-like intersections).

For my specific case, all images have a set max dimension of 150px, which could mean the height OR width is a max of 150px (could be 150px by 450px, or 378px by 150px).

This seems like it could be a classic programming challenge but I'm finding the topic hard to Google...

EDIT: Changed image to show that there is no restriction on how the overall arrangement must be (doesn't have to fit inside a set area)

Jeff Mercado
  • 129,526
  • 32
  • 251
  • 272
andrhamm
  • 3,924
  • 4
  • 33
  • 46

3 Answers3

1

If you are not opposed to jquery plugin, you can check this out - http://masonry.desandro.com/

rchiriboga
  • 187
  • 2
  • 16
0

Your problem is NP-Hard.

This thread shows that even with one type of nXm rectangles, it is NP-Hard to find if there is a solution , so your more generalized problem is of course NP-Hard as well [The only one type of rectangle is a private case of this problem]

You could try a backtracking solution if you are after optimized solution, or a heuristic approach such as genetic algorithms or hill climbing, which will be faster - but will usually find a non optimal result.

Community
  • 1
  • 1
amit
  • 175,853
  • 27
  • 231
  • 333
  • @Triptych: I did not understand you, what is "random treemap?" [what do you mean by "it's"? what is it?] And why do you claim it is not NP-Hard? it is a variation of the 2d-bin packing – amit Feb 15 '12 at 17:57
  • It's only NP-hard if you have the rectangle sizes beforehand. If you can pick sizes to suit you as you go, you can just recurse by randomly subdividing the original rectangle. – Kenan Banks Feb 15 '12 at 17:59
  • My mistake - just noticed that the sizes are given. You're right. – Kenan Banks Feb 15 '12 at 18:02
  • @Triptych: If you want best `"no large gaps"` [as the OP asks], you need to find the minimal rectangle that your given 50 images can fit in. If you could find it in polynomial time, you could also find in polynomial time the answer if you have the sizes beforehand. – amit Feb 15 '12 at 18:04
  • Would the complexity change (become easier) if I added in that the arrangement doesn't need to fit within a set rectangle? I kinda figured it would start in the center and fill in, moving outward to make (potentially) an arrangement like a circle? Kinda like this[https://img.skitch.com/20120215-gtt2ckhe46hap2xik1tb8yhi4b.jpg] – andrhamm Feb 15 '12 at 18:20
  • @andrhamm: It won't. The complexity of the problem is not the outer rectangle, it's minimizing the gaps. – amit Feb 15 '12 at 18:26
0

I have built something similar to this (although it is probably not the most sophisticated solution). My approach was to use a quadtree to organize the rectangles that I had placed on the canvas. I then just basically went around the center point in a spiral, trying to place new rectangles, and using the quadtree to detect collisions. If I detected a collision then I would move the rectangle I was trying to place to the edge of the rectangle that it collided with that was furthest from the center and repeat the collision checking process.

Again, probably not the most sophisticated method, and it does tend to leave some larger gaps between rectangles (the borders between them are not uniform), but to my taste it gave good results.

Gordon Bailey
  • 3,881
  • 20
  • 28