welzl

welzl, an Octave code which computes the minimal bounding circle or sphere for a set of points, using algorithms by Welzl or Ritter, by Anton Semechko.

Functions are provided for computing the exact minimal bounding sphere in 2 and 3 dimensions, using Welzl's algorithm. Additional functions approximate the minimal bounding sphere in higher dimensions, using Ritter's algorithm.

Licensing:

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

Languages:

welzl is available in a MATLAB version and an Octave version.

Related Data and Programs:

welzl_test

Reference:

1. Jack Ritter,
   An efficient bounding sphere,
   in Graphics Gems,
   edited by Andrew Glassner,
   Academic Press, pages 301-303, 1990.
2. Emo Welzl,
   Smallest enclosing disks (balls and ellipsoids),
   Lecture Notes in Computer Science,
   Volume 555, pages 359-370, 1991.
3. https://www.mathworks.com/matlabcentral/fileexchange/48725-exact-minimum-bounding-spheres-and-circles

Source Code:

• ApproxMinBoundSphereND.m, ?
• closed_mesh_volume.m, volume of a region enclosed by a triangular surface mesh.
• exact_min_bound_circle.m, computes exact minimum bounding circle of 2D points.
• ExactMinBoundSphere3D.m, ?
• fit_circle_2_points.m, fit a circle to 2 or 3 points.
• fit_sphere_2_points.m, fits a sphere to 2, 3 or at most 4 points in 3D.
• get_mesh_data.m, gets face-vertex connectivity and vertex coordinates of a mesh.
• icosahedron_mesh.m, generates a triangular surface mesh of an icosahedron.
• min_bound_sphere_demo.m, demonstrates the minimum bound sphere algorithm
• ProjectOnSn.m, ?
• SubdivideSphericalMesh.m, ?
• TriQuad.m, ?
• visualize_bound_circle.m, visualizes a 2D point cloud and its bounding circle.
• VisualizeBoundSphere.m, ?