Generating random "roughly circular" polygons

Question

I am trying to generate a set of points distributed in such a way as to give a "rough circle" sort of shape. The points should not deviate too far from neighboring points, with larger jumps being rarer, though the radius can gradually deviate from whatever the starting mean radius was. The angular seperation of the points are equally distributed, but the number of points can vary.

My first strategy was to do a random walk around the circle, with the next point having a radius that's different by a normally-distributed random number. The problem is once we get to the last point, it will more often than not have a big discontinuity with the first point, larger than what we would expect from the normal variation in neighboring points.

Now I don't need the last point to be exactly the same as the first, but I would like an approach that has the first and the last points to be as near as we would expect any other two adjacent points to be. Is there some way to pick random points in such a way, so that a random walk "returns to its starting position" so to speak?

For context, the use case is the creation of objects in an Asteroids (the arcade game) sort of style. Those asteroids simply used a uniformly distributed random radius for each point in the polygon, but that produces objects more jaggedy than what I would like, and lead to more visually spherical objects as you add more points. But my polygons still have few enough points where a full application of Perlin noise or some other fractal method would be overkill I would think.

Answer 1

Using radius perturbance (as per the question)

This is a matter of combining different frequencies of noise. Let's ignore fine perturbations for now and look at the basis first, which as you state, needs to match around t == 0.0, and let's consider the problem by "unrolling" the circumference of your circle into a straight line.

A simple way to solve this is using a sine or cosine wave, which repeat endlessly and seamlessly, having always the same value at 0 and 2*pi radians. You can thus create a (co)sine wave with a large amplitude, say 10.0, and then randomly perturb each point by a much smaller magnitude, say 2.0. You can combine just 2 waveforms, or many waveforms of differing frequencies and amplitudes (like Perlin Noise).

const amplitudeLarge = 10.0;
const amplitudeSmall = 2.0;


float calcPerturbedRadius(theta, amplitudeLarge, amplitudeSmall)
{
    return amplitudeLarge * sin(theta)
         + amplitudeSmall * sin(theta);
}

for (let i = 0; i < radiusPointsCount; i++)
{
    let frac = i / radiusPointsCount;
    let theta = frac * (pi * 2);
    pointsRadii[i] = calcPerturbedRadius(theta, amplitudeLarge, amplitudeSmall);

    //render etc.
}

By combining multiple large waveforms (say 2 that are both using amplitudeLarge) you can create a more interesting "coarse" basis upon which you will apply your "fine" (per point) adjustments. A cursory web search for "combining sine waves" will give you more insight into this.

Alternative 1: Diffusion clouds

For context, the use case is the creation of objects in an Asteroids (the arcade game) sort of style. Those asteroids simply used a uniformly distributed random radius for each point in the polygon, but that produces objects more jaggedy than what I would like, and lead to more visually spherical objects as you add more points. But my polygons still have few enough points where a full application of Perlin noise or some other fractal method would be overkill I would think. Any ideas would be appreciated, thanks.

There's another way to achieve smooth, organic outlines, using image processing instead of radius perturbation: Using a small image / grid of NxN, where N is your maximum height / width of your asteroid form, plot a few points at random between 0..N-1 in each axis, setting these to some maximum value (255, 1024, or what have you). Then run multiple diffusion passes over this grayscale "image" (2D array), passing dc = 0.2 initially:

function diffuse(mapOld, mapNew, width, dc)
{
    mapNew.set(mapOld);
    
    let px = 0, py = 0, nx = 0, ny = 0; //integers
    for (let y = 0; y < width; y++)
    {
        py = y - 1; if (py < 0)      py = py + width;
        ny = y + 1; if (ny >= width) ny = ny - width;
        
        for (let x = 0; x < width; x++)
        {
            px = x - 1; if (px < 0)      px = px + width;
            nx = x + 1; if (nx >= width) nx = nx - width;
            
            mapNew[y * width + x] = dc * 
                (
                mapOld[ y * width + x] + //centre
                mapNew[py * width + x] + //east
                mapNew[ny * width + x] + //west
                mapNew[ y * width + px] + //north (or south)
                mapNew[ y * width + nx]   //south (or north)
                );
        }
    }
    
    mapOld.set(mapNew);
}

const numPasses = 10;
const dc = 0.2;

for (let p = 0; p < numPasses; p++)
{
    diffuse(mapOld, mapNew, N, dc)
}

On every step, the randomly-plotted cells diffuse into neighbouring cells. This has the effect of softening outlines, like a cloud. Points plotted near each other will gradually merge together in a cloud-like form.

Finally, any cells with values greater than 0.0 are clamped to 1.0, anything else is left as zero. This should give you a binary (black/white) image with fairly rounded outlines.

Play with dc and numPasses to get the effect you need. You may also need to create a large grid and only randomly plot nearer to the centre. You may also need to play with the resolution to get the smoothness you want for your asteroids.

You could then also extract the edges into a series of points, if you prefer working in vector format rather than with bitmaps.

Alternative 2: Metaballs

Another alternative for organic outlines is 2D metaballs. There are tons of sources and implementations across the web, so I will not go into detail here.

Answer 2

Say you needed to generate 19 points, the first 10 points could be generated from the random function of your choice.

• Point 11 would be 90% random and 10% of the value of point 9
• Point 12 would be 80% random and 20% of the value of point 8
• ...
• Point 19 would be 10% random and 90% of the value of point 1

I.e. you are lerp()ing with earlier points as you get closer to closing the polygon. The problem with this strategy is the first/last few points may look symmetrical, so you may need to tinker with how many points you use / the lerp factor, to balance out getting the points close verses looking too symmetric.