GEOMPACK
Voronoi diagrams, Delaunay triangulations

GEOMPACK is a library of MATLAB routines which can compute the Delaunay triangulation of a set of points in the plane.

Related Data and Programs:

GEOMETRY is a MATLAB library of routines for geometric calculations in 2, 3 and N dimensional space.

GEOMPACK is also available in a C++ version and a FORTRAN90 version and a PASCAL version.

Author:

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

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,
   ../../pdf/aurenhammer.pdf
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:

• dtris2.m, returns the Delaunay triangulation of a set of points in 2D.
• 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_inv.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.
• r8_epsilon.m, returns the R8 machine precision.
• r8vec_heap_sort_index_a.m, creates an ascending sort index for an R82VEC using heap sort.
• r82vec_part_quick_a.m, partitions an R82VEC for a quick sort.
• r82vec_permute.m, permutes an R82VEC according to an index vector.
• 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.m, returns an R8MAT of scaled uniform pseudorandom numbers.
• 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.
• timestring.m, returns the current YMDHMS date as a string.
• 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.out, the output from a run of the tests.
• geompack_test01.m, tests POINTS_NAIVE_DELAUNAY_2D.
• geompack_test02.m, tests D2VEC_PART_QUICK_A.
• geompack_test03.m, tests D2VEC_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.