geompack

geompack, an Octave code which carries out certain geometric computations, including the convex hull, the Delaunay triangulation and the Voronoi diagram of a set of points in the plane, by Barry Joe.

Licensing:

The information on this web page is distributed under the MIT license.

Languages:

geompack is available in a C version and a C++ version and a Fortran90 version and a MATLAB version and an Octave version.

Related Data and Programs:

geompack_test

geometry, an Octave code which carries out geometric calculations in 2, 3 and N dimensional space.

voronoi_display, an Octave code which computes the exact Voronoi diagram using geompack(), and displays it.

Author:

Original Fortran77 version by Barry Joe; This version by John Burkardt.

Reference:

1. Franz Aurenhammer,
   Voronoi diagrams - a study of a fundamental geometric data structure,
   ACM Computing Surveys,
   Volume 23, Number 3, pages 345-405, September 1991.
2. Barry Joe,
   GEOMPACK - a software package for the generation of meshes using geometric algorithms,
   Advances in Engineering Software,
   Volume 13, pages 325-331, 1991.

Source Code:

• alpha_measure.m, measures the triangulated point set quality measure ALPHA.
• angle_rad_2d.m, returns the angle between two rays in 2D, in radians;
• diaedg.m, chooses a diagonal edge.
• i4_modp.m, returns the positive remainder after division.
• i4_sign.m, returns the sign of an integer.
• i4_wrap.m, wraps an integer into a limited range.
• i4mat_transpose_print.m, prints the transpose of an I4MAT.
• i4mat_transpose_print_some.m, prints some of the transpose of an I4MAT.
• i4vec_heap_d.m, rearranges an I4VEC into a descending heap.
• i4vec_indicator.m, sets an I4VEC to the indicator vector.
• i4vec_print.m, prints an I4VEC.
• i4vec_sort_heap_a.m, ascending heap sorts an I4VEC.
• i4vec_sorted_unique.m, returns the unique elements of a sorted I4VEC.
• lrline.m, determines if a point lies to the left or right of a directed line.
• perm_check.m, checks a permutation.
• perm_inverse.m, finds the inverse of a permutation.
• points_delaunay_naive_2d.m, a "naive" code for computing the Delaunay triangulation of a set of points in 2D.
• points_hull_2d.m, computes the convex hull of a set of points in 2D;
• quad_convex_random.m, returns a random convex quadrilateral in the unit square.
• r8_acos.m, computes the inverse cosine;
• r8_epsilon.m, returns the R8 machine precision.
• r8_huge.m, returns a "huge" R8;
• r82vec_part_quick_a.m, partitions an R82VEC for a quick sort.
• r82vec_permute.m, permutes an R82VEC according to an index vector.
• r8vec_sort_heap_index_a.m, creates an ascending sort index for an R82VEC using heap sort.
• r82vec_sort_quick_a.m, ascending sorts an R82VEC using quick sort.
• r8mat_transpose_print.m, prints the transpose of an R8MAT.
• r8mat_transpose_print_some.m, prints some of the transpose of an R8MAT.
• r8mat_uniform_01.m, returns an R8MAT of uniform pseudorandom numbers.
• r8tris2.m, returns the Delaunay triangulation of a set of points in 2D.
• r8vec_eq.m, is true if two R8VECs are equal.
• r8vec_gt.m, is true if one R8VEC is greater than another.
• r8vec_lt.m, is true if one R8VEC is less than another.
• r8vec_print.m, prints an R8VEC;
• s_len_trim.m, returns the length of a string to the last nonblank.
• swapec.m, determines which of two diagonals of a quadrilateral should to use in a mesh.
• timestamp.m, prints the current YMDHMS date as a timestamp.
• triangle_circumcenter_2d.m, computes the circumcenter of a triangle in 2D.
• triangulation_plot_eps.m, makes an Encapsulated PostScript image of a triangulation in 2D.
• triangulation_print.m, prints information about a triangulation in 2D.
• vbedg.m, determines which edges are visible to a point.