Delaunay triangulation

From visone manual
Revision as of 13:04, 25 May 2023 by Muellerj (talk | contribs)
Jump to navigation Jump to search

The Delaunay triangulation of points is a triangulation of such that no point in 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 is the angle at which the end points of the Delaunay edges see the dual Voronoi edge. That is, if and are the Delaunay triangles incident to the edge , then ; if is on the convex hull, then given the only incident Delaunay triangle . 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 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 and , then let be the intersection point of the perpendicular bisectors of and . The distance stability of a Delaunay edge is defined as , i.e., half the difference in radius of the circle centered at and passing through and to the circle centered at and passing through and .
    • If the Delaunay edge of triangle is located on the convex hull, the distance stability is given by half the distance of from the edge .

Note that the angular stability is invariant to rescaling of the coordinates by a factor , 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.