Help for TIECONV

PURPOSE

     TIECONV prepares a gridded dataset for POLYGEOM, GEOMA, 
     LGEOM,  MGEOM,  GEOMV or  GEOMZ  transformations. Input
     is paired sets of tiepoints with no restrictions. It is
     in principle, a surface generation routine, but creates 
     the  gridded  dataset so as to best interface with  the 
     VICAR routines above.   The sequence GEN,  TIECONV, and 
     GEOMZ can be used to generate a surface in image format 
     through an arbitrary set of points.
     TIECONV uses the finite element method  (triangulation) 
     for  surface  fitting.   It is anticipated  that  other 
     surface  fitting methods will be integrated into  VICAR 
     in  the same fashion as tieconv so that users will have 
     maximum flexibility both in terms of choice of  surface 
     fit and in terms on application.
     The triangulation method is Thiessen triangulation. The
     maximum number of points is  probably  about 1 million.
     The largest case  tried so far is 400,000 points, which
     ran in 4 hours 31 minutes on a SUN SPARCstation 20.
     
     TIECONV can be used to prepare a polynomial surface fit
     of four types.  The keyword is POLY  and  it  has  five
     values: "LINEAR","KEYSTONE","QUAD","CUBIC", (or ""  for
     triangulation).  LINEAR fits the  best plane (in the L2
     norm or least squares) through the x-distortion and the
     y-distortion.   KEYSTONE fits a  bilinear surface, QUAD
     fits a general quadratic surface and CUBIC fits  a gen-
     eral cubic surface.  The  number of  tiepoints required
     are LINEAR - 3, KEYSTONE - 4, QUAD - 6, and CUBIC - 10.
     More tiepoints  are handled  by a least squares fit.
     
     
TAE COMMAND LINE FORMAT

     tieconv OUT=B PARAMS
     tieconv PARMS=parm_file OUT=B PARAMS
     tieconv INP=tiep  OUT=B  PARAMS

     where

     parm_file           is an optional disk parameter dataset 
			   containing the input tiepoints.
     tiep		 is an optional IBIS tabular file containing
			   the input tiepoints.
     B                   is the output parameter dataset.
     PARAMS              is a standard VICAR parameter field.
OPERATION

     tieconv operates in two phases.   In phase 1, the input 
     points  are  fully  triangulated  by  a version  of the 
     Thiessen   algorithm.   This operates by  computing the
     Voronoi polygons (polygons of area  nearest each point)
     and  computing  the  triangles  formed by the bisectors
     of the  polygons.   Four extra points  are  added  five 
     diameters away from the convex hull so that the surface 
     will extend smoothly beyond the input tiepoints.

     In  phase 2,  the output grid is formed by  evaluating 
     the  triangular surface at grid point locations.   That 
     is,  a grid point will fall in some triangle,  and  the 
     GEOM  shift  will  be the linear interpolation  of  the 
     input shifts at the three corners of the triangle.  The 
     user  should  note  that  the  triangular  surface   is 
     continuous but not differentiable and it passes through 
     all  of  the input  points.   Point-surface  generation 
     routines can e compared in the following table.
|       \ PROPERTIES| CONTI-|DIFFEREN-| EVALUATES |   WELL   |
|        \    OF    | NUOUS |TIABLE   | AT INPUT  |  BEHAVE  |
| METHOD  \ SURFACE |       |         |   POINT   | NO MESAS |
|-------------------|-------|---------|-----------|----------|
| Triangulation     |  yes  |    no   |    yes    |   yes    |
|-------------------|-------|---------|-----------|----------|
|                -1 |       |         |           |          |
| Interpolation r   |   no  |    no   |    yes    |   yes    |
|-------------------|-------|---------|-----------|----------|
|                -p |       |         |           |          |
| Interpolation r   |   no  |    no   |    yes    |    no    |
|-------------------|-------|---------|-----------|----------|
| Polynomial Fit    |  yes  |    yes  |    no     |    no    |
|-------------------|-------|---------|-----------|----------|
| Linear            |  yes  |    yes  |    no     |   yes    |
|-------------------|-------|---------|-----------|----------|
| Bilin (keystone)  |  yes  |    yes  |    no     |   yes    |
|-------------------|-------|---------|-----------|----------|
| Quadratic         |  yes  |    yes  |    no     |   yes    |
|-------------------|-------|---------|-----------|----------|
| Cubic             |  yes  |    yes  |    no     |   yes    |
|-------------------|-------|---------|-----------|----------|

EXAMPLE

     tieconv OUT=B 'GEOMA NAH=44 NAV=24
           TIEPOINT=(   346       432       353      422
                        479       316       482      313
                         .
                         .
                         .
                        723       529       715      527)
     POLYGEOM INP=X PARMS=B OUT=Y

     In this example,  the tiepoints are used to set up a 44 
     x  24 grid for use by POLYGEOM.   The tiepoints can  be 
     scattered  over  the  image  in  any  fashion   whereas 
     POLYGEOM requires a regular grid.
     
     TIECONV can be used to prepare a polynomial surface fit
     of four types.  The keyword is POLY  and  it  has  five
     values: "LINEAR","KEYSTONE","QUAD","CUBIC", (or ""  for
     triangulation).  LINEAR fits the  best plane (in the L2
     norm or least squares) through the x-distortion and the
     y-distortion.   KEYSTONE fits a  bilinear surface, QUAD
     fits a general quadratic surface and CUBIC fits  a gen-
     eral cubic surface.  The  number of  tiepoints required
     are LINEAR - 3, KEYSTONE - 4, QUAD - 6, and CUBIC - 10.
     More tiepoints  are handled  by a least squares fit.
     
     
     Back to the  triangulation case, if the  input data set
     is a  grid, or  approximately  a  grid, a  shortcut  is
     applied that  speeds up  enormously.  The detection  of
     the grid is automatic.
     

     GEN OUT=X NL=1000 NS=1000 IVAL=0 LINC=0 SINC=0
     tieconv OUT=B 'GEOMZ              TIEPOINT=(
               1   1    0
               1000   1    0
               1    1000     0
               1000  1000      0
               500   500       255)
     GEOMZ INP=X PARMS=B OUT=Y

     this  example constructs a "pyramid" shaped  brightness 
     surface in the image Y.

TIMING

     Timing  is dominated by the triangulation method  which 
     is 0(n*log(n)) where n is the number of input points.  A case 
     with  10000  points  was run in 1.63 minutes  CPU  time, 
     and a case with 400,000 points was run in 4.52 hours on
     a SPARCstation 20.
     
     If the input data set is a grid, or approximately a grid,
     a shortcut is applied that speeds up enormously.  The
     detection of the grid is automatic.
     
     The polynomial fits (LINEAR, KEYSTONE, QUAD, CUBIC) are
     very fast.
     
RESTRICTIONS

   The maximum number of input tiepoints is probably about 1 million.
   This value will increase as the machines get more virtual and
   real memory since dynamic memory allocation is used throughout
   the algorithm.
   
   The maximum number of output tiepoints is limited by IBIS table
   size (currently about 10 million?).  Internal to the program,
   dynamic memory allocation is used.


WRITTEN BY:            A. L. Zobrist, 29 August 1979

COGNIZANT PROGRAMMER:  A. L. Zobrist

REVISIONS: 
  PORTED TO UNIX	C. R. Schenk (CRI)  31-Oct 1994
  ALGORITHM UPDATED     A. L. Zobrist 19-Jul 1999
  lsq update for poly   A. L. Zobrist 27-Aug 2002
Fri Jan 11 2008 wlb switched to USES_ANSI_C AND LIB_CARTO; misc cleanup  

PARAMETERS: