GEOMPACK3
Computational Geometry in 2D, 3D, ND

GEOMPACK3 is a FORTRAN90 library which handles certain computational geometry problems, by Barry Joe.

In particular, GEOMPACK3 can compute the Voronoi diagram, and the Delaunay triangulation, of a set of points in the plane, and can carry out analogous operations for points in 3D and in N-dimensional space.

Languages:

GEOMPACK3 is available in a FORTRAN90 version

Related Data and Programs:

DUTCH, a FORTRAN90 library which carries out tasks in computational geometry.

GEOMETRY, a FORTRAN90 library which performs geometric calculations in 2, 3 and N dimensional space.

GEOMPACK, a FORTRAN90 library which contains a subset of the routines in GEOMPACK3, but only those for certain 2D calculations.

TET_MESH_DISPLAY_OPENGL, a C++ program which reads a tet mesh and displays the nodes and edges using OpenGL.

Author:

Original FORTRAN77 version by Barry Joe; FORTRAN90 version by John Burkardt.

Reference:

1. Barry Joe,
   GEOMPACK - a software package for the generation of meshes using geometric algorithms,
   Advances in Engineering Software,
   Volume 13, pages 325-331, 1991.
2. George Forsythe, Michael Malcolm, Cleve Moler,
   Computer Methods for Mathematical Computations,
   Prentice Hall, 1971.

Source Code:

• geompack3.f90, the source code.
• geompack3.sh, commands to compile the source code.

Examples and Tests:

• geompack3_test.f90, a sample problem.
• geompack3_test.sh, commands to compile, link and run the sample problem.
• geompack3_test.txt, the output file.

List of Routines:

• 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.
• 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.
• GET_UNIT returns a free FORTRAN unit number.
• 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.
• I4_MODP returns the nonnegative remainder of integer division.
• I4_SWAP swaps two integer values.
• I4_UNIFORM returns a scaled pseudorandom I4.
• I4_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.
• I4MAT_TRANSPOSE_PRINT prints an I4MAT, transposed.
• I4MAT_TRANSPOSE_PRINT_SOME prints some of the transpose of an I4MAT.
• IMPTR3 improves a 3D triangulation.
• IMPTRD further improves a 3D triangulation.
• IMPTRF improves a given triangulation in 3D.
• 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.
• PRIME 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.
• R8MAT_TRANSPOSE_PRINT prints an R8MAT, transposed.
• R8MAT_TRANSPOSE_PRINT_SOME prints some of an R8MAT, transposed.
• RADRTH computes the aspect ratio of a tetrahedron.
• RANDPT generates N random points in KD.
• RESEDG resolves a reflex edge by a cut polygon.
• RESHOL finds a cut face in a polyhedron to resolve an interior hole.
• RESVRF resolves a reflex vertex of a simple polygon.
• RESVRH resolves a hole vertex on a face by finding a separator.
• 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.

You can go up one level to the FORTRAN90 source codes.