5
\$\begingroup\$

Let us consider the case: there is an overall bounding rectangle (call this Rb) which contains a number of rectangles within it (call this set SRo). Now I would like to randomly position a new rectangle with known bounds (call this Rn) within the bounds of Rb without intersecting any of the rectangles in the set SRo

My current approach is rather brute force:

  1. Generate random x-y coordinates for new rectangle
  2. Check Rb contains Rn if it is placed at intended coordinates
  3. Check Rn does not intersect any of rectangles inside set SRo

Anyone got any better idea?

\$\endgroup\$
3
  • \$\begingroup\$ A couple questions: "known bounds" means that the size of Rn is fixed and you only have to randomly choose a point? Or does it mean that they will also be randomly generated but within some bounds? Question 2: Is it a pixel representation with integer coordinates or a vector representation where coordinates/sizes can be real values? \$\endgroup\$ Commented Dec 22, 2010 at 14:34
  • \$\begingroup\$ 1-known bounds mean size of Rn is fixed. 2-pixel representation with integer values \$\endgroup\$ Commented Dec 22, 2010 at 14:59
  • \$\begingroup\$ stackoverflow.com/questions/716558/… \$\endgroup\$ Commented Feb 19, 2017 at 15:19

6 Answers 6

Reset to default
2
\$\begingroup\$

Recursive subdivision is one simple and guaranteed finite-time solution, though it tends to look a little... non-uniform. The end result is reminiscent a bit of a mondrian painting and doesn't look exactly like random scattered rectangles. If that's still good enough for you, the algorithm is:

makeRects(x, y, width, height) if shouldSubdivide(width * height) then // pick which way to split it, tend towards making // the resulting pieces closer to square if random(width + height) < width then // split vertically var split = random(width) makeRects(x, y, split, height) makeRects(x + split, y, width - split, height) else // split horizontally var split = random(height) makeRects(x, y, width, split) makeRects(x, y + split, width, height - split) end else // not splitting the box, so just draw a rectangle inside it randomRect(x, y, width, height) end end // randomly inset the rect within the given bounds randomRect(x, y, width, height) var insetWidth = random(width) var insetHeight = random(height) var insetX = random(width - insetWidth) var insetY = random(height - insetHeight) placeRect(x, y, width, height) end // determine if a rect of the given area should be // subdivided, or if its small enough that we should // stop here shouldSubdivide(area) // return true or false. the smaller the area, the more // likely to be false. tune to taste... end random(max) // generate random value between 0 and max... end placeRect(x, y, width, height) // do whatever you want here to place the rect... end
\$\endgroup\$
2
\$\begingroup\$

This sounds similar to a collision-detection problem. Look at "spacial partitioning" to sub-divide Rb, and find the set of open spaces in which Rn would fit. Randomly select one of those spaces, and place Rn randomly within it.

\$\endgroup\$
1
  • \$\begingroup\$ definitely looking into it \$\endgroup\$ Commented Dec 22, 2010 at 15:49
2
\$\begingroup\$

If don't run that algorithm too often (eg. just at startup-time) and there aren't thousands of rectangles, I'd probably just stick with the brute-force approach.

You could already eliminate a lot of unnecessary trial/error attempts, by combining step 1 and 2 into one step. To do this, just make sure you generate random x and y coordinates that are guaranteed to be inside Rb.

Example in pseudo-code, assumes that random() returns a value from 0-1 and that y-axis points down (screen-space).

y = Rb.minY + (random() * (Rb.height - Rn.height)) x = Rb.minX + (random() * (Rb.width - Rn.width))

Then check the rectangle position against all the already placed rectangles. If it intersects another rectangle, restart at step 1.

Depending on the generated random-values, this approach could need a lot of tries to be successful though. An optimization would be to divide your containing rectangle (Rb) into sections and increase a counter for each section that intersects a placed rectangle. Then pick random coordinates from sections with a low "rectangle-count" in step 1.

If you try to place a lot of rectangles into Rb (so that a big part of the area of Rb is covered), the brute-force approach is a very bad choice, since there's a very high probability that it will fail (endless loop).

Maybe also have a look at this answer over at stackoverflow for another approach.

\$\endgroup\$
0
\$\begingroup\$

Sounds like a fair implementation, there is no simple trick for avoiding doing a fair amount of checking. If you have got a performance problem then show us your code, otherwise just stick with it.

\$\endgroup\$
0
\$\begingroup\$

Depending on the layout of rectangles already inside, if you find that brute-force is taking too many iterations (i.e. that there are too few valid spaces to put a new rectangle after some point in time), an alternative might be to iterate through the entire bounding box, making a list of all valid positions where the new smaller box can go. Then, choose a random element from that list. Worst-case O(x*y) time, which is at least better than the random worst-case O(infinity).

\$\endgroup\$
0
\$\begingroup\$

I used a greedy approach:

  • Rectangularize the overall (global) rectangle: create a grid from the sorted x & sorted y coordinates of all rectangles so far. So that will give you an irregular (but rectangular) grid.
  • For each grid cell calculate the area, this gives you a matrix of areas.
  • Use Kadanes 2D algorithm to find the sub matrix that gives you the maximum area (= the largest free rectangle)
  • Place a random rectangle in that free space
  • Repeat

This requires a conversion from your original coordinate space to/from the grid space but straightforward to do.

(Note that running Kadene directly on the original, global rectangle takes to long. Going via a grid approximation is plenty fast for my application)

\$\endgroup\$
1

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.