Convex Hulls and Metric Gabriel Graphs - Cellular Automata in Image Processing and Geometry - page 190

rule to our previous construction is enough to complete to the complete convex hull.
It turns out to be the case from the results of the next section, and we can already
say that the final construction of the convex hull is therefore obtain using the dist,
cent, back, and conv. Although we used different colors to mark middles, and non
middle cells, they can all be marked in the same way is our static case. We therefore
use 7 states: i.e. one seed state, and for non-seed cells, there is a binary mark and a
modulo 3 value, so 2*3=6otherstates.Thebinarymarkissetto“true”eitherby
the middle detection, the back detection or the conv detection. This is a first possible
summary of our metric solution. But understanding why this is indeed a solution in
general is the same as understanding how the middles should be detected, which is
the subject of the next section. A more detailed summary is given in Sect. 10.6.

10.5 Detectable Middles and Metric Gabriel Graphs

10.5.1 Pairwise Construction in Euclidean Space

In order to understand the detection of the middles, let us look at the pairwise con-
struction described earlier in the context of Euclidean geometry. Figure 10.13 shows
very precisely what the result would be in this case, and has to be compared with
Fig. 10.12. The distance field would be continuous, and concentric circle would
grow similarly as seen in the cellular automata case. When the circles collide, some
middles showed in light green are detected, and the corresponding paths from these
middles back to the seeds can also be detected. The analogy allows us to use existing
tools build from Euclidean spaces to re-expressed the behavior of this construction:
we can use now the vocabulary of Voronoï regions and diagrams and two of its
associated proximity graphs: Delaunay and Gabriel graphs.

10.5.1.1 Voronoï Diagram and Distance Fields

The Voronoï diagram is a famous construction [1, 3]. It consists of associating to
each point of the space its closest seeds. After doing so, each seed has an associated
set of points, and this is called the Vo r o n o ï r e g i o n of this seed. Some points have
many seeds at equal distance. If we highlight these points, the result is called the
Voronoï diagram and displays the borders of the Voronoï regions, the points where
the Voronoï regions are in contact.
Using the distance field implicitly means to have some relation with the Voronoï
regions and diagrams since the distance field associates to each cell of the space
the distance to the closest seeds. Cells that have more than one closest seeds are
those having special patterns of distance value in their neighborhood. This relation
is shown in Fig. 10.14a, where the Voronoï regions boundaries, a.k.a. the Voronoï di-
agram, is displayed in blue. Comparing this with the final configuration of Fig. 10.13
shows the relation with the circles of distance field.