Create random polygon shapes

Question

I want to make a random shape made out of points. I want the points to create a polygon shape. Is there a clever way to create a random shape like this? Im thinking going throug X points and giving them random positions but the problem is that they shoudl never intersect and the last point should connect to the first, which they always can do but the points should be somewhat evenly spread out. Im betting there are already good algorithms for this but i lack the words to know what to look for.

Answer 1

Just winging it, here's two possible approaches...

Constructively

Build in such a way that lines cannot intersect. For example, take points spaced evenly alone a circle, and then randomize their radii. Could also randomize their angular position, within their pie wedge.

This won't make all possible polygons, the ones it makes will be non-self-intersecting.

Test & Reject

You could pick a set of ordered random points within the size you want, and then test if the polygon they form is suitable (in your case, non-self-intersecting), and if it passes, keep it. Else, try again.

A similar approach would be to start with 3 non collinear points, which must be a triangle. Then add a random fourth point. If it causes an intersection, reject it and try a different one. Repeat for as many vertices as you want, maybe a random number.

Answer 2

Some more options to consider:

Convex Polygons:

If you're OK generating only convex polygons, a fairly painless approach is to generate some number of random points and find the convex hull. Example (by Mike Bostock) here:

http://bl.ocks.org/mbostock/4341699

(Fairly easy to intuit that the fewer points you generate, the less "rounded" the hull will be.)

Concave Polygons:

If instead you want to allow concave polygons, it depends a lot on what kind of shapes you have in mind.

E.g., you could take a convex hull and cut out triangles to make it concave, like so:

1. Generate set of random points S
2. Calculate convex hull H
3. Calculate set of remaining points R, R=S-H

4. Until "concave enough" (however you want to define that)

   • Select a pair of adjacent vertices A and B from the H
   • Select a random point C from R
   • Check whether the triangle formed by A, B, and C overlaps any previous triangles.

   • If not,

     • Record the triangle
     • Insert C between A and B

The "record the triangle / compare against previous triangles" bit is just to prevent self-intersecting polygons.

(This might be a little more complex, bookkeeping-wise, than david van brink's answer.)

Of course you could cut quads (or higher) instead of triangles. All depends on the look you've got in mind.

---

Edit: Wanted to clarify that I did not implement the lovely example from bl.ocks.org, in case it wasn't obvious. Credit goes to (the very talented) Mike Bostock.

Answer 3

This is a graph theory problem to determine the outerplanar graph from a random set of vertices. Professors Manuel Bodirsky and Mihyuan Kang of Humboldt University of Berlin considered this question in, Generating outerplanar graphs uniformly at random, 2006. Their work is made available to the public by researchgate here: link to PDF