GEOMPACK
Voronoi diagrams, Delaunay triangulations

GEOMPACK is a MATLAB library which computes the Delaunay triangulation of a set of points in the plane, by Barry Joe.

Licensing:

The computer code and data files described and made available on this web page are distributed under the GNU LGPL license.

Languages:

GEOMPACK is available in a C version and a C++ version and a FORTRAN77 version and a FORTRAN90 version and a MATLAB version.

Related Data and Programs:

GEOMETRY, a MATLAB library which carries out geometric calculations in 2, 3 and N dimensional space.

VORONOI_DISPLAY, a MATLAB program which computes the exact Voronoi diagram using geompack, and displays it.

Author:

Original FORTRAN77 version by Barry Joe; Matlab 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.

Examples and Tests:

• geompack_test.m, calls all the tests.
• geompack_test_output.txt, the output file.
• geompack_test005.m, tests DIAEDG.
• geompack_test01.m, tests POINTS_NAIVE_DELAUNAY_2D.
• geompack_test02.m, tests R82VEC_PART_QUICK_A.
• geompack_test03.m, tests R82VEC_SORT_QUICK_A.
• geompack_test05.m, tests DTRIS2.
• geompack_test06.m, tests TRIANGLE_CIRCUMCENTER_2D.
• geompack_test07.m, tests TRIANGULATION_PLOT_EPS.
• triangulation_plot.png, a PNG image of the triangulation created by GEOMPACK_TEST_07.
• geompack_test08.m, tests TRIANGULATION_PRINT.

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