source: trunk/src2/voronoi/Doc @ 1016

Last change on this file since 1016 was 666, checked in by mmc, 17 years ago

Added voronoi code, which is currently used by the nanovis server
to generate triangular meshes for point clouds.

File size: 1.0 KB
1voronoi - compute Voronoi diagram or Delaunay triangulation
3        voronoi [-s -t] <pointfile >outputfile
5Voronoi reads the standard input for a set of points in the plane and writes either
6the Voronoi diagram or the Delaunay triangulation to the standard output.
7Each input line should consist of two real numbers, separated by white space.
9If option
10        -t
11is present, the Delaunay triangulation is produced.
12Each output line is a triple
13        i j k
14which are the indices of the three points in a Delaunay triangle. Points are
15numbered starting at 0. If this option is not present, the
16Voronoi diagram is produced.  There are four output record types.
17        s a b
18indicates that an input point at coordinates
19        l a b c
20indicates a line with equation ax + by = c.
21        v a b
22indicates a vertex at  a b.
23        e l v1 v2
24indicates a Voronoi segment which is a subsegment of line number l;
25with endpoints numbered v1 and v2.  If v1 or v2 is -1, the line
26extends to infinity.
29Steve J. Fortune (1987) A Sweepline Algorithm for Voronoi Diagrams,
30Algorithmica 2, 153-174.
Note: See TracBrowser for help on using the repository browser.