I'm spaced out!

September 29, 2005 3:10 PM

Programming/geometry: in a Flash program (you don't need to know Flash to answer this), I'm trying to place rectangular images at random positions on the screen. There are already images on the screen. I need to make sure that the new, randomly-placed images don't obscure the images already there.

So I've got a rectangular screen and I know its width and height. I also know the x,y coordinates of each image already on that screen. And I know each image's width and height. I also know the dimensions of all the images not yet placed.

New images (and already placed items) are NOT all the same size (different widths & heights). Which makes things difficult.

So lets say I need to place a 100px by 200px image on the stage. I need to somehow generate a list of all the 100x200px (or greater) free areas. Then I just need to randomly pick one of those areas and place the new image in it. That last part's east. It's finding the free space that's confusing me.

Given the info I have (x/y coords, w/h of screen, w/h of images), how do I proceed?
So, before placing a new image

posted by grumblebee to computers & internet (25 comments total)

Yeesh, that's a tough one. That's like an ACM Programming Contest question. Would a lazier solution be acceptable? Like, you have a function that tells you if an image placed at x,y of w,h would overlap any already placed images, and you just pick random points until you find one that doesn't overlap or you give up?
posted by Capn at 3:20 PM on September 29, 2005

Simplest answer: Just place all the new random images on a layer beneath the current ones.

Or, maybe you could have your images come in completely at random then do hitTest check to see if it overlaps one of the existing images. Then you could delete the overlapping image or place it behind or move it or whatever.
posted by ssmith at 3:24 PM on September 29, 2005

Yuck, that's horrid. Off the top of my head this is what I would do, but it's untested and may have loads of holes in, sorry if it's not explained very well.

Grid up your space so you have to search less points, say every 32 pixels or something.

For each x,y point (x1,y1) on your grid loop over all the images that are currently on the page and calculate the x distance and y distance from the center of each image (x2,y2) to get a distance "power" like this...

Power = 1/((x1-x2)^2 + (y1-y1)^2) (which is putting 1 over the square of the hypotenuse). Add that value to a running total for the current grid point.

So if you have 16 grid points and 6 images, each grid point would have the total "power" based on it's distance from all 6 images.

The grid point with the weakest power, is in theory the one that is furthest away from most images, this most likely to be in an open space. I'd then test the weakest points for suitability.

If none of the points are suitable resort to brute force.

Perhaps you can improve the algorithm by making images with larger areas have more "power" and smaller with less to favour testing near smaller images.

Anyway in short the plan is to try and find spots that are as far away from the other images as possible. The downside of this is that you're going to be putting images right into the middle of spaces, reducing the remaining free space (maybe put it down and move it over in one direction until you hit and then move it back a bit?)
posted by RevDanCatt at 3:48 PM on September 29, 2005 [1 favorite]

Oh, forgot. If none of the weak points are suitable (they may be unsuitable by a few pixels), re-grid a smaller area around the weak points and retest again.
posted by RevDanCatt at 3:50 PM on September 29, 2005

Capn and ssmith have already suggested a simpler solution (hit testing), but it sounds like you could do a subdivision algorithm. Your screen is a rectangle. Is there anything on it? If yes, then divide it in half. Check each half - is there anything on it? If yes, ... etc. At the end of this recursive algorithm, you'll be left with a list of empty rectangles. If you want to be really clever, you can coalesce adjacent empty rectangles when you're done.

The advantage of this solution over hit testing is that it'll be faster if your images are static and you'll refer to the empty spaces often. The disadvantge is that you've divided your empty space up in such a way that many possible locations for, say, a 100x200 random image will be excluded.
posted by zanni at 3:53 PM on September 29, 2005 [1 favorite]

Sorry to hit you all with such a brainteaser. I was hoping (and maybe I'm still right???) that there is some clever math trick that could solve my problem and that a function already exists.

I've thought about the hitTest thing, and I may go with that, but it has some drawbacks. Besides (probably) being slow, it might bog down forever -- there might be NO space big enough for a specific image. But the program would keep trying to find space for it anyway. So I would have to program in an arbitrary stop-time. Which would also suck, because maybe there IS space for the image and the random choices just got unlucky so far. Also -- and I'll admit that this isn't the most important factor -- the hitTest solution feels like an ugly, awkward kludge. I was hoping for something more elegant.

simplest answer: Just place all the new random images on a layer beneath the current ones.

ssmith, I wasn't clear enough. This won't work because the images mustn't VISUALLY overlap. Imagine you had a wall in your house with some pictures on it of various sizes. You need to place NEW pictures (also of various sizes) on the wall, but the new ones can't overlap with the old ones). This is easy to eyeball as a human. How do you get a computer to do it?

Are there other, better forums where I might get an answer? I know some good Flash forums, but there might be a C++ programmer or a Calculus professor (who doesn't know Flash) who could help me out.
posted by grumblebee at 4:11 PM on September 29, 2005

Subdivide your screen into a grid of AxB squares. Maintain a list of all the squares that aren't covered by an image. When the time comes to place a new image, calculate how many adjacent squares it needs and iterate over the list looking for adjacent squares. This is sort of what RevDanCatt was saying, but you don't need to do any calculation--just a yes/no if the square is covered. This solution will be very fast because you can iterate over the empty squares list, select a square and examine its neighbors to see if it can support the image and, if it can't, you can remove the empty square and deprioritize the neighbors.
posted by nixerman at 4:14 PM on September 29, 2005

Sorry for the huge comment - my <pre>s are coming out double-spaced for some reason.

I'm miserable at algorithms, so this is probably pessimal, but here's what I'd do. Start from (0, 0) and "draw" a line through your canvas, making a list of the rows of blanks, something like this:

for each pixel

  if it's blank

    if inagap is true

      thisgapsize = thisgapsize + 1

    else (this is a new gap)

      thisgapstart = thecurrentpixel

      thisgap = 0

  else (it's not blank)

    if inagap is true

      gaps = gaps + (thisgapstart, thisgapsize)

      inagap = false

    else

      don't do anything

Now you have a list of all the starts and lengths of the horizontal gaps in the picture. Now iterate through that list of gaps and, for each one, check whether the gap continues for the number of rows you need:

for each (gapstart, gapsize) in gap

  for each pixel in the height of the image:

    for each pixel between (gapstart) and (gapstart + gapsize)

      if it's not blank

        bail out

  we didn't bail out - this space is okay

The obvious flaw is that if the gap is 300 pixels and narrows to 200, it'll throw it away, even though your 200px image would fit. That's not hugely hard to fix - I'd just run the gap-check algorithm against each of the rows in question and throw away pieces where gaps didn't overlap, checking at the end if you still have a big enough hole.

Now, when you're all done this, if you have no usable gaps, move on to the next row. This isn't fast, and it isn't elegant, but hopefully it'll help you think of a fast, elegant way to do it. If not, well, CPU time is cheap these days anyway.

On preview - I like nixerman's algorithm better, but here I already went and typed this all out, so you get it anyway.
posted by pocams at 4:16 PM on September 29, 2005

A kludgy, but doable approach (playing off the first two answers) might be something like this:

1. Select a random point.
2. Test if that is inside an existing rectangle.
3. If not, drop a rectangle of shape A and total pixels N1, centered on that random point.
4. Do a HitTest, If it shows no collision, increase the total pixels to N2, and test again. Continue until a collision occurs; note the maximum non-collision size for shape A.
5. Repeat steps 3 and 4 for shapes B, C, D, etc. (square, tall-skinny, wide-skinny, etc.).
6. Store information on the largest retangle (shape, pixel count) that fits, for that random point.
7. Repeat steps 1 through 6 as desired, but saving only information on the random point with the largest area found since the search began.
8. When you stop searching, using information from step 7 to place the rectangle.


This is better than what zanni suggested, I think, because it is critical to "coalesce adjacent empty rectangles", in order to really determine what is possible, but this is not not exactly trivial - adjacent empty rectangles don't necessarily have exactly equal sizes facing each other, for example.
posted by WestCoaster at 4:17 PM on September 29, 2005

For your hit test:

Assuming that images are rectangular and you are not worried about transparency:

Have a list of the two diagonally opposite corners for each current image.

Then with the new image's corners ((xn, yn), ...):
- for each item ((x0, y0) (x1, y1)) on the list of existing images
-- if xn > x0 and xn -- if yn > y0 and yn
As to the problem of getting stuck, you need to maintain another data structure that models the distance between sides. You could build this up as you add each new image.

I'm not at home where I have the right books to look this up for you, but you're looking for terms like "hull", "perimeter", "boundary" and "polygon" when you google for algorithms. Adding "computer graphics" would help too, I have dim memories of problems of exactly this nature when I studied it years ago.
posted by i_am_joe's_spleen at 5:23 PM on September 29, 2005 [1 favorite]

grumblebee: What you're looking at is a restricted form of bin packing called I guess 2BP which is a Hard problem, so I don't think you're going to find a magic bullet.. but you might find a pretty good one.
posted by fleacircus at 5:33 PM on September 29, 2005

Don't kill yourself hunting for an ideal solution grumblebee. It looks like your algorithm is going to be at worst O(n^2) for a brute force hunt. Since you're dealing with 100 pix rectangles, this thing isn't going to scale very badly.

unless you're running this on a 386

You can't have a truly random solution since you're balancing it against 'making the free space work'. Do you need to completely pack the screen?

I'm going to go out on a limb here and say the Monte Carlo approach is best for you. Just randomly pick points for the upper left hand corner of your rectangle, then have a clever hit test algorithm to determine whether you have found a good space.

Think Battleship!
posted by onalark at 7:09 PM on September 29, 2005

I'd say it really depends -- on the size of the canvas, the size and number of images to place, the desired density, and how many times you need to do this. If you are talking about a 800x600 canvas and a dozen or so images of varying sizes, then the "monte carlo hit test" method is probably going to be the best way to go. If you're talking about a very large canvas or hundreds/thousands of relatively small images, or you will be repeating this many times (animation), or you need to pack these as densely as is possible (i.e. you need to know for sure whether it's possible to fit the next image anywhere or not) then you'll have to use an algorithm with more smarts to it.

Does the order matter, or are you only interested in the end result? Because if you just want to say "here are 'n' images, find me an arrangement where they are all on the canvas and none overlap" then you might consider something like simulated annealing where you start with them all positioned randomly and then interatively step through an algorithm where two sqaures that are overlapping repel each other by an amount proportional to the overlap. Or something like the "spring tension" model that is well understood.
posted by Rhomboid at 7:20 PM on September 29, 2005

Alright, I got something tricky.

Keep a list of all current images with x, y of top-left corner and w, h.

For every new image you want to insert, loop through the current list of images and attempt to place the new image on each of the four sides. If this would place the image off-screen (easy to calculate), discard this side and move to the next side. If it's on-screen, perform a hitTest() against the remaining images. If it fails, move on to the next side.

If all four sides are exhausted, move on to the next image.

Downside: It's not *random*, so if you want it to look random, you're boned. Also, it's specifically patterned, which will draw the eye and may be ugly.
posted by Imperfect at 9:04 PM on September 29, 2005

I don't really know what you're really trying to achieve, but here's a quick and dirty solution I whipped up based on Rhomboid's "spring tension" idea.

It does assume a couple things, but it may just be good enough depending on what you need.

1) Existing rectangles are allowed to be pushed by newer randomly placed rectangles

2) We'll model the rectangular constraints as circular ones (because I'm too lazy to really think after happy hour)

3) The layout algorithm is pretty CPU intensive...but I guess you'd only ever have to lay them out once anyways.

SWF
Click inside movie to reset

and source (Flash 8 file, I'm afraid...let me know if you need a more compatible version)
FLA

Like the rest said...there really isn't an elegant 5-minute approach to this. I'd say go with one of the brute force routines.
posted by pooya at 9:27 PM on September 29, 2005 [1 favorite]

Check out this "box fitting image" demo (click on one of the small/medium/large launch applet links). That shows a demo of boxes randomly distributed around the screen, very similar to what it is you're asking for (I think).

The source code to this app is written for an environment called "processing" which is really just a simple layer on top of java, so the code is quite easy to understand. I'm guessing that there is an algorithm in there that you can use.
posted by freshgroundpepper at 9:48 PM on September 29, 2005

Thank you all for the fascinating answers!

pooya, What happens if you hand it a rectangle that's too big to fit?

---

Having read through all your posts, I'm thinking that hitTest will be best for me, because I won't be dealing with that many rectangles. But I'll keep reading in case anyone comes up with something better.
posted by grumblebee at 6:18 AM on September 30, 2005

Here's an (animated, not programmed) demo of what I'm trying to do.
posted by grumblebee at 6:40 AM on September 30, 2005

The demo is very helpful.

Think about what happens when you place the first box on the screen. You've started with a single rectangular free space region: {left=0, top=0, right=screen_width, below=screen_height}. Placing the first box {box_left, box_top, box_right, box_below} destroys that free space region and creates four new, smaller, overlapping, rectangular free space regions:

above: {left=0, top=0, right=screen_width, below=box_top}
to the left: {left=0, top=0, right=box_left, below=screen_height}
below: {0, box_below, screen_width, screen_height}
to the right: {box_right, 0, screen_width, screen_height}

Maintain a list of free space regions, starting with a single entry representing the whole screen.

Every time you want to place a box, scan the list to find a free space region that's big enough to hold the box you want to place. Place the box in that space.

Next, scan the list for free spaces that intersect the box you've just placed. Each time you find one, remove it from the list and add entries for the newly created overlapping rectangles within the space just removed above, left, below and right of the box you've just placed.

In all cases except the original region you picked to put your box in, some of those newly created spaces will be degenerate (zero or negative width or height) and can be ignored; any with positive widths and heights get added back onto the list.

You might find there's a clever way to order the list so you don't have to scan the whole lot (perhaps it should be a tree). Do that tweak later, if you can be bothered.

When you remove a box, scan the list for free spaces immediately adjacent to its edges; as you find them, coalesce those with common corners.

Clear as mud?

Perhaps it would help to add shaded overlapping rectangles above, left, below and right of newly placed boxes in your animated demo.
posted by flabdablet at 8:16 AM on September 30, 2005

If you're really looking for some fun algorithms to help out, you need to see k-d trees, specifically spacial (skd trees) or extend kd-trees. They basically keep track of where things are and how much space is between them in d-dimensional space (2 dimensions in your case).

I worked on a fairly similar project once, but we were trying to pack boxes rather than lay them out. Unfortunately, I can't find any of the biblios for that work right now... but then there is always google!

Here is a nice Java applet to show how the algorithm works:
http://www.rolemaker.dk/nonRoleMaker/uni/algogem/kdtree.htm
posted by gus at 8:16 AM on September 30, 2005

Here's some great examples of various spacial indexing algorithms:
http://www.cs.umd.edu/~brabec/quadtree/
posted by gus at 8:47 AM on September 30, 2005

I had the same question several weeks ago for a psychophysics experiment I'm programming (a visual search task where targets/distractors can't be laid out in any obvious grid). So I asked a computational geometer, and he confirmed all of the above statements about the hardness of the problem.

In the end, I just took the Monte Carlo approach, which is "good enough" because my arrangements tend to be pretty sparse. I rejected the spring tension model because it was important to me to have a truly random distribution.

One improvement I might make to my algorithm next time I do this is add a check of the current arrangement to ensure that there is actually space for my object after the first collision occurs.
posted by Eamon at 10:07 AM on September 30, 2005

flabdablet, I had the same idea as you and was going to post it but after considering it for a while there is a giant gaping hole in that idea. If you treat the free space as a long list of rectangular regions, you miss opportunities to place boxes in the space created by two adjacent "space rectangles".

Let me give a quick example. Let's say you have a very simple 2x2 canvas, which so far has a single 1x1 placed in the upper left corner. So there are now three remaining rectangular spaces left - these could be represented by either a rectangle of 2x1 (or 1x2) and a 1x1 square, or three 1x1 squares.

Let's assume for the sake of argument that you choose to represent it as a 2x1 and a 1x1. Now you are asked to place a 1x2 object. Well shoot, that object won't fit in either of those two spaces, but it will fit in the combined space formed by both of them. And similarly if you chose to represent it as three 1x1s, and so on.

The point is that you can't just loop through a list of free rectangular regions and try to find one that is large enough to fit the shape. You have to consider the space formed by multiple adjacent regions as well. Or alternatively put, the particular rectangular representation that you choose is not unique to describe the space, because there would be many permutations of rectangular regions that you could choose to describe a complex space. In the example above, this is illustrated by noting that describing the space as "2x1 1x1" does not afford a match to "1x2" shape, but if you'd chosen the "1x2 1x1" representation it would. So in order to make this work you would have to simultaneously keep a list of EVERY permutation of rectangles that you could use to represent the space. This would be a LARGE amount of work, and it would be much easier to just try the target shape in every possible x,y coordinate.
posted by Rhomboid at 8:23 PM on September 30, 2005

Upon rereading your method I missed the part where you said you maintain a list of overlapping regions and so my example does not apply. However, I think that my general point still does: By doing it that way you still have to maintain an inordinately large list of regions due to the fact that you have to describe the space using every conceivable way of choosing the regions.
posted by Rhomboid at 8:30 PM on September 30, 2005

Well after thinking about it more I guess it's probably not as bad as I thought. I made a quick animation to help visualize this. The red boxes represent the regions that you would need to have in your list at that point. (I could very well have missed some.) In this simple case of only 3 rectangles placed, there are already a lot of regions and I wonder if it would grow uncontrollably. I guess it would be linear with the number of boxes placed.
posted by Rhomboid at 9:14 PM on September 30, 2005