GEOMPACK - Voronoi diagrams, Delaunay triangulations

GEOMPACK 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:

• geompack.f90, the source code.
• geompack_prb.f90, a sample problem.
• geompack_prb.out, sample problem output.

Sample data sets include:

• annulus.in, an annulus.
• cmos.in, 30 nodes
• convex.in, a convex polygon with 6 nodes.
• holeatt.in. attached hole in square, 12 nodes.
• intfac.in, interfaces in region, 90 nodes.
• lsup.in, the outline of Lake Superior;
• notch.in, notch in a rectangle.
• ptpg.in.
• refcor.in, refined corner of a square.
• refint.in, refinement in interior of square.
• refsid.in, refinement in the side of a square.
• shr1.in.
• shr2.in.
• shr3.in.
• shr4.in.
• simple.in, a simple polygon.
• vpol1.in.
• vpol2.in.
• vpol3.in.
• vpol4.in.
• vpol5.in.
• vpol6.in.

The list of routines includes:

• ANGLE computes the interior angle at a vertex defined by 3 points.
• AREAPG computes twice the signed area of a simple polygon.
• AREATR computes twice the signed area of a triangle.
• BEDGMV generates boundary edge mesh vertices.
• BNSRT2 bin sorts N points in 2D into increasing bin order.
• CMCIRC determines whether a point lies within a circle through 3 points.
• CVDEC2 decomposes a polygonal region into convex polygons.
• CVDTRI converts boundary triangles to Delaunay triangles.
• DEGREES_TO_RADIANS converts an angle from degrees to radians.
• DELAUNAY_PRINT prints out information defining a Delaunay triangulation.
• DHPSRT sorts points into lexicographic order using heap sort
• DIAEDG chooses one of the diagonals of a quadrilateral.
• DIAM2 finds the diameter of a convex polygon.
• DLESS determine whether P is lexicographically less than Q.
• DMAT_PRINT prints a double precision matrix.
• DSFTDW sifts A(*,MAP(L)) down a heap of size U.
• DSMCPR initializes the polygonal decomposition data structure.
• DSMDF2 sets up a data structure for a heuristic mesh distribution.
• DSPGDC initializes the polygonal decomposition data structure.
• DTRIS2 constructs a Delaunay triangulation of 2D vertices.
• DTRIW2 constructs an incremental Delaunay triangulation in 2D.
• EDGHT searches a hash table for a record in EDGE containing key (A,B).
• EQDIS2 further subdivides convex polygons for mesh equidistribution.
• FNDSEP finds separators to resolve a reflex vertex.
• FNDTRI finds two triangles containing a given edge.
• GTIME gets the current CPU time in seconds.
• HOLVRT determines top and bottom vertices of holes in polygonal regions.
• I_MODP returns the nonnegative remainder of integer division.
• I_SWAP swaps two integer values.
• I_WRAP forces an integer to lie between given limits by wrapping.
• IHPSRT uses heapsort on integer points in K-dimension.
• ILESS determines whether a K-dimensional point P is lexically less than Q.
• IMAT_PRINT prints an integer matrix.
• INSED2 inserts an edge into the head and polygon vertex lists.
• INSVR2 inserts a point into the vertex coordinate and polygon vertex lists.
• INTPG integrates the mesh distribution function in a convex polygon.
• INTTRI generates triangles inside a convex polygon.
• ISFTDW sifts A(*,MAP(L)) down a heap of size U.
• IVEC_IDENTITY sets an integer vector to the identity vector A(I)=I.
• JNHOLE joins a hole boundary to the boundary of a polygon.
• LOP applies the local optimization procedure to two triangles.
• LRLINE determines if a point is left of, right or, or on a directed line.
• LUFAC computes the LU factorization of a matrix.
• LUSOL solves a linear system with an LU factored matrix.
• MDF2 evaluates the heuristic mesh distribution function at (X,Y).
• MFDEC2 subdivides polygons to decrease mesh distribution variation.
• MINANG determines the minimum of the boundary angles for a separator.
• MMASEP chooses the best of four separators by the max-min angle criterion.
• MTREDG sets fields for a triangle as needed by routine TMERGE.
• PRIME returns a prime greater than a given integer K.
• PI returns the value of pi.
• PRMDF2 preprocesses a mesh distribution function evaluation.
• PTPOLG determines if a point is in, on or outside a polygon.
• RADIANS_TO_DEGREES converts an angle from radians to degrees.
• RANDPT generates N random K-dimensional points from the uniform distribution.
• RESVRT resolves a reflex vertex of a simply connected polygon.
• ROTIAR rotates the elements of an integer array.
• ROTIPG rotates the vertex indices of a simple polygon.
• ROTPG rotates a convex polygon.
• SEPMDF splits a polygon according to the mesh distribution function.
• SEPSHP splits a convex polygon according to shape.
• SFDWMF sifts PSI(INDP(L)) down a heap.
• SFUPMF sifts PSI(INDP(R)) up a heap.
• SHRNK2 shrinks a convex polygon.
• SPDEC2 decomposes a polygonal region with holes into simple polygons.
• SWAPEC swaps diagonal edges until all triangles are Delaunay.
• TIMESTAMP prints the current YMDHMS date as a time stamp.
• TMERGE forms triangles near the boundary by merging vertex chains.
• TRINBR determines the neighboring triangles of every triangle.
• TRIPR2 generates triangles inside each convex polygon of a decomposition.
• TRISIZ smooths the mean mesh distribution function.
• TRPOLG generates a Delaunay triangular mesh inside a convex polygon.
• UMDF2 is a dummy mesh distribution function.
• URAND is a uniform random number generator.
• VBEDG determines visible boundary edges of a 2D triangulation.
• VISPOL computes the visibility polygon.
• VISVRT determines a list of visible vertices.
• VORNBR determines the Voronoi neighbors of an eyepoint.
• VPLEFT is called by routine VISPOL for the LEFT operation (OPER = 1).
• VPRGHT is called by routine VISPOL for the RIGHT operation (OPER = 2).
• VPSCNA is called by routine VISPOL for the SCANA operation (OPER = 3).
• VPSCNB is called by routine VISPOL for the SCANB operation (OPER = 4).
• VPSCNC is called by routine VISPOL for the SCANC operation (OPER = 5).
• VPSCND is called by routine VISPOL for the SCAND operation (OPER = 6).
• WALKT2 searches for a triangle containing a point.
• WIDTH2 finds the minimum breadth of a convex polygon.
• XEDGE determines if an edge intersects another edge or ray.
• XLINE finds the intersection of lines parallel to two other lines.

Return to the FORTRAN software page.