## NAME

v.geom - Computes constrained MinMax-Angle triangulation, constrained MinMax-Slope triangulation, constrained MaxMin-Height triangulation, constrained planesweep triangulation, constrained delaunay heuristic, and convex hull of sites and prescribed edges in 2 and 2 1/2 dimensions.

## SYNOPSIS

v.geom
v.geom help
v.geom input=name output=name [precision=value] [operation=name]

## DESCRIPTION

v.geom takes a vector file as input and computes various triangulations respecting the input edges, 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. 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 constrained version also minimizes this vector but under the constrained that prescribed (i.e. input) edges are part of the final triangulation. The MaxMin-height and MinMax-slope triangulations are similar. The algorithms used for the computations are not heuristics, they actually achieve the optimum.

We use a simple extension of the algorithm used to compute the Delaunay triangulation in s.geom to compute a triangulation which can be considered an approximatoin of the constrained Delaunay triangulation. However, this is only a (bad?) heuristic.

The output is saved in vector file format. Edge labels of input edges will also be attached to the corresponding output edges.

## 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 constrained planesweep triangulation, constrained Delaunay heuristic, constrained MinMax-angle triangulation, constrained MaxMin-height triangulation, constrained MinMax-slope triangulation, and convex hull, respectively. (default is constrained planesweep triangulation).

## NOTE

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 approx. 16 decimal digits).

It is important that the input vector file is reasonably "clean". The current implementation of v.geom takes care of loops (i.e. zero length edges), duplicate edges, and edges which are collinear and overlapping. However, because of the internal representation of coordinates in fix-point format it can happen that certain anomalies are introduced. For examples edges can cross although they don't in the input data. Currently, the program does not test for such cases. If it occures one of two situations will happen. Either, the planesweep algorithm terminates with a segmentation fault, or it will loop forever. For the data where we had problems these problems could be eliminated if we first used v.spag.

## 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

s.geom

## AUTHOR

Roman Waupotitsch

Last changed: $Date: 2002/01/25 05:45:35 $