Information Technology Reference
In-Depth Information
we let
ˀ
sweep downward and thereby construct the remaining part of the roof
structure outside of
P
.
This idea can be summarized in the next algorithm, where we concentrate
on the construction of the straight skeleton inside
P
.
Algorithm 1 (Straight skeleton).
Input: polygon
P
and angle
ʱ
between the roof plates and the horizontal plane.
Output: straight skeleton inside
P
.
Procedure:
1. For each edge
e
of
P
, generate the half-plane containing
e
that is toward the
inside of
P
, forming angle
ʱ
with respect to the horizontal plane, and put it
into storage
S
. (We will call the elements of
S
the
roof plates
.)
2. For each vertex
v
of
P
, generate the half-line at the intersection of the two
roof plates that are associated with the two edges incident to
v
, and put it
into storage
E
. (We will call the elements of
E
the
roof edges
.)
3. For each edge
e
of
P
, trim the corresponding roof plates in
S
by the two roof
edges emanating from the two t
er
mina
l
vertices of
e
.
4. Create empty storage locations
E
and
S
.
5. Repeat Steps 5.1, 5.2, and 5.3 until
E
and
S
are empty.
5.1 Find a pair (
e, s
) of a roof edge
e
and a nonneighboring roof plate
s
such
that they intersect and the point of intersection is the lowest among all
such pairs.
5.2 Move
e
from
E
to
E
.
5.3 Increment the roof structure around the point of intersection (details of
this procedure will be shown below). If new roof edges are created, add
them to
E
. If the roof plate
s
in
S
become completely bounded by roof
edges, move them from
S
to
S
.
6. Ou
tp
ut the roof structure consisting of the roof edges in
E
and the roof plates
in
S
.
(
(
(
Fig. 9.
Inconsistency in the construction of a degenerate straight skeleton: (a) regular
polygon and growing skeleton edges; (b) detection of the first vertex; (c) detection of
the second vertex, which contradicts the first vertex.
Search WWH ::
Custom Search