Delaunay triangulation: Difference between revisions

From visone manual
Jump to navigation Jump to search
No edit summary
No edit summary
 
(6 intermediate revisions by the same user not shown)
Line 6: Line 6:


The stability measures are the following:
The stability measures are the following:
* The angular stability of a Delaunay edge <math>PQ</math> is the angle <math>\alpha</math> at which the end points of the Delaunay edges see the dual Voronoi edge. That is, if <math>PQR</math> and <math>PQS</math> are the Delaunay triangles incident to the edge <math>PQ</math>, then <math>\alpha = \pi - \angle PRQ - \angle PSQ</math>; if <math>PQ</math> is on the convex hull, then <math>\alpha = \pi - \angle PRQ</math> given the only incident Delaunay triangle <math>PQR</math>. For the original definition of this stability measure and a discussion of its properties, see [https://doi.org/10.1007/s00454-015-9730-x Agarwal et al. (2015), Stable Delaunay Graphs, Discrete & Computational Geometry 54:905–929].
* The angular stability of a Delaunay edge <math>PQ</math> is the angle <math>\alpha</math> at which the end points of the Delaunay edges see the dual Voronoi edge. That is, if <math>PQR</math> and <math>PQS</math> are the Delaunay triangles incident to the edge <math>PQ</math>, then <math>\alpha = \pi - \angle PRQ - \angle PSQ</math>; if <math>PQ</math> is on the convex hull, then <math>\alpha = \pi - \angle PRQ</math> given the only incident Delaunay triangle <math>PQR</math>. For the original definition of this stability measure and a discussion of its properties, see [https://doi.org/10.1007/s00454-015-9730-x Agarwal et al. (2015), Stable Delaunay Graphs. Discrete & Computational Geometry 54:905–929].
* The distance stability of a Delaunay edge <math>PQ</math> is computed as follows:
* The distance stability of a Delaunay edge <math>PQ</math> was originally defined in [https://doi.org/10.1016/S0020-0190(99)00107-6 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 <math>PQR</math> and <math>PQS</math>, then let <math>C</math> be the intersection point of the perpendicular bisectors of <math>PQ</math> and <math>RS</math>. The distance stability of a Delaunay edge <math>PQ</math> is defined as the radius of the circle centered at <math>C</math> and passing through <math>R</math> and <math>S</math> minus the radius of the circle centered at <math>C</math> and passing through <math>P</math> and <math>Q</math>.
** If the Delaunay edge has two incident Delaunay triangles <math>PQR</math> and <math>PQS</math>, then let <math>C</math> be the intersection point of the perpendicular bisectors of <math>PQ</math> and <math>RS</math>. The distance stability of a Delaunay edge <math>PQ</math> is defined as <math>(|\overline{CR}|-|\overline{CP}|)/2</math>, i.e., half the difference in radius of the circle centered at <math>C</math> and passing through <math>R</math> and <math>S</math> to the circle centered at <math>C</math> and passing through <math>P</math> and <math>Q</math>.
** If the Delaunay edge <math>PQ</math> of triangle <math>PQR</math> is located on the convex hull, the distance stability is given by the distance of <math>R</math> from the edge <math>PQ</math>.
** If the Delaunay edge <math>PQ</math> of triangle <math>PQR</math> is located on the convex hull, the distance stability is given by half the distance of <math>R</math> from the edge <math>PQ</math>.


Note that the angular stability is invariant to rescaling of the coordinates by a factor <math>\beta > 0</math>, while the distance stability scales linearly.
Note that the angular stability is invariant to rescaling of the coordinates by a factor <math>\beta > 0</math>, while the distance stability scales linearly.
Line 15: Line 15:
== Result ==
== 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.
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 (while the values assigned to pre-existing edges are left unchanged).

Latest revision as of 13:05, 25 May 2023

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 (while the values assigned to pre-existing edges are left unchanged).