Information Technology Reference
In-Depth Information
Both for technical and theoretical reasons we are also interested in decom-
posing octilinear polygons into convex components, still by using octilinear cuts
only.
(opd-c) octilinear polygon decomp. into octilinear convex components
given:
A multiple octilinear polygon
P
.
problem: Decompose
P
into the minimum number of octilinear convex com-
ponents.
3 Preliminary Results
As observed in the previous section, the opd-tr problem is a generalization
of the well known problem of “minimum dissection of rectilinear regions” [
16
],
denoted here as opd-tr
−
. As already mentioned, this problem is solvable in
polynomial time. Why this problem is so easy? On the sight of addressing the
opd-tr problem, it is useful to provide a brief explanation.
Concerning the opd-tr
−
problem, note that a rectilinear polygon has ver-
tices of type
only, while rectangles (i.e., the final components of the
decomposition) has vertices
b
and
e
only. This implies that, solving the opd-tr
−
prob-
lem requires to use cuts that “remove” angles of type
b
, i.e. all the concave
vertices. To remove the concave vertices, two kind of cuts can be used:
e
v, v
], where
-
vertex-cut:
a vertex-cut is a rectilinear cut [
v
is the concave
v
vertex to be removed and
is any other vertex. At a closer analysis, in the
v
must be a concave vertex as well.
-
point-cut:
a point-cut is a rectilinear cut [
case of rectilinear polygons,
v, p
], where
v
is the concave vertex
to be removed and
is a point internal to some edge (an original edge, or
some edge generated by cuts).
p
In [
7
] it is recalled that the opd-tr
−
problem can be eciently solved by
using a two-phase approach: first find and apply a maximum set of disjoint
rectilinear vertex-cuts, then for each concave vertex
v
(taken in an arbitrary
order) apply a rectilinear point-cut [
]. Now we could ask whether such an
approach can be useful to face with the general case, i.e. when the input is
an octilinear polygon. Unfortunately, the answer is negative since at least the
following observations apply:
v, p
- for the rectilinear case, when a point-cut [
v, p
] that eliminates the concavity
of
is a point internal to some edge), the cut
does
not create
new concave vertices (in fact, it creates two new convex vertices,
i.e. both of type
v
meets a point
p
(where
p
).
In the octilinear case, a cut [
b
v, p
] may create at
p
two new vertices of type
a
and
needs
to be further removed by planning a new octilinear cut, and this new cut may
create further concave vertices and so on.
c
(cf polygons in Fig.
2
). Hence, the new concave vertex of type
c
Search WWH ::
Custom Search