# How can I create random concave polygons for test purposes?

In the context of generating random test data using QGIS (in a shapefile):

I can generate random, continuous (adjacent) polygons by first creating n random points using ftools and then generating a Voronoi diagram from those. Using this technique I get n convex polygons within some extent. Additionally, I know that all the polygons are contiguous and it is possible to build an adjacency matrix.

Is it possible to generate random convex and concave polygons that are (1) bounded by some defined extent and (2) continuous?

My initial thought is to generate n x 3 polygons and then begin randomly merging them (using a Python script) until only n remain. This should generate at least a few convex polygons.

Does QGIS (or GRASS) offer a means to do this? How about an external package?

Edited for @whuber's comment:

1. It is possible to trace a path from any polygon to any other polygon without exiting a polygon in the set, e.g. the contiguous U.S. Adding the Hawaii multipolygon would fail the contiguity test because one has to exit California (for example), enter unbounded planar space, and then re-enter the polygon set.

2. The probability distribution of the random points is not important, in that, the density of polygons generated from the randomly distributed points does not matter. The goal is simply to vary the number of neighbors each polygon has - the distribution of the neighbor cardinality is not important, but it should not be equal across all polygons as with a regular lattice.

3. This is a test of regionalization algorithms using randomly generated data These tests have used lattices and Voronoi diagrams. I want to explore a particular algorithm on test data using convex and concave polygons. The generation of convex polygons that meet my constraints is handled using the technique I describe above.

Thanks!

• (1) What do you mean by "continuous"? (2) "Random" implies some probability distribution. What distribution do you have in mind? You probably do not know--it would be very hard to derive distributions for arbitrary concave polygons--so instead it would help to understand why you want to generate these polygons randomly. What are you testing? – whuber Oct 26 '13 at 15:49
• Thanks: apparently "continuous" means "contiguous" and that's now clear. Given that your concern seems primarily about varying the number of adjacent neighbors, could you share some ideas about why testing a "regionalization algorithm" with concave polygons would be important? At any rate, there are simple ad hoc solutions but I wonder whether they would meet your needs. For instance, take a set of Voronoi polygons and slightly perturb the common edges (without changing their endpoints): that guarantees concavity on at least one side of each. – whuber Oct 26 '13 at 22:13
• @whuber A sample dataset consisting of just convex polygons does not simulate the convex / concave reality that one sees in applications such as congressional redistricting - this discount multipart polygons and islands (in the sense that the unit has not neighbor, not just in the case of a physical island). Additionally, a generated dataset provides the means for a priori knowledge of the optimal solution. Can you suggest any references to the perturbation method? It sounds as if this will simply introduce slivers at common edges (fixed endpoints with each edge defined by only two points). – Jay Laura Oct 26 '13 at 22:53
• You seem to be thinking of datasets that are maintained without "topology," where common edges are represented twice. With topology they are represented once, limiting the possibility of slivers or other problems when they are modified. But, as I was trying to say, a good approach will be one that is suited to stress the aspects of your algorithm you wish to test. Without knowing the nature of this algorithm it is difficult to recommend any particular one of the very, very many possible approaches that are available. – whuber Oct 26 '13 at 23:06
• @whuber Edited the question to assume a shapefile - so topology is not recorded within the dataset. Do you have a reference to any of the many approaches available with the context of either QGIS or GRASS? Clearly, I can densify my polygons(as topology is not stored) and write custom code to perform alterations in my polygons such that some number of them are concave. This would be in addition to the technique I offered in the question. My goal is to avoid writing such code and leverage some built-in functionality. – Jay Laura Oct 27 '13 at 3:04