Delaunay triangulation

The Delaunay triangulation of points $P$ is a triangulation of $P$ such that no point in $P$ lies in the circumcircle of a triangle. The Delaunay triangulation is the dual of the Voronoi diagram.

Stability measures

visone computes two stability measures on Delaunay edges. Smaller values of these measures mean less change is needed to the coordinates of nearby points for the edge to vanish in the triangulation.

The stability measures are the following:

• The angular stability of a Delaunay edge $PQ$ is the angle $\alpha$ at which the end points of the Delaunay edges see the dual Voronoi edge. That is, if $PQR$ and $PQS$ are the Delaunay triangles incident to the edge $PQ$, then $\alpha =\pi -\angle PRQ-\angle PSQ$; if $PQ$ is on the convex hull, then $\alpha =\pi -\angle PRQ$ given the only incident Delaunay triangle $PQR$. For the original definition of this stability measure and a discussion of its properties, see Agarwal et al. (2015), Stable Delaunay Graphs. Discrete & Computational Geometry 54:905–929.
• The distance stability of a Delaunay edge $PQ$ was originally defined in Abellanas et al. (1999), Structural tolerance and Delaunay triangulation. Information Processing Letters 71(5–6):221–227. It is computed as follows:
  • If the Delaunay edge has two incident Delaunay triangles $PQR$ and $PQS$, then let $C$ be the intersection point of the perpendicular bisectors of $PQ$ and $RS$. The distance stability of a Delaunay edge $PQ$ is defined as $(|{\overline {CR}}|-|{\overline {CP}}|)/2$, i.e., half the difference in radius of the circle centered at $C$ and passing through $R$ and $S$ to the circle centered at $C$ and passing through $P$ and $Q$.
  • If the Delaunay edge $PQ$ of triangle $PQR$ is located on the convex hull, the distance stability is given by half the distance of $R$ from the edge $PQ$.

Note that the angular stability is invariant to rescaling of the coordinates by a factor $\beta >0$, while the distance stability scales linearly.

Result

visone computes the Delaunay triangulation of a set of points described by the given nodes in a network, plus the stability measures computed on each Delaunay edge. If desired, pre-existing edges in the network can be removed, and unstable Delaunay edges whose stability measures are below given thresholds can be elided. Moreover, newly created Delaunay edges are assigned the value true in a specified Boolean edge attribute.