I find that a very elegant way of random placement is the use of Halton sequences.
Compare the random with Halton, here:
As you can see, the Halton-2,3 distribution is much more orderly, in that all points have their neighbours at a reasonable distance. Also, it progressively densifies, so the first samples are all widely spaced apart.
Now, in your specific application, you want to grow outwards. You could achieve this with filtering the sequence based on proximity to centre.
Do you ever want your cities to show 'infill?' If not, you could simply sort the sequence on distance to centre, and create them in that order.
If you do want occasional infill, I would push them outward, with increasing distance for each city. The extends will grow, yet, spaces in the interiour will get filled every now and then.
You could also reject outliers based on a radius, with a growing radius as the city grows.
The code to reject samples would look like this:
i = 0
while numaccepted < numv:
x = -1 + 2 * halton( i, 2 )
y = -1 + 2 * halton( i, 3 )
allowed_radius = 0.1 + 0.9 * numaccepted / float(numv)
if pt_in_circle( x, y, allowed_radius ) :
accepted.append( (x,y) )
numaccepted += 1
i += 1
As you generate samples, you slowly grow the accepted distance from centre from 0.1 to 1.0 units.
And to generate the halton numbers, I used:
def halton(idx, base) :
result = 0
f = 1.0 / base
i = idx
while ( i > 0 ) :
result += f * ( i % base )
i = i / base
f = f / base
Which results in the follow growth animation of 200 samples that survived the rejection test. To get them, a total of 2791 samples were tested, by the way.
Because so many samples are rejected, the final result is not as nicely distributed as straight up Halton-2,3. You would get a nicer distribution by sorting the Halton samples, at the detriment of never seeing new samples in the interiour: they will always grow at the outskirts.
This is what it looks like if you generate 200 Halton samples that fall with in the unit circle, and then sort them by distance to the origin: