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

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, 153174. 

Note: See
TracBrowser
for help on using the repository browser.