The spg (simple polygon generator) code constructs a simple polygon P on a given point set S in the plane. Initially, spg creates a (not necessarily simple) polygon by choosing a random perturbation of the input vertices. Then it performs a series of line sweeps to find intersections and resolves these using two-opt moves.
The implementation is being developed as part of a master thesis by Steinþór Jasonarson. Source code is available on github.
See the spg* directories in /db/wip/polygons/random/ for polygons.
There are two variants (see the paper, link pending):
a) After a two-opt move is carried out, we simply continue with the line-sweep. When we arrived at the last vertex we repeat the line-sweep until all intersections are resolved. b) After a two-opt move, we reverse the line-sweep, possibly observing new edge intersections. We restart our (forward) line-sweep at the smallest vertex affected by the two-opt move.
spg-a-poly_0000040_1