Dune Surfaces: A Spatial Visualization Technique for Medial Axes in the Plane or on the Sphere

Year: 2012 Authors: Peter Calvache

Core claim

Closest-distance height mapping produces aesthetically readable surfaces whose ridges coincide with medial axes in both planar and spherical settings.

Topics

medial axes, Voronoi diagrams, spatial visualization, geographic data

Domains

computational geometry, distance functions, point-in-polygon, spherical geometry, data visualization, geometric aesthetics, cartographic visualization

Methods

closest-distance mapping, ray casting algorithm, great-circle distance, spherical coordinate transform

Media

planar shapes, earth continents dataset, Spratly Islands

Paper text

The text below is the locally extracted OCR/Markdown version of the paper. Raw PDF files remain local and are not published here.

Bridges 2012: Mathematics, Music, Art, Architecture, Culture

Dune Surfaces: A Spatial Visualization Technique for Medial Axes in the Plane or on the Sphere

Peter Calvache Department of Geometry University of Applied Arts Vienna Oskar-Kokoschka-Platz 2 1010 Vienna, Austria E-mail: petercalvache@gmail.com

Abstract

We present a technique by which the decomposition of surface areas through medial axes can be visualized in a fuzzy manner, in contrast to the discrete manner that medial axes normally impose. By mapping the closest-distance value of each point on the surface to its height-coordinate, remarkably aesthetic surfaces are constructed that uniquely relate the surface points to their nearest points on the shapes. We call the resulting manifolds “Dune Surfaces” because of the resemblance to sand dunes. We apply this technique of visualization, on a large scale, to the continents of the earth and, on a small scale, to the hotly disputed Spratly Islands in the South China Sea.

The Problem

Let $\mathbb{C}\subset {\mathbb{R}}^2$ be an arbitrary closed shape in the plane – the boundary of a closed region $\mathbb{R}$ . Can a polyline be found that subdivides $\mathbb{R}$ into two parts along the (potentially multiple) length axes of the shape $\mathbb{C}$ ? Geometrically speaking, this simply requires the finding of the medial axis – the locus $l$ of all points $p\in {\mathbb{R}}^2$ in $\mathbb{R}$ that have more than one closest point on $\mathbb{C}$ [1]. Equally, $l$ is the locus of the midpoints of all circles within $\mathbb{R}$ that don’t intersect $\mathbb{C}$ but touch at least two of its sides (maximal circles). It is defined as:

where

For convex and concave shapes $\mathbb{C}$ alike, $l$ can be approximated as a polyline, albeit for concave shapes, it takes the form of a graph rather than that of a linear chain (see Figure 1).

Calvache

Figure 1: The medial axis of a concave shape (notice the maximal circles).

Medial axes are frequently employed in shape recognition – particularly in character recognition, where an alphabetic character can be guessed from the graph topology of the medial axis that is derived from its bitmap representation. Our goal was to present medial axes spatially, suggesting a fuzzy gradation rather than a discrete division, so that the decomposition of highly complex and concave surfaces would be instantly comprehensive to a visual mind.

The Dune Surface

Let $S=\{C\}$ be a set of shapes $C$ in the Euclidean plane. The spatial dune surface $\Delta$ is defined as follows, given a surface point $p\in {\mathbb{R}}^2$ and the set of shapes $S$ as parameters:

where

In computational terms, the function $i(p,S)$ may be further specified as follows:

where $s(p,S)$ yields the number of intersections between any shapes in $S$ and a ray from $p$ in an arbitrary direction. Thus, $i$ always yields 1 for all $p$ inside single closed polygons and $-1$ for all other cases – a slight adaptation of the ray casting algorithm [2] of the point-in-polygon query.

To put it more simply, we simply define the $z$-Coordinate of the dune surfaces’ parametric point as the minimum distance between that parametric point and any point on any shapes in $S$. We further multiply this $z$-Coordinate by $-1$ if the parametric point happens to reside outside any closed shape in $S$, thus inverting the direction of the surface for all non-enclosed points.

440

Dune Surfaces: A Spatial Visualization Technique for Medial Axes in the Plane or

on the Sphere

Figure 2: The Dune Surface for the Spratly Islands – not exactly a solution to the political problem, but a valid subdivision all the same. When a planar Dune Surface is seen from top, it resembles a Voronoi Diagram (left image).

When derived from a very fragmented and chaotic set of shapes, it is no wonder that, if shaded and seen from the top, the Dune Surface exhibits features resembling a Voronoi Diagram (see Figure 2). The ridges of the Dune Surface are located precisely at the medial axes, as we would expect.

At this point, we could also calculate a planar Voronoi Diagram given a set of two-dimensional closed lines (like S) as the Voronoi generators, and we would get a structure where the division lines between the Voronoi cells coincide with the ridges of the Dune Surface. Normally, this would be an unusual application for a Voronoi Diagram, given that the generators of most are zero-dimensional points. The constant sharpness of the ridges (and the trenches below sea level) also visualizes the fact that for any $n$ -dimensional Voronoi Diagram derived from any set of $m$ -dimensional generators (where $m\le n$ ), the divisions between the Voronoi cells are always unambiguous [3], as are (by analogy) the Dune Surface ridges (or median axes).

On the Sphere

When attempting the calculation using spherical coordinates, the Euclidean distance function $d(a,b)$ for $a\in {\mathbb{R}}^2$ and $b\in {\mathbb{R}}^2$ , which was introduced as part of the definition of the median axis, must be replaced by the equivalent spherical function that yields the great-circle distance:

Furthermore, the Dune Surface $\Delta (p,S)$ in spherical coordinates (with the $z$ -coordinate still denoting the height relative to sea level) must finally be transformed back into Cartesian space:

The transformation for $p\in {\mathbb{R}}^3$ proceeds as follows:

Calvache

We have applied the spherical method on a rough dataset of earth’s continents (see Figure 3).

Figure 3: Dune Surface based on earth’s continents.

Conclusion

Dune Surfaces nicely illustrate the fuzzy geometric relations underlying the discrete structures of medial axes or Voronoi Diagrams. Whereas Voronoi Diagrams display the precise relationship between each point and its generator, Dune Surfaces visualize how the differing distances of each point to its generator lead to the emergence of discrete Voronoi cell divisions – the ridges and trenches of the Dune Surface. We have shown how the surface can be calculated both in the Euclidean plane and on the sphere. Finally, we have presented some interesting graphical results based on geographic data.

References

[1] H. Blum A Transformation for Extracting New Descriptors of Shape, 1967, Proc. Models for the Perception of Speech and Visual Form, S.~362-380. [2] I. Sutherland, et al. A Characterization of Ten Hidden-Surface Algorithms, 1974, ACM Computing Surveys vol. 6 no. 1. [3] F. Aurenhammer, Voronoi diagrams – a survey of a fundamental geometric data structure, ACM Computing Surveys (CSUR), Volume 23 Issue 3, Sept. 1991.