StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>Subdivide your window into <code>w</code> by <code>h</code> blocks. You'll be maintaining a <code>w</code> by <code>h</code> array, <code>dist</code>. <code>dist[x][y]</code> contains the size of the largest circle that can be centred at (x, y). (You can use pixels as blocks, although we'll be updating the entire array with each circle placed, so you may want to choose larger blocks for improved speed, at the cost of slightly reduced packing densities.)</p> <h2>Initialisation</h2> <p>Initially, set all <code>dist[x][y]</code> to <code>min(x, y, w - x, h - y)</code>. This encodes the limits given by the bounding box that is the window.</p> <h2>Update procedure</h2> <p>Every time you add a circle to the window, say one positioned at <code>(a, b)</code> with radius <code>r</code>, you need to update <em>all</em> elements of <code>dist</code>.</p> <p>The update required for each position <code>(x, y)</code> is:</p> <pre><code>dist[x][y] = min(dist[x][y], sqrt((x - a)^2 + (y - b)^2) - r); </code></pre> <p>(Obviously, <code>^2</code> here means squaring, not XOR.) Basically, we are saying: "Set dist[x][y] to the minimum distance to the circle just placed, unless the situation is already worse than that." <code>dist</code> values for points inside the circle just placed will be negative, but that doesn't matter.</p> <h2>Finding the next location</h2> <p>Then, when you want to insert the next circle of radius <code>q</code>, just scan through <code>dist</code> looking for a location with <code>dist</code> value >= <code>q</code>. (If you want to randomly choose such a location, find the complete list of valid locations and then randomly choose one.)</p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload