Figure 13.20 Construction of a Delaunay triangulation.
if and only if the circumscribed circle (i.e. the circle passing through the three points; on the left in the Figure) includes no other point. For example, the file of coordinates shown in the central part of the Figure gives rise to the triangulation on the right. The triangulation is fully described by a list of pairs of points corresponding to its edges; this is how the information can be passed on to a computer program for constrained clustering (Subsection 2).
Long edges may be created at the outskirts of a set of points, simply because there is no other point located farther away in the sampling design; this is called a border effect. For example, edges 2-9 and 7-9 might have been removed from the triangulation in Fig. 13.20 by the presence of other points in the circumscribed circles of triangles (2, 5, 9) and (7, 8, 9) had the sampling extent been broader. Long peripheral edges may be removed by hand or by the computer algorithm.
Gabriel • Gabriel graph — The Gabriel graph criterion (Gabriel & Sokal, 1969) differs from graph that of the Delaunay triangulation (Fig. 13.21a). Draw a line between two points A and
B. This line is part of the Gabriel graph if and only if no other point C lies inside the circle whose diameter is that line. In other words, the edge between A and B is part of the Gabriel graph if D2(A, B) < D2(A, C) + D2(B, C) for all other points C in the study, where D2(A, B) is the square of the geographic distance between points A and B. Another way of expressing this criterion is the following: if CENTRE represents the middle point between A and B, the edge connecting A to B is part of the Gabriel graph if D (A, B)/2 < D (CENTRE, C) for any other point C in the study.
(a) Gabriel graph
Was this article helpful?