Information Technology Reference
In-Depth Information
S
CH
(
S
)
(b)
(a)
(c)
(d)
(e)
Fig. 2.
Convexity measures for a shape
S
enclosing red points. (a) Solid segments are within
S
,
while dashed ones are not. (b) A shape and its convex hull (dashed). (c) Area-based measure
ignores boundary defects. (d-e) Ink needed to connect the points is much bigger than the length
of the minimum spanning tree. The shape is enclosed in solid black, while the tree is dashed red.
all the clusters will be processed as the trees do not separate the plane into more than
one region. Finally, contiguous non-overlapping regions can be grown, starting from
these disjoint trees. However, this procedure often generates “octopus”-like shapes that
are neither aesthetically pleasant nor practically useful for visualization; see Fig.1.
Hence, we require a method for creating regions that are as convex as possible. In order
to designsuch a method, a quality criterion for measuring the convexity of regions is
needed. Next we review and formalize several convexity measures.
3.1
Convexity Measures
A shape
S
is said to be convex if it has the following property: If points
p,q
∈
R
belong
to
S
then all points from the line segment [
pq
] belong to
S
as well. The definition allows
for several different ways to measure the convexity of non-convex shapes.
Point/Vertex Visibility.
For a given shape
S
, this convexity measure is defined as the
probability that for points
p
and
q
, chosen uniformly at random from
S
, all points from
the line segment [
pq
] also belong to
S
[24]. The result is a real number from [0
,
1], with
1 corresponding to convex shapes. A problem with this definition is that it is difficult
to compute, even if
S
is a polygon. Hence, we consider its discrete variant, taking into
account that the inputofour problem specifies points in the plane; see Fig.2(a).
This vertex-based measure takes into account how many segments [
pq
] are com-
pletely in
S
for pairs of input points
p,q
∈
P
of the cluster corresponding to
S
.The
p,q∈P
ʴ
(
p,q
)
|
measure is defined as
2
,wherethesum is over all pairs of input points
P
and
ʴ
(
p,q
)=1if [
pq
] lies inside
S
and
ʴ
(
p,q
)=0,otherwise.
P
|
Convex Hull Area/Perimeter.
Recall that the smallest convex set which includes a
shape
S
is called the
convex hull
,
CH
(
S
),of
S
;seeFig. 2(b). The area-based convexity
measure is defined as
Area
(
S
)
Area
(
CH
(
S
))
;itisfrequently used and appears in textbooks [23].
The result is a real number from [0
,
1], with 1 corresponding to convex shapes. Unlike
visibility-based measures, the convex hull-based one is very easy to calculate efficiently
and is robust with respect to noise. However, the definition does not allow to detect
defects on boundary that have a relatively small impact on the shape area; see Fig.2(c).
The perimeter-based definition attempts to remedy this:
Perimeter
(
S
)
Perimeter
(
CH
(
S
))
.
