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