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.
Part of
Geometry in Action,
a collection of applications of computational geometry.
David Eppstein,
Theory Group,
ICS,
UC Irvine.
Semi-automatically
filtered
from a common source file.
