2009 | OriginalPaper | Buchkapitel
On the Structure of Straight Skeletons
verfasst von : Kira Vyatkina
Erschienen in: Transactions on Computational Science VI
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
For a planar straight line graph
G
, its straight skeleton
S
(
G
) can be partitioned into two subgraphs
S
c
(
G
) and
S
r
(
G
) traced out by the convex and by the reflex vertices of the linear wavefront, respectively. By further splitting
S
c
(
G
) at the nodes, at which the reflex wavefront vertices vanish, we obtain a set of connected subgraphs
M
1
, ...,
M
k
of
S
c
(
G
). We show that each
M
i
is a pruned medial axis for a certain convex polygon
Q
i
closely related to
G
, and give an optimal algorithm for computation of all those polygons, for 1 ≤
i
≤
k
. Here “pruned” means that
M
i
can be obtained from the medial axis
M
(
Q
i
) for
Q
i
by appropriately trimming some (if any) edges of
M
(
Q
i
) incident to the leaves of the latter.