CGAL users discussion list

["Amir Vaxman" <>]

Yes, there are many methods (for instance, making a voronoi diagram, and
connect every site to two neighbors, and keeping consistent orientation). I
just wanted to know if there is a ready tool for this.

Amir.

-----Original Message-----
From: Michael Hoffmann 
[mailto:]
 
Sent: Wednesday, February 04, 2009 12:35 PM
To: 

Subject: Re: [cgal-discuss] Random Polygon Generator

> 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
-- 
You are currently subscribed to cgal-discuss.
To unsubscribe or access the archives, go to
https://lists-sop.inria.fr/wws/info/cgal-discuss