# Generate a Random Polygon

Does some package exist with a function that takes a parameter $n$ and generates a random 2D $n$-sided simple polygon (convex or non-convex), possibly within a certain bounding box?

It does not suffice to simply generate $n$ random points as I would have to figure out how to connect the points in a non-intersecting manner. I am sure there are algorithms to solve this particular problem, but I would much rather use a ready-made function that would be guaranteed to work, rather than code my own function and introduce more bugs.

I am trying to generate a large number of "random" test cases for my algorithm that is supposed to work for all polygons.

-
Without more information I'd put my money on RandomReal or similar. Please add as much info as possible and any relevant code you already have in place. –  Yves Klett Sep 21 '13 at 6:42
as @YvesKlett said, maybe: Graphics@Polygon[RandomReal[{5, 10}, {RandomInteger[{2, 10}], 2}]] or similar? –  Pinguin Dirk Sep 21 '13 at 6:51
Generating a random cyclic graph - which is the limit of what RandomReal or RandomInteger can do - might yield a self-intersecting polygon, which I wish to avoid. I have elaborated on that in my edit to the question. –  Herng Yi Sep 21 '13 at 7:13
Can it have concave angles? –  Vitaliy Kaurov Sep 21 '13 at 7:13
Yes, that is allowed, and desired. The question did not exclude such a possibility, and "randomness" would definitely produce some concave angles, but let me edit this into the question just to be safe. –  Herng Yi Sep 21 '13 at 7:18

There is some undocumented functionality in GraphicsMesh that may help.

• SimplePolygonPartition will break apart a self-intersecting polygon into non-self-intersecting components (the components include the "holes" in the original)
• PolygonCombine will merge those components into a single polygon (note that while free of interior holes this polygon may still intersect itself)
• FindIntersections will find any self-intersections and can therefore be used to filter out such polygons

.

GraphicsMeshMeshInit[];

randompoly := Module[{poly},
While[Length[FindIntersections[
poly = PolygonCombine @ SimplePolygonPartition @
Polygon[RandomReal[{-1, 1}, {25, 2}]]]] > 0];
poly]

Graphics[{EdgeForm[Red], Yellow, randompoly}]


There are also some built-in polygons which may be useful for testing. They are:

PolygonData[]
(* {"Blob", "ChvatalComb", "FractalCross", "HeptaSpiral", "HexaSpiral",
"LSystem01", "PentaSpiral", "RandomWalk", "Test01", "TriSpiral"} *)


The available properties are:

PolygonData["Properties"]
(* {"Data", "Graphics", "GraphicsLine", "GraphicsPoint",
"GraphicsPolygon", "Line", "MeshObject", "Point", "Polygon"} *)


For example

polys = PolygonData[#, "Polygon"] & /@ PolygonData[];
Graphics[{EdgeForm[Red], Yellow, #}, ImageSize -> 100] & /@ polys


-
I have tested your code and it works, but the output of randompoly is not a list poly = {pt1, ..., ptn} of 2D coordinates, but a graphics primitive Polygon[poly]. This hinders manipulation of the output polygon, unless there is a way to "unwrap" the raw data from Polygon? –  Herng Yi Sep 22 '13 at 3:08
the output polygons of randompoly also seem to have a "fat center" as compared to the output of @ybeltukov's answer. But I see this as a minor issue. –  Herng Yi Sep 22 '13 at 3:47
@HerngYi you can extract the coordinates using List @@ randompoly –  E.O. Sep 22 '13 at 4:23
Sorry but I couldn't find the documentation on the @@ operator - does it do something like replacing the header of an expression? Would be great if you could link me to some documentation on this. –  Herng Yi Sep 22 '13 at 5:21
@HerngYi Yes, that's exactly what it does. You can select @@ in the Front End and press F1 key to bring up the page for Apply. You could also use this reference to find the same page. –  Mr.Wizard Sep 22 '13 at 7:43

I propose "deintersection" algorithm.

Let we have $n$ random points.

n = 10;
p = RandomReal[1.0, {n, 2}];


We want change the order of this points to get rid of the intersections.

Line segments $(p_1,p_2)$ and $(p_3,p_4)$ intersect if and only if the signs of areas of triangles $p_1p_2p_3$ and $p_1p_2p_4$ are different and the signs of areas of triangles $p_3p_4p_1$ and $p_3p_4p_1$ are also different.

Corresponding function

SignedArea[p1_, p2_, p3_] :=
0.5 (#1[[2]] #2[[1]] - #1[[1]] #2[[2]]) &[p2 - p1, p3 - p1];
IntersectionQ[p1_, p2_, p3_, p4_] :=
SignedArea[p1, p2, p3] SignedArea[p1, p2, p4] < 0 &&
SignedArea[p3, p4, p1] SignedArea[p3, p4, p2] < 0;


Main step

Patterns in Mathematica are very convenient for the searching and removing intersections.

Deintersect[p_] :=
Append[p, p[[1]]] //.
{s1___, p1_, p2_, s2___, p3_, p4_, s3___} /; IntersectionQ[p1, p2, p3, p4] :>
({s1, p1, p3, Sequence @@ Reverse@{s2}, p2, p4, s3}) // Most;


To add the segment between the last and the first point I use Append and Most.

As a result we got the polygon without intersections

p2 = Deintersect[p];
Graphics[{Lighter@Red, EdgeForm@Thickness[0.01], EdgeForm@Red,
Polygon[p2]}]


And many other funny polygons

Graphics[{Lighter@Red, EdgeForm@Thickness[0.01], EdgeForm@Red,
Polygon[#]}, ImageSize -> 100] &@Deintersect[#] & /@ RandomReal[1.0, {10, n, 2}]


As you can see, this algorithm can give more complicated polygons than in other answers.

-
This is the same idea I had after reading the question but I wasn't sure how to go about it. Good thing you're here to implement it for us. :-) +1 –  Mr.Wizard Sep 22 '13 at 7:45
I like the elegance of the implementation using patterns, and the assortment of generated polygons seems more random than that of the other answers, but I was looking for a ready-made function, not a new algorithm. I think that others who ask the same question will be looking for ready-made functions as well, so I did not accept this answer. I will use both this answer and that of @SimonWoods' in my testing, though. –  Herng Yi Sep 22 '13 at 10:41

======= update ===========

I guess a general method (to get elongated polygons too) would be to sample elliptic shapes of various axis ratios at a few points and then perturb them outwards (inflate) randomly.

ngon[n_, s_, r_] :=
Polygon[RandomReal[r, n] Table[{s Cos[2 Pi k/n], Sin[2 Pi k/n]/s}, {k, n}]]

Table[ngon[RandomInteger[{7, 13}], RandomInteger[{1, 3}],
RandomReal[{1, 2}]] // Graphics, {5}, {5}] // GraphicsGrid


======= older ===========

Maybe this post is useful to read - there is some sorting points discussion:

Character edge finding

Another idea that does it in a simple way is a perturbative approach. Start from a regular polygon and randomly perturb the vertices. Note it will keep polygons within some bounding box defined by regular polygon side and max perturbation amplitude.

For positive-negative perturbations smaller than some number self-intersections will be impossible. For another positive only perturbations and a different "smaller than number" you will have only convex polygons. The value of these "smaller than numbers" can be found from geometric considerations that I leave to you.

For arbitrary concave and convex shapes define:

ngon[n_, r_] :=
Polygon[Table[RandomReal[{-r, r}, 2] + {Cos[2 Pi k/n], Sin[2 Pi k/n]}, {k, n}]]

Table[Graphics[ngon[RandomInteger[{3, 9}],
RandomReal[{.3, .7}]]], {5}, {5}] // GraphicsGrid


Here is the limiting case of perturbing a line:

n = 7; pts = Table[k/n, {k, -n/2, n/2}];

Table[Join[{RandomReal[{1.1, 1.5}] #, RandomReal[{0, .2}]} & /@
pts, {RandomReal[{1.1, 1.5}] #, RandomReal[{0, -.2}]} & /@ pts //
Reverse] // Polygon // Graphics, {5}, {5}] // GraphicsGrid


For shapes only convex (with another "less than" parameter):

ngon[n_, r_] :=
Polygon[Table[RandomReal[r, 2] + {Cos[2 Pi k/n], Sin[2 Pi k/n]}, {k, n}]]

Table[Graphics[ngon[RandomInteger[{3, 9}],
RandomReal[{.3, .4}]]], {5}, {5}] // GraphicsGrid
`

-
Perturbation under a small displacement limit will not be able to produce "thin" polygons such as slightly thickened graphs. I need to test my algorithms on those kinds of polygons as well. –  Herng Yi Sep 21 '13 at 8:55
@HerngYi those can be simulated by perturbing an infinitely thin loop (line) with random shifts outwards from geometrical center. –  Vitaliy Kaurov Sep 21 '13 at 9:06
@HerngYi I modified the method to get all types. See update. –  Vitaliy Kaurov Sep 21 '13 at 9:48
This is still a rather limited variety - You may be able to produce "thickened lines" but not a general "thickened tree", for example. –  Herng Yi Sep 21 '13 at 10:10