Randomly and efficiently filling space with shapes

Question

What is the most efficient way to randomly fill a space with as many non-overlapping shapes? In my specific case, I'm filling a circle with circles. I'm randomly placing circles until either a certain percentage of the outer circle is filled OR a certain number of placements have failed (i.e. were placed in a position that overlapped an existing circle). This is pretty slow, and often leaves empty spaces unless I allow a huge number of failures.

So, is there some other type of filling algorithm I can use to quickly fill as much space as possible, but still look random?

Answer 1

Issue you are running into

You are running into the Coupon collector's problem because you are using a technique of Rejection sampling.

You are also making strong assumptions about what a "random filling" is. Your algorithm will leave large gaps between circles; is this what you mean by "random"? Nevertheless it is a perfectly valid definition, and I approve of it.

---

Solution

To adapt your current "random filling" to avoid the rejection sampling coupon-collector's issue, merely divide the space you are filling into a grid. For example if your circles are of radius 1, divide the larger circle into a grid of 1/sqrt(2)-width blocks. When it becomes "impossible" to fill a gridbox, ignore that gridbox when you pick new points. Problem solved!

---

Possible dangers

You have to be careful how you code this however! Possible dangers:

• If you do something like if (random point in invalid grid){ generateAnotherPoint() } then you ignore the benefit / core idea of this optimization.
• If you do something like pickARandomValidGridbox() then you will slightly reduce the probability of making circles near the edge of the larger circle (though this may be fine if you're doing this for a graphics art project and not for a scientific or mathematical project); however if you make the grid size 1/sqrt(2) times the radius of the circle, you will not run into this problem because it will be impossible to draw blocks at the edge of the large circle, and thus you can ignore all gridboxes at the edge.

---

Implementation

Thus the generalization of your method to avoid the coupon-collector's problem is as follows:

Inputs: large circle coordinates/radius(R), small circle radius(r)
Output: set of coordinates of all the small circles
Algorithm:
  divide your LargeCircle into a grid of r/sqrt(2)

  ValidBoxes = {set of all gridboxes that lie entirely within LargeCircle}

  SmallCircles = {empty set}

  until ValidBoxes is empty:
    pick a random gridbox Box from ValidBoxes
    pick a random point inside Box to be center of small circle C

    check neighboring gridboxes for other circles which may overlap*
    if there is no overlap:
      add C to SmallCircles
      remove the box from ValidBoxes  # possible because grid is small
    else if there is an overlap:
      increase the Box.failcount
      if Box.failcount > MAX_PERGRIDBOX_FAIL_COUNT:
        remove the box from ValidBoxes

  return SmallCircles

(*) This step is also an important optimization, which I can only assume you do not already have. Without it, your doesThisCircleOverlapAnother(...) function is incredibly inefficient at O(N) per query, which will make filling in circles nearly impossible for large ratios R>>r.

This is the exact generalization of your algorithm to avoid the slowness, while still retaining the elegant randomness of it.

---

Generalization to larger irregular features

edit: Since you've commented that this is for a game and you are interested in irregular shapes, you can generalize this as follows. For any small irregular shape, enclose it in a circle that represent how far you want it to be from things. Your grid can be the size of the smallest terrain feature. Larger features can encompass 1x2 or 2x2 or 3x2 or 3x3 etc. contiguous blocks. Note that many games with features that span large distances (mountains) and small distances (torches) often require grids which are recursively split (i.e. some blocks are split into further 2x2 or 2x2x2 subblocks), generating a tree structure. This structure with extensive bookkeeping will allow you to randomly place the contiguous blocks, however it requires a lot of coding. What you can do however is use the circle-grid algorithm to place the larger features first (when there's lot of space to work with on the map and you can just check adjacent gridboxes for a collection without running into the coupon-collector's problem), then place the smaller features. If you can place your features in this order, this requires almost no extra coding besides checking neighboring gridboxes for collisions when you place a 1x2/3x3/etc. group.