Medial Axes

The medial axis of a polygon is the boundary of the Voronoi diagram of its edges, and forms a tree-like skeleton useful in character recognition, road network detection in geographic information systems, and other applications.

• Analysis of metaphase chromosomes. D. Sudar et al. use medial axes to map locations along images of chromosome structures.

• Central path algorithm. Y.R. Ge and D. Stelts use medial axes to find paths along the central line of the intestinal system as part of a virtual endoscopy system for non-invasive medical diagnosis.

• Convex hull, Voronoi diagram, and Delaunay triangulation software from Nina Amenta's CG software directory.

• Detail removal. The Queen's U. finite element group uses medial axes to simplify parts to be simulated while maintaining as little error as possible, as part of their QUB mesh generation system. Presumably similar ideas would also apply to model simplification for virtual reality.

• Font Wizard Algorithm. Howard Trickey of Bell Labs describes his software for producing three-dimensional renderings of letterforms, including a straight skeleton like algorithm for achieving a beveled effect.

• A formal approach to lettershape description for type design. P. Ghosh and C. Bigelow describe character shapes in terms of their medial axes.

• Geometric morphology of granular materials. B. R. Schlei, L. Prasad, and A. N. Skourikhine use constrained Delaunay meshing and chordal axis transforms to identify grains and determine statistical features in micrographs of porous media in order to obtain input for hydrodynamic calculations. For more information, see Schlei's web site, and their additional papers "A geometric transform for shape feature extraction" and "Feature-based syntactic and metric shape recognition".

• Medial axis for chamfer distances in 2d, 3d and 4d. E. Remy and E. Thiel describe algorithms for computing medial axes for certain polyhedral distance functions.

• Medial axis pruning. Robert Ogniewicz of Harvard uses medial axes for shape recognition.

• Medial axis transformation and its application to seal imprint verification. Y.-M. Fuh uses medial axis skeletonization as part of a method for detecting forgeries in Chinese signature blocks.

• Medial-axis-based methods in mesh generation, from Steve Owen's Meshing Research Corner.

• A novel type of skeleton for polygons. Aichholzer, Alberts, Aurenhammer, and Gärtner define the "straight skeleton", a geometric construction resembling the medial axis and potentially useful in defining rooflines of buildings. (Warning: lots of incredibly annoying cookies.)

• Scale space skeletonization. Pixel-based medial axis transform techniques by L. da F. Costa and L. F. Estrozi.

• Sity. Tom Kelly appears to be creating artificial cityscapes by using Voronoi diagrams of sites with lots of collinearity to form the city blocks and streets, similar Voronoi diagrams within the blocks to form property boundaries and building floorplans, and straight skeletons for the rooflines.

• Skeleton and boundary extraction. Glynn Robinson of Yale overlays the Delaunay triangulation and Voronoi diagram of points sampled from a surface (the boundary between different features in a medical image) and somehow extracts from them subsets representing the surface itself and its medial axis.

• Straight skeleton implementation. Petr Felkel and Stepán Obdrzálek apply this medial axis variant to segmentation of images of placentas as a preliminary step in shape reconstruction from contours.

• Tesarna Typesetter Program uses medial axes to produce carved lettering by a computer controlled router.

• Three Dimensional Medial Axis Analysis of the Void Structure of Geological Materials, Coker, Lindquist, and Lee, BAPSPC '95. (Abstract only.) See also Medial axis analysis of three dimensional tomographic images of drill core samples, a journal submission by the same authors.

• Time-critical collision detection. Philip Hubbard uses medial axes to find multi-resolution approximations of a shape by unions of spheres, and uses these approximations for fast collision detection.

• TRIM Watershed Atlas. This project uses medial axes to approximate the drainage patterns of watersheds. Warning: 472kb PDF file. See especially appendix D on page 45 of the PDF, describing the algorithms used by this project.

• US Patents 5506784, 5510994, and 5541847 use medial axes to generate embroidery patterns.

• Virtual terrain project: Roofs.