GEOMPACK
Voronoi diagrams, Delaunay triangulations

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

Licensing:

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

Related Data and Programs:

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

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

Reference:

Franz Aurenhammer,
Voronoi diagrams - a study of a fundamental geometric data structure,
ACM Computing Surveys,
Volume 23, Number 3, pages 345-405, September 1991.
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;
arc_cosine.m, computes the inverse cosine;
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_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_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.
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_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.