Creating closed spatial polygons

Question

I need to create a (large) set of spatial polygons for test purposes. Is there an algorithm that will create a randomly shaped polygon staying within a bounding envelope? I'm using OGC Simple stuff so a routine to create the well known text is the most useful, Language of choice is C# but it's not that important.

Answer 1

Hi

What shape is your bounding envelope ? If it's a rectangle, then generate your random polygon as a list of points within [0,1]x[0,1] and scale to the size of your rectangle.

If the envelope is not a rectangle things get a little more tricky. In this case you might get best performance simply by generating points inside the unit square and rejecting any which lie in the part of the unit square which does not scale to the bounding envelope of your choice.

HTH

Mark

Supplement

If you wanted only convex polygons you'd use one of the convex hull algorithms. Since you don't seem to want only convex polygons your suggestion of a circular sweep would work.

But you might find it simpler to sweep along a line parallel to either the x- or y-axis. Assume the x-axis.

1. Sort the points into x-order.
2. Select the leftmost (ie first) point. At the y-coordinate of this point draw an imaginary horizontal line across the unit square. Prepare to create a list of points along the boundary of the polygon above the imaginary line, and another list along the boundary below it.
3. Select the next point. Add it to the upper or lower boundary list as determined by it's y-coordinate.
4. Continue until you're out of points.

This will generate convex and non-convex polygons, but the non-convexity will be of a fairly limited form. No inlets or twists and turns.

Another Thought

To avoid edge crossings and to avoid a circular sweep after generating your random points inside the unit square you could:

1. Generate random points inside the unit circle in polar coordinates, ie (r, theta).
2. Sort the points in theta order.
3. Transform to cartesian coordinates.
4. Scale the unit circle to a bounding ellipse of your choice.

Off the top of my head, that seems to work OK

Answer 2

Do they really need to be random, or would some real WKT do? Because if it will, just go to http://koordinates.com/ and download a few layers.

Answer 3

Here you can find two examples of how to generate random convex polygons. They both are in Java, but should be easy to rewrite them to C#:

• Generate Polygon example from Sun
• from JTS mailing list, post Minimum Area bounding box by Michael Bedward

Another possible approach based on generating set of random points and employ Delaunay tessellation.

Generally, problem of generating proper random polygons is not trivial.