v.geom(1)		      Grass User's Manual		     v.geom(1)



NNAAMMEE
       _v_._g_e_o_m	- 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	dimen-
       sions.

SSYYNNOOPPSSIISS
       vv..ggeeoomm
       vv..ggeeoomm hheellpp
       vv..ggeeoomm iinnppuutt==_n_a_m_e oouuttppuutt==_n_a_m_e [pprreecciissiioonn==_v_a_l_u_e] [ooppeerraattiioonn==_n_a_m_e]

DDEESSCCRRIIPPTTIIOONN
       _v_._g_e_o_m 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, oth-
       erwise 0 is assumed. The z-coordinate is used for the MinMax-slope tri-
       angulation.  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 Min-
       Max-slope triangulations are similar.  The algorithms used for the com-
       putations are not heuristics, they actually achieve the optimum.


       We use a simple extension of the algorithm used to compute the Delaunay
       triangulation in _s_._g_e_o_m to compute a triangulation which can be consid-
       ered  an approximatoin of the constrained Delaunay triangulation.  How-
       ever, 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.

OOPPTTIIOONNSS
   PPaarraammeetteerrss::
       iinnppuutt==_n_a_m_e
	      Input vector (level 2) file.

       oouuttppuutt==_n_a_m_e
	      Output vector file.

       pprreecciissiioonn==_v_a_l_u_e
	      Number   of  significant	positions  after  the  decimal	point.
	      (default is 0).

       ooppeerraattiioonn==_n_a_m_e
	      One of the following: _s_w_e_e_p,  _d_e_l_a_u_n_a_y,  _a_n_g_l_e,  _h_e_i_g_h_t,	_s_l_o_p_e,
	      _h_u_l_l.  These correspond to the constrained planesweep triangula-
	      tion, constrained Delaunay heuristic,  constrained  MinMax-angle
	      triangulation,  constrained  MaxMin-height  triangulation,  con-
	      strained MinMax-slope triangulation, and	convex	hull,  respec-
	      tively.  (default is constrained planesweep triangulation).


NNOOTTEE
       The  computation  times	for the various operations depends strongly on
       the algorithm used.


       The plansweep triangulation and convex hull computation require _O_(_n _l_o_g
       _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 prac-
       tice.  The MinMax-angle and MaxMin-height triangulations need _O_(_n_^_2 _l_o_g
       _n_) operations [EdTa], and the MinMax-slope triangulation  needs	_O_(_n_^_3_)
       operations [BeEd].


       Internally,  the  coordinates of the sites are stored in fix-point for-
       mat.  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_._g_e_o_m 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.   Cur-
       rently,	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_._s_p_a_g.

BBUUGGSS
       Some fields of the header in the output file are not properly set.

RREEFFEERREENNCCEESS
       [BeEd]  M.Bern,	H.  Edelsbrunner,  D.  Eppstein, S. Mitchel, T.S. Tan.
       Edge Insertion for Optimal Triangulations.  _I_n _P_r_o_c_. _1_s_t _L_a_t_i_n _A_m_e_r_i_c_a_n
       _S_y_m_p_o_s_. _T_h_e_o_r_e_t_.  _I_n_f_o_r_m_a_t_i_c_s _1_9_9_2, 46--60.


       [Ed]  H. Edelsbrunner.  _A_l_g_o_r_i_t_h_m_s _i_n _C_o_m_b_i_n_a_t_o_r_i_a_l _G_e_o_m_e_t_r_y_. Springer-
       Verlag, Heidelberg, Germany, 1987.


       [EdSh] H. Edelsbrunner, N. R. Shah.   Incremental  Flipping  Works  for
       Regular	Triangulations.  _I_n _P_r_o_c_. _8_t_h _A_n_n_. _S_y_m_p_o_s_. _C_o_m_p_u_t_. _G_e_o_m_. _1_9_9_2,
       43-52.


       [EdTa] H. Edelsbrunner, T.S. Tan and R. Waupotitsch.  An O(n^2  log  n)
       Time  Algorithm	for  the  MinMax  Angle  Triangulation.   _S_I_A_M _J_. _S_c_i_.
       _S_t_a_t_i_s_t_. _C_o_m_p_u_t_. _1_3 _1_9_9_2, 994-1008.

SSEEEE AALLSSOO
       _s_._g_e_o_m

AAUUTTHHOORR
       Roman Waupotitsch

       _L_a_s_t _c_h_a_n_g_e_d_: _$_D_a_t_e_: _2_0_0_2_/_0_1_/_2_5 _0_5_:_4_5_:_3_5 _$



GRASS 5.0							     v.geom(1)
