spg - Combining Line-Sweep and Two-Opt

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.

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.
• c) 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.