Note: This webpage is under construction. Some of its content is still evolving and may not be completely accurate. More content and corrections are coming soon.

Introduction

Part 1 of these notes introduced the concepts underlying a 2D alpha shape utility. This section of the notes covers the algorithms and technical details of the Tinfour implementation. Although the Tinfour AlphaShape class is written in Java, the ideas described in these notes would carry over to any development environment.

The classic alpha shape definition depends on the construction of a Delaunay triangulation. And, naturally, the Tinfour AlphaShape code is built on top of the Tinfour Delaunay triangulation classes. Tinfour implements the Delaunay using a Java interface known as IIncrementalTin (for "incremental triangulated irregular network"). While some of the operations described in this article depend the capabilities defined by that interface, all of the functions it uses should have equivalents in other Delaunay triangulation implementations.

Preliminaries

Before getting into the techniques used by AlphaShape, we will briefly review the relevant features of Tinfour Delaunay triangulations. The figure below illustrates the structure of a simple triangulation based on four vertices labeled A, B, C, and D.

The following details will be relevant to our discussion of the Tinfour algorithms for constructing an AlphaShape from a Delaunay triangulation.

• Tinfour Delaunay triangulations implement a collection of vertices and edges. Triangles are not actively maintained in memory, but may be constructed on an as-needed basis.
• In the classic Delaunay triangulation, pairs of vertices are linked together by bi-directional edges. Tinfour uses a "paired edge" structure in which two single-direction edges are coupled together, one edge for each direction of traversal.
• Each Tinfour edge carries a reference to a corresponding "dual" edge that supports the opposite direction of traversal. In the figure above, the edge labeled "0" indicates the traversal from vertex A to B. Its dual, the edge labeled "1" supports the traversal from vertex B to A.
• Tinfour assigns unique integer index values to each edge at the time it is created. These index values allow an application to maintain supplemental information about the edges they represent.
• To form triangles, each Tinfour edge is linked to two other edges. These linked edges are referred to the "forward" edge and the "reverse" edge. The Tinfour API provides methods for obtaining references to each linked edge (forward, reverse, and dual).
• When three edges are linked together to form a triangle, the triangle is always specified in counterclockwise order.

Additional details about the Tinfour edge concept are presented in our Wiki article Tutorial Using Edge Based Techniques.

Building an alpha shape

The Tinfour technique for building an alpha is a three-step process:

1. Create a Delaunay triangulation from a set of scattered data points
2. Use the alpha-circle criteria to identify edges from the triangulation as being either a border, or interior or exterior to the alpha shape (Edelsbrunner referred to exterior edges as α-exposed).
3. Connect the border edges together to form polygons enclosing the alpha shape.
   • An alpha shape may consist of multiple polygons.
   • Some polygons may include "holes" (nested polygons).
   • For sufficiently small radius values, it may be impossible to build polygons that enclose all of the input points. Some points may remain as "orphans" which must be treated as isolated individuals rather than part of a polygon structure.

The Delaunay triangulation is the focus of the Tinfour software project. Given a set of scattered points, the Tinfour API includes classes that link points into a triangle-based mesh structure that can be accessed through the Java interface IIncrementalTin. Interested readers may consult our project documentation and Wiki page for more information.

Is an edge exposed?

Once a Delaunay triangulation is constructed from a set of scattered points, it may be passed to Tinfour's AlphaShape constructor along with an arbitrarily specified radius value.

AlphaShape begins by classifying each edge in the Delaunay triangulation as either interior (α-unexposed), exterior (α-exposed), or a border according to the following rules:

• α-exposed: If both of the alpha circles associated with the edge are empty, the edge is exterior to the alpha shape.
• α-unexposed: If both of the circles are occupied by distinct vertices, the edge is interior to the alpha shape.
• border: If one of the circles is occupied by a vertex and the other is empty, then the edge is a border of the alpha shape (see The circle selection criteria).
• border (Tinfour modified rule): If both circles are occupied by the same vertex, but not by any others, the edge is a border of the alpha shape (see Tinfour modifications for border identification).

If we had to search for every point in an input sample set in order to discover whether a circle is occupied or not, the processing cost for a large set of points might become prohibitive (on the order of N²). Fortunately, the nature of the Delaunay triangulation makes that unnecessary.

To determine the alpha exposure value for any standard edge in the Delaunay triangulation, it is sufficient to inspect the two vertices opposite that edge. If an alpha circle is not occupied by either of the associated vertices, then it will not be occupied by any other vertices in the Delaunay triangulation. A typical edge/vertex situation is illustrated in the figure below

Assigning an edge as a border or interior component

When both alpha circles associated with an segment (pair of edges) are occupied by vertices, the segment is treated as being part of the interior of the alpha shape. When both circles are empty, the segment is treated as being exterior to the alpha shape ( Because the alpha circles contain a vertex on one side of segment AB, but not both, the segment would be treated as a border. The alpha circle to the right of the edge is occupied by Vertex D. The alpha circle to the left is not occupied. Tinfour defines the side of the edge with an empty circle as being exterior to the alpha shape. The side of the edge with an occupied circle is treated as being in the interior.

During the construction of the AlphaShape, Tinfour maintains an array of flags indicating which edges are interior to the alpha shape and which are borders^[1]. These arrays are named covered[] and border[]. The arrays are indexed using the edge index as shown in the figure above^[2]. In the figure above, segment AB is a border because only one of the alpha circles is occupied (by vertex D). The segment has two sides (two Tinfour edge objects) which are numbered 0 and 1. In the figure, the edge to the left of segment, which has edge index 0, faces the exterior of the alpha shape. So border[0] would be set to true. The edge to the right of the segment, which has edge index 1, faces the interior of the alpha shape, so covered[0] would be set to true.

Stitching edges together to form alpha polygons

The alpha circle criterion allows an application to identify a set of edges that border an alpha shape. Once the border segments are established, the AlphaShape links them together into polygons using a sweep technique as illustrated in the figure below. Before considering the figure, we note the following:

• The outward side of the edge is marked with the border flag. For example, in the upper part of the image, edges 1, 15, and 21 are borders.
• The inward side of the edge is marked with the covered flag and treated as being interior to the alpha shape. For example, edges 0, 14, and 20 are covered.
• The alpha shape polygon will consist of the inside edges and be given in a counterclockwise order.

The sweep

The sweep process begins with an arbitrarily chosen border edge. As described above, the border edge faces outward from the alpha shape. The logic adds the dual of the border edge (the dual is the inner facing edge) to the polygon. The process then searches the edges that are adjacent to the border by sweeping in a counterclockwise order around its initial point (in the figure, the sweeps are shown as loops ending with arrows). The polygon is considered complete when the search reaches the starting polygon.

The alpha shape may contain multiple polygons. Once a polygon is completed, the code searches for any additional edges that have not yet been committed to a polygon. As they are found, the sweep-and-build process continues as described above. When no additional uncommitted edges are available, the polygon-building portion of the alpha shape algorithm terminates.

The final step in the process is to collect a list of any individual vertices that were not part of the region enclosed by the polygons. To do so, Tinfour simply checks for any vertices that were not connected to an edge that was classified as covered.

Accomplishing the sweep

To perform the sweep operation, the AlphaShape class uses the forward, dual, and reverse links for each edge. The figure below shows a locally concave section of the Delaunay triangulation near its upper corner.

During the border identification process, edge 21 is marked as a border (edge 20 is interior to the alpha shape and so marked as covered). The initial vertex of edge 21 is marked as the "Pivot". If the algorithm picked 21 as its starting edge, it would add its dual (edge 20) to the polygon and transfer the search to edge 15. Edge 15 is part of the same triangle as 21 and is referenced by the reverse link of 21. This observation leads to a partial description of the traversal rule:

• For each border edge, obtain its reverse link
• If the reverse link is a border, transfer to the reverse

The figure below shows a section of a Delaunay triangulation that is locally convex. If the algorithm picked edge 507 as a starting edge, it would have to traverse across 4 α-exposed edges in order to reach the next border segment (edge 501).

The observation that the traversal must sometimes cross multiple edges leads to a more complete description of the traversal rule:

• For the current edge, obtain its reverse link
  • If the reverse link is a border, transfer to the reverse.
  • If the reverse link is α-exposed, transfer to the dual of the the reverse link

Finally, we note that in the figures above, the sweeps sometimes pass outside the convex hull of the Delaunay triangulation. To ensure that the Delaunay triangulation link relationships are fully populated (reverse, forward, and dual), Tinfour implements a set of non-standard edges (so called "ghost edges") which lie outside the convex hull. The presence os these edges allows the AlphaShape class to apply the traversal rules without special considerations.

More content to come: Present the complete algorithm in outline form, suitable for implementation. Add a conclusion. Mention the example class AlphaShapeDemoImage.java from the Tinfour code distribution.

Notes

[1] Edelsbrunner, et al., original paper treats border edges as α-exposed. That choice reflects the mathematical basis for their proofs and derivation (as does the choice of open circles versus closed circles for the edge selection criterion). To distinguish implementation considerations the Tinfour code does not use the term "unexposed". Instead, it uses the term "covered" to refer to edges that are either α-unexposed (interior) or part of the border.

[2] For clarity, it is worth noting that what Tinfour calls an "edge" is usually just a single side of a bidirectional segment created between two vertices in the Delaunay triangulation.

References

Edelsbrunner, Herbert; Kirkpatrick, David G.; Seidel, Raimund. (1983). On the shape of a set of points in the plane, IEEE Transactions on Information Theory, 29 (4): 551–559, doi:10.1109/TIT.1983.1056714.