Information Technology Reference
In-Depth Information
(
a
)
(
b
)
(
c
)
(
d
)
(
e
)
Fig. 1.
All the possible internal angles at vertices in octilinear polygons (angles
d
,
e
and
f
are concave). Angles
b
and
e
are the only possible internal angles of rectilinear
polygons.
with internal angles of 180
◦
. Given a multiple polygon
A
P
,
P
, we denote by
B
P
,C
P
,D
P
,E
P
,F
P
) the number of angles of type
(resp.,
a
(resp.,
b, c, d, e, f,
)
A
P
,if
in
is clear by the context, and we do the same
for the other types of angle. Note that angles of type
P
. We write
A
, instead of
P
a, b, c
d, e, f
)are
convex (resp., concave). A component with only convex angles is called
convex
component
.
We use
cuts
to divide polygons. A cut for a polygon
(resp.,
P
can be defined as
a segment
c
=[
p
1
,p
2
] such that both
p
1
and
p
2
belong to the boundary of
P
. A cut parallel to
a rectilinear (octilinear, resp.) direction is called
rectilinear cut
(
octilinear cut
,
resp.). Figure
2
and each internal point of
c
belongs to the interior of
P
a
shows an octilinear polygon
P
with two rectilinear cuts that
divide
into two triangles and one rectangle.
A
decomposition
of a polygon
P
P
is defined by a sequence (
c
1
,c
2
,...,c
m
)
of cuts for
P
that, when applied in order, produces a multiple polygon
P
=
{P
1
,P
2
,...,P
m
}
such that: (1) the union of elements of
P
gives
P
, and (2) the
intersection of any two elements of
, if non-empty, consists totally of edges and
vertices. In general, we are interested in decomposition producing multiple poly-
gons having only components as elements. Generalizing, decomposing a multiple
polygon
P
P
consisting of the union of the
P
produces a new multiple polygon
decompositions of all elements of
.
In this work we are interested in decomposing octilinear polygons into octilin-
ear triangles and rectangles. In the remainder, octilinear rectangles and triangles
are simply called
basic components
.
P
(
opd-tr) octilinear pol. decomp. into octilinear triangles and rectangles
given:
A multiple octilinear polygon
P
.
problem: Decompose
P
into the minimum number of basic components.
When the input of the opd-tr problem is restricted to rectilinear polygons,
it can be easily observed that we get the well known problem of “minimum
dissection of rectilinear regions” [
16
], that has been solved in polynomial-time
at earlier stage.
Search WWH ::
Custom Search