Delaunay Triangulation Demonstration Code
          (Guibas-Stolfi algorithm with winged edge data structure)
          =========================================================

Source code from Martin Pavlovsky, July 2008 as part of interim evaluation
in the Google Summer of Code project "Reimplementation of v.voronoi and
v.delaunay modules in the Vector library of GRASS GIS using more efficient
algorithms".

Description from the author:

Date: Sun, 13 Jul 2008 18:57:46 +0200
From: "Martin Pavlovsky" <mpavlovsky@gmail.com>
To: "Paul Kelly" <paul-grass@stjohnspoint.co.uk>
Subject: UPDATE: SVGAlib replaced with cairo, freezes are no longer present

[...]
Source code in the attachement is just the implementation of the
guibas-stolfi algorithm with winged-edge data structure, not an actual GRASS
module. I will start working on the module itself as soon as I feel that the
algorithm is robust and stable enough.

Since I understand that it is almost impossible for a human to check if a
triangulation of lets say 1000 or more sites is correct by just reading text
output of the edges of the triangulation (e.g. pairs of the form:
{edge_origin edge_destination}) I decided to use graphic library Cairo
to visualize the triangulation.

You can compile the sources using makefile included in the directory. Then
you run the executable guibas-stolfi.

The program generates the Delaunay-triangulation of N randomly generated
sites(this is just for testing and presentation purposes). After starting
the program, you are prompted to enter number of sites. After you run the
program, you can find the visual output in file "dt.png".

You may notice that triangulation for a higher number of sites (>500) are
sometimes not correct(merging of two halves is not complete occasionaly). I
am working on correcting this bug.