GEOMPACK3 - 2D, 3D and KD Computational Geometry

GEOMPACK3 is a set of routines for certain computational geometry problems. In particular, it can compute the Voronoi diagram, and the Delaunay triangulation, of a set of points in the plane.

Author:

Barry Joe,
Department of Computing Science,
University of Alberta,
Edmonton, Alberta, Canada T6G 2H1
Phone: (403) 492-5757
Email: barry@cs.ualberta.ca

Files you may copy include:

• geompack3.f90, the source code.
• geompack3_prb.f90, a sample problem.
• geompack3_prb.out, sample problem output.

Error codes: Error codes IERR from 1 to 99 indicate not enough space in some array. Error codes IERR >= 100 mean that the input specification is incorrect, there is a program bug, or the tolerance TOL is too small or large (try calling INITCB with a different TOLIN value).

IERR     DESCRIPTION OF ERROR
   1  -  not enough space in EDGE array for routine EDGHT
   2  -  not enough space in HOLV array for routine DSMCPR or DSPGDC
   3  -  not enough space in 2-D VCL array
   4  -  not enough space in HVL array
   5  -  not enough space in PVL, IANG arrays
   6  -  not enough space in IWK array
   7  -  not enough space in WK array
   8  -  not enough space in STACK array for routine SWAPEC, DTRIS2, or DTRIW2
   9  -  not enough space in TIL array
  10  -  not enough space in CWALK array for routine INTTRI
  11  -  not enough space in FC array for 3-D
  12  -  not enough space in BF array for 3-D
  13  -  not enough space in SVCL, SFVL arrays for routine SHRNK3
  14  -  not enough space in 3-D VCL array
  15  -  not enough space in FVL, EANG arrays for polyhedral decomposition
  16  -  not enough space in FACEP, NRML arrays
  17  -  not enough space in PFL array
  18  -  not enough space in HFL array
  19  -  not enough space in BTL array
  20  -  not enough space in VM array
  21  -  not enough space in HT array
  22  -  not enough space in FC array for K-D
  23  -  not enough space in BF array for K-D
 100  -  higher primes need to be added to routine PRIME
 200  -  abnormal return in routine DIAM2
 201  -  abnormal return in routine WIDTH2
 202  -  parallel lines in routine SHRNK2
 205  -  horizontal ray to right does not intersect polygon in routine ROTIPG
 206  -  out-of-range index when popping points from stack in routine VPRGHT
 207  -  out-of-range index when scanning vertices in routine VPSCNA
 208  -  out-of-range index when scanning vertices in routine VPSCNB
 209  -  out-of-range index when scanning vertices in routine VPSCNC
 210  -  out-of-range index when scanning vertices in routine VPSCND
 212  -  singular matrix in routine VORNBR
 215  -  unmatched separator interface edge determined by routine DSPGDC
 216  -  all edges of an outer boundary curve are specified as hole
	 edges in input to routine DSPGDC
 218  -  cannot find subregion above top vertex of hole in routine JNHOLE
 219  -  angle at hole vertex in modified region is too far from PI due
	 to use of relative tolerance in routine JNHOLE
 222  -  separator not found in routine MFDEC2 (not likely to occur if
	 ANGSPC <= 30 degrees and ANGTOL <= 20 degrees)
 224  -  2 vertices with identical coordinates (in floating point arithmetic)
	 detected in routine DTRIS2 or DTRIW2
 225  -  all vertices input to DTRIS2 or DTRIW2 are collinear (in fl pt arith)
 226  -  cycle detected in walk by routine WALKT2
 230  -  invalid (CW-oriented) triangle created in routine TMERGE
 231  -  unsuccessful search in routine FNDTRI
 300  -  unsuccessful search by routine HTSRC
 301  -  degenerate tetrahedron detected by routine BARYTH, CCSPH, or OPSIDE
 302  -  2 vertices with identical coordinates (in floating point arithmetic)
	 detected in routine FRSTET, DTRIS3, DTRIW3, or ITRIS3
 303  -  all vertices input to DTRIS3 or DTRIW3 are collinear (in fl pt arith)
 304  -  all vertices input to DTRIS3 or DTRIW3 are coplanar (in fl pt arith)
 305  -  invalid configuration (due to tolerance) detected by routine SWAPES
 306  -  no visible boundary face found in routine DTRIS3 or ITRIS3
 307  -  cycle detected in walk by routine WALKT3
 308  -  nontransformable or nonexistent face at top of stack in routine SWAPTF
 309  -  ALPHA(4) = 0 occurs after calling BARYTH in SWAPES, SWAPMU, etc.;
	 TOL must be decreased
 310  -  unmatched edge determined by routine DSCPH
 313  -  incorrect value for variable T in routine XPGHPL
 314  -  unmatched edge in shrunken polyhedron in routine SHRNK3
 315  -  2 "identical" vertices with unequal coordinates in routine SHRNK3
 318  -  vertex ITOP not found in FVL array in routine INTMVG
 321  -  face oriented same way twice in routine DSPHDC or DSPHFH
 322  -  unmatched edge determined by routine DSPHDC, DSPHFH, or DSPHIH
 325  -  unsuccessful search for next edge of cut polygon in routine CUTFAC
 326  -  unsuccessful search for intersecting edge of face FL in CUTFAC
 327  -  at least one reflex edge has not been resolved by routine RESEDG
 328  -  value of constant MAXEV must be increased in routine CUTFAC
 330  -  value of MAXSV must be increased before calling SHRNK3 in TRIPR3
 331  -  invalid vertex detected from walk or linear search in routine BCDTRI
 334  -  unsuccessful search for next edge of cut polygon in routine SEPFAC
 335  -  unsuccessful search for intersecting edge of face FL in SEPFAC
 336  -  separator face not found in routine MFDEC3
 340  -  holes are not in nondecreasing face index order in routine DSPHFH
 341  -  hole on non-boundary face of polyhedral region detected by DSPHFH
 342  -  face containing non-coplanar vertices detected by DSPHFH
 344  -  cannot find subregion above top (or below bottom) vertex of hole in
	 routine SPDECF
 346  -  hole polyhedron not connected to outer boundary by routine DSPHIH
 347  -  starting edge not found by routine RESHOL (because PT not in polyh)
 348  -  starting edge not found by routine RESHOL (because ray meets vertex)
 349  -  unsuccessful search for intersecting edge of face FMIN in RESHOL
 400  -  unsuccessful search by routine HTSRCK or HTSDLK
 401  -  degenerate simplex detected by routine BARYCK
 402  -  2 vertices with identical coordinates (in floating point arithmetic)
	 detected in routine FRSMPX, DTRISK, DTRIWK, or DTRIMK
 403  -  all vertices input to DTRISK, DTRIWK, or DTRIMK are in same hyperplane
	 (in floating point arithmetic)
 405  -  invalid configuration (due to tolerance) detected by routine SWAPHS
 406  -  no visible boundary face found in routine DTRISK
 407  -  cycle detected in walk by routine WALKTK
      

The list of routines includes:

• ANGLE computes the size of an angle in 2D.
• ANGLE3 computes the size of a plane angle in 3D.
• AREAPG computes twice the signed area of a simple polygon.
• AREATR computes twice the signed area of a triangle.
• AVAILF returns the index of the next available record in the FC array.
• AVAILK returns the position of the next available record in the FC array,
• BARYCK computes the barycentric coordinates of a point in KD.
• BARYTH computes barycentric coordinates of a point in 3D.
• BCDTRI constructs a boundary-constrained Delaunay triangulation in 3D.
• BNSRT2 bin sorts a set of 2D points.
• BNSRT3 bin sorts a set of 3D points.
• BNSRTK bin sorts a set of KD points.
• CCRADI computes the circumradius of a tetrahedron.
• CCSPH finds the circumsphere through the vertices of a tetrahedron.
• CCSPHK finds the circumsphere through a simplex in KD.
• CMCIRC determines if a point is in the circumcircle of three points.
• CUTFAC traces a cut face of a polyhedron from a starting edge.
• CVDEC2 decomposes a polygonal region into convex polygons.
• CVDEC3 decomposes polyhedra into convex parts.
• CVDECF updates a polyhedral decomposition.
• CVDTRI converts boundary triangles to Delaunay triangles.
• DHPSRT sorts a list of double precision points in KD.
• DIAEDG determines which diagonal to use in a quadrilateral.
• DIAM2 finds the diameter of a convex polygon.
• DIAM3 finds the diameter of a set of 3D points.
• DLESS determines the lexicographically lesser of two double precision values.
• DPI returns the value of pi.
• DSCONV converts the representation of a convex polyhedron.
• DSCPH initalizes the convex polyhedron data structure.
• DSFTDW does one step of the heap sort algorithm for double precision data.
• DSMCPR initializes the polygonal decomposition data structure.
• DSMDF2 sets up a mesh distribution function data structure in 2D
• DSMDF3 sets up a mesh distribution function data structure in 3D.
• DSPGDC initializes the polygonal decomposition data structure.
• DSPHDC initializes the polyhedral decomposition data structure.
• DSPHFH initializes the polyhedral decomposition data structure.
• DSPHIH updates the polyhedral decomposition data structure.
• DTRIMK constructs a Delaunay triangulation of points in KD.
• DTRIS2 constructs the Delaunay triangulation of vertices in 2D.
• DTRIS3 constructs a Delaunay triangulation of vertices in 3D.
• DTRISK constructs a Delaunay triangulation of vertices in KD.
• DTRIW2 constructs a Delaunay triangulation of vertices in 2D.
• DTRIW3 constructs a Delaunay triangulation of vertices in 3D.
• DTRIWK constructs a Delaunay triangulation of vertices in KD.
• EDGHT searches a hash table for an edge record.
• EMNRTH computes the mean ratio of a tetrahedron.
• EQDIS2 subdivides convex polygons for equidistribution.
• EQDIS3 subdivides polyhedra for equidistribution.
• FNDMSW finds local transformation that improve a 3D triangulation.
• FNDSEP finds separators to resolve a reflex vertex.
• FNDSPF finds separators to resolve a reflex vertex.
• FNDSPH finds a separator from top or bottom hole vertex.
• FNDTRI finds two triangles containing a given edge.
• FRSMPX shifts vertices to the first K+1 are in general position in KD.
• FRSTET shifts vertices so the first 4 vertices are in general position in 3D.
• GTIME returns the current CPU time in seconds.
• HEXAGON_VERTICES_2D returns the vertices of the unit hexagon in 2D.
• HOLVRT determines top and bottom vertices of holes in polygonal regions.
• HTDEL deletes a record from the hash table.
• HTDELK deletes a record from the hash table.
• HTINS inserts a record into the hash table.
• HTINSK inserts a record into the hash table.
• HTSDLK searches for a record in the hash table, and deletes it if found.
• HTSRC searches for a record in the hash table.
• HTSRCK searches for a record in the hash table.
• I_MODP returns the nonnegative remainder of integer division.
• I_WRAP forces an integer to lie between given limits by wrapping.
• IFACTY determines the type of an interior face in a 3D triangulation.
• IHPSRT sorts a list of integer points in KD.
• ILESS determines the lexicographically lesser of two integer values.
• IMPTR3 improves a 3D triangulation.
• IMPTRD further improves a 3D triangulation.
• INTTRI generates triangles inside a convex polygon.
• INSED2 inserts an edge into the head and polygon vertex lists.
• INSED3 inserts an edge into the polyhedral decomposition data structure.
• INSEH3 inserts an edge into the polyhedral decomposition data structure.
• INSFAC inserts a new cut face into a polyhedral decomposition.
• INSPH finds the center and radius of the insphere of a tetrahedron.
• INSVR2 inserts a point into the vertex coordinate and polygon vertex lists.
• INSVR3 inserts a point into the polyhedral decomposition database.
• INTMVG generates interior mesh vertices in a shrunken polyhedron.
• INTPG integrates a mesh distribution function over a polygon.
• INTPH integrates a mesh distribution function over a polyhedron.
• ISFTDW does one step of the heap sort algorithm for integer data.
• ITRIS3 constructs an initial triangulation of 3D vertices.
• JNHOLE joins a hole boundary to the boundary of the surrounding polygon.
• LFCINI initializes two lists of faces.
• LOP applies the local optimization procedure to two triangles.
• LRLINE determines whether a point is left, right, or on a directed line.
• LSRCT3 searches a 3D triangulation for the tetrahedron containing a point.
• LUFAC factors a matrix.
• LUSOL solves a linear system involving a matrix factored by LUFAC.
• MDF2 evaluates a heuristic mesh distribution function in 2D.
• MDF3 evaluates a heuristic mesh distribution function in 3D.
• MFDEC2 further divides convex polygons to limit mesh function variation.
• MFDEC3 subdivides polyhedra to control the mesh distribution function.
• MINANG determines the minimum of the boundary angles for a separator.
• MMASEP finds the best of four possible separators.
• MTREDG sets fields for a triangle as needed by routine TMERGE.
• NWSXED creates new simplices from insertion of an interior vertex.
• NWSXFC creates new simplices from the insertion of a face vertex.
• NWSXIN creates new simplices from the insertion of an interior vertex.
• NWSXOU creates new simplices for vertices outside the current convex hull.
• NWTHED creates new tetrahedra from the insertion of a vertex, in 3D.
• NWTHFC creates new tetrahedra after the insertion of a new face vertex.
• NWTHIN creates new tetrahedra after the insertion of an interior vertex.
• NWTHOU creates new tetrahedra outside the current convex hull.
• OPSIDE tests if points are on opposite sides of a triangular face.
• OPSIDK tests if points are on opposite sides of a face in KD.
• ORDER3 reorders 3 integers into ascending order.
• ORDERK reorders K elements of an array in nondecreasing order.
• PRIKME returns a prime greater than a given value K.
• PRMDF2 does preprocessing for the mesh distribution function evaluation.
• PRMDF3 does preprocessing for the mesh distribution function evaluation.
• PTPOLG determines where a point lies with respect to a polygon.
• RADRTH computes the aspect ratio of a tetrahedron.
• RANDPT generates N random points in KD.
• RESEDG resolves a reflex edge by a cut polygon.
• RESHOL3 finds a cut face in a polyhedron to resolve an interior hole.
• RESVRF resolves a reflex vertex of a simple polygon.
• RESVRT resolves a reflex vertex of a simply connected polygon.
• RMCLED removes collinear adjacent convex polyhedron edges from the database.
• RMCPFC removes coplanar adjacent polyhedron faces from the data base.
• ROTIAR rotates elements of an integer array.
• ROTIPG rotates the indices of the vertices of a simple polygon.
• ROTPG rotates a convex polygon.
• SANGMN computes the minimum solid angle of a tetrahedron.
• SDANG computes the solid and dihedral angles of a tetrahedron.
• SEPFAC traces out a separator in a convex polyhedron.
• SEPMDF determines a separator that splits a convex polygon.
• SEPSHP determines a separator that splits a convex polygon.
• SFC1MF seeks a separator or cut face in a convex polyhedron.
• SFC2MF finds a separator or cut face in a convex polyhedron.
• SFCSHP seeks a separator or cut face in a convex polyhedron.
• SFDWMF sifts down a heap.
• SFUPMF sifts up a heap.
• SHRNK2 shrinks a convex polygon.
• SHRNK3 shrinks a convex polyhedron.
• SMPXDA deletes simplices whose circumhypersphere contains a vertex.
• SMPXLS constructs a list of simplices from the FC array.
• SPDEC2 decomposes a polygonal region with holes into simple polygons.
• SPDECH decomposes a face of a polyhedral region.
• STATS computes statistical measurements for data.
• SWAPDG applies swaps in a KD triangulation.
• SWAPEC swaps diagonal edges in a 2D triangulation
• SWAPES swaps faces in a 3D triangulation.
• SWAPHS swaps faces in a KD triangulation.
• SWAPMU swaps faces in a KD triangulation.
• SWAPTF swaps tranformable faces in a 3D triangulation.
• SWPREM tries to remove an interior vertex.
• TETLST constructs a list of tetrahedra from the FC array.
• TETMU computes a tetrahedron shape measure.
• TETSIZ smooths PSI values and computes tetrahedron sizes.
• TIMESTAMP prints the current YMDHMS date as a time stamp.
• TMERGE forms triangles near the boundary by merging vertex chains.
• TRIBFC generates a Delaunay triangulation on polyhedron boundary faces.
• TRIPR3 generates mesh vertices in a decomposed polygonal region.
• TRISIZ smooths PSI and computes triangle sizes.
• TRPOLG generates a Delaunay triangular mesh inside a convex polygon.
• UMDF2 is a sample user mesh distribution function for 2D.
• UMDF3 is a sample user mesh distribution function for 3D.
• UPDATF updates a record in FC after a local transformation.
• UPDATK updates a record in FC after a local transformation.
• UPDATR updates a record in FC after a local transformation.
• URAND is a uniform random number generator.
• VBEDG determines the boundary edges of a 2D triangulation.
• VBFAC determines the boundary faces of a 3D triangulation.
• VBFACK determines the boundary faces of a KD triangulation.
• VISPOL computes the visibility polygon from an eyepoint.
• VISVRT determines a list of visible vertices.
• VOLCPH computes the volume of a convex polyhedron.
• VOLTH computes the volume of a tetrahedron.
• VORNBR determines the Voronoi neighbors of a point.
• VPLEFT is called by VISPOL for the LEFT operation.
• VPRGHT is called by VISPOL for the RIGHT operation.
• VPSCNA is called by VISPOL for the SCANA operation.
• VPSCNB is called by VISPOL for the SCANB operation.
• VPSCNC is called by VISPOL for the SCANC operation.
• VPSCND is called by VISPOL for the SCAND operation.
• WALKT2 walks through a 2D triangulation searching for a point.
• WALKT3 walks through a 3D triangulation searching for a point.
• WALKTH finds the Delaunay simplex containing a point by "walking".
• WIDTH2 determines the width of a convex polygon.
• WIDTH3 determines the width of a convex polyhedron.
• XEDGE determines whether two edges, or an edge and a ray intersect.
• XLINE intersects two lines parallel to given lines.
• XPGHPL intersects a convex polygon with a half plane.

Return to the FORTRAN software page.