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

a Von Neumann: θ = 90 b Moore: θ = 45 c Hexagonal: θ = 60

Fig. 10.3 θ -convex hulls in cellular spaces

vector directions. The Von Neumann, Moore, and hexagonal cellular spaces thus al-
low directions whose angles are multiple of 90 ⓦ ,45 ⓦ and 60 ⓦ respectively. This con-
cept is called

-convex hull are shown in Fig. 10.3.
It might worth noting that, contrary to the Euclidean convex hull, the vertices of the
θ

θ -convexity , and examples of θ

-convex hull polygon are not necessarily in the original set of points. Using this
definition, let us examine again the behavior the majority rule and see how arbitrary
sets of seeds can be handle.

10.3.1 Majority Rule and θ -Convexity

With the definition of -convexity, we have an explanation of the results of the evo-

lution depicted in Fig. 10.2. However this behavior is not the general case. When the
set of points is not dense enough, we might obtain a disconnected set, corresponding
to a collection of partial

θ

-convex hulls. In fact, it is not really a matter of density,
and if we take the initial configuration of Fig. 10.2 and move only one of the six
bottom seeds, we obtain the behavior shown in Fig. 10.4. In Fig. 10.2, the moved
seed is higher, allowing the partial convex hulls to merge into a bigger convex-hull.
So in general, the complete

θ

-convex hull is not obtained, and it is hard to describe
the final result by an other way than saying that this is the fixpoint of the majority
rule. But both of these issues will be addressed, firstly with the solution described
in the next section, and then further by changing the point of view from a angular to
a metrical one.

θ

10.3.2 Complete θ -Convex Hull

In [5, 14], a cellular automaton is proposed that constructs the -convex hull of

an arbitrary set of seeds, with the little price that the seeds have to be already en-
closed in an arbitrary initial connected region. This rule improves this initial re-
gion by two stages that eventually transforms it into the

θ

-convex hull of the seeds.
The first stage is to reduce the region to ensure that it is smaller than the wanted
θ

θ

-convex hull. The second stage is to inflate the region just enough to exactly match