CGAL users discussion list

[Michael Hoffmann <>]

> Is there any way to produce a random simple polygon (confined in a
> given bounding box) w/holes, with a given complexity n?

depends on what you mean by random simple polygon. :-)

You can, for instance, pick the vertices according to your favorite
distribution and connect them,

1) along their upper convex hull and the rest in lexicographic order;

2) choosing a random permutation and successively flipping edge
   crossings;

3) by an (approximate) Minimum TSP tour (e.g., starting from an EMST
   and then remove crossings);

4) similar as in the SLR/Graham scan convex hull algorithm, except
   that you don't enforce local convexity but only that no point
   appears on both chains;

5) ... (probably many other options, depending on what you want)

hth,
Michael