NAME
s.geom - Computes Delaunay triangulation,
MinMax-Angle triangulation, MinMax-Slope triangulation,
MaxMin-Height triangulation, Regular triangulation,
planesweep triangulation, Voronoi diagram, and convex hull
of sites in 2 and 2 1/2 dimensions.
SYNOPSIS
s.geom
s.geom help
s.geom input=name output=name
[precision=value] [operation=name]
DESCRIPTION
s.geom takes a sites file as input and computes
various triangulations, the Voronoi diagram, or the convex
hull of the sites. The z-coordinate is read from the
description field if it is specified, otherwise 0 is
assumed. The z-coordinate is used for the MinMax-slope
triangulation and for the regular triangulation (where it
is interpreted as the weight of the site). For all other
computations the z-coordinate is ignored.
The MinMax-angle triangulation is the triangulation for the
sites which minmizes (lexicographically) the sorted vector
of all the angles of triangles in the triangulation. The
MaxMin-height and MinMax-slope triangulations are similar.
The algorithms used for the computations are not
heuristics, they actually achieve the optimum.
The regular triangulation is the weighted version of the
delaunay triangulation (weights are assigned to the sites,
the delaunay triangulation corresponds to the regular
triangulation where all the sites have identical weights).
The output is saved in vector file format.
OPTIONS
Parameters:
- input=name
- Input vector (level 2) file.
- output=name
- Output vector file.
- precision=value
- Number of significant positions after the decimal point. (default is 0).
- operation=name
- One of the following: sweep,
delaunay, angle, height,
slope, hull. These correspond to the
planesweep triangulation, Delaunay triangulation,
MinMax-angle triangulation, MaxMin-height triangulation,
MinMax-slope triangulation, regular triangulation, Voronoi
diagram, and convex hull, respectively. (default is
Delaunay triangulation).
NOTE
Only the sites which fall into the current region are used
for the computations.
The computation times for the various operations depends
strongly on the algorithm used.
The plansweep triangulation and convex hull computation
require O(n log n) operations in the worst case
[Ed]. The Delaunay heuristic needs
O(n^2) time in the worst case, however it performs
much faster in practice. The MinMax-angle and MaxMin-height
triangulations need O(n^2 log n) operations
[BeEd, EdTa], and the
MinMax-slope triangulation needs O(n^3) operations
[BeEd].
Internally, the coordinates of the sites are stored in
fix-point format. Therefore, the number of decimal digits
cannot exceed 64 bit (or apprx. 16 decimal digits).
BUGS
Some fields of the header in the output file are not properly set.
REFERENCES
[BeEd]
M.Bern, H. Edelsbrunner, D. Eppstein, S. Mitchel,
T.S. Tan. Edge Insertion for Optimal Triangulations.
In Proc. 1st Latin American Sympos. Theoret.
Informatics 1992, 46--60.
[Ed]
H. Edelsbrunner. Algorithms in Combinatorial
Geometry. Springer-Verlag, Heidelberg, Germany, 1987.
[EdSh]
H. Edelsbrunner, N. R. Shah.
Incremental Flipping Works for Regular Triangulations.
In Proc. 8th Ann. Sympos. Comput. Geom. 1992, 43-52.
[EdTa]
H. Edelsbrunner, T.S. Tan and R. Waupotitsch.
An O(n^2 log n) Time Algorithm for the MinMax Angle Triangulation.
SIAM J. Sci. Statist. Comput. 13 1992, 994-1008.
SEE ALSO
v.geom
AUTHOR
Roman Waupotitsch