Graphics Reference
In-Depth Information
(1) all the points
p
i
, except possibly the first and last, are distinct, and
(2) no segments [
p
i
,
p
i+1
] and [
p
j
,
p
j+1
], 0 £ i < j < k, intersect unless
(a) j = i + 1, in which case they intersect in the point
p
i+1
, or
(b) the curve is closed, i = 0, and j = k - 1, in which case they intersect in the
point
p
0
=
p
k
.
If
q
Œ [
p
i
,
p
i+1
], then the pwl curve (
p
0
,
p
1
,...,
p
i
,
q
,
p
i+1
,...,
p
k
) is called an
elementary
subdivision
of the pwl curve p and a
proper elementary subdivision
if
q
lies in the inte-
rior of the segment [
p
i
,
p
i+1
]. A pwl curve that is obtained from p by a sequence of
(proper) elementary subdivisions is called a (
proper
)
subdivision
of p.
If we think of pwl curves as defining a path that one walks along, then in the case
of a simple pwl curve there is no backtracking or self-intersection. In particular, a
simple pwl curve traces out a one-dimensional manifold. (See Lemma 15.3.2.1 below.)
Clearly, proper subdivisions of simple curves are again simple.
It is easy to parameterize the path of a pwl curve.
Definition.
Let p = (
p
0
,
p
1
,...,
p
k
) be a pwl curve and let
i
k
i
+
1
È
Í
˘
˙
Æ
[
]
r
i
:
,
pp
,
,
0
£<
ik
,
i
i
+
1
k
be the standard linear map that, using barycentric coordinates, has the form
i
k
s
i
+
1
+
t
Æ+
s t
pp
,
st
,
≥
0
,
st
+=
1
.
i
i
+
1
k
The map
0
[
Æ p
r :,
,
where
i
k
i
+
1
È
Í
˘
˙
=
r
|
,
r
,
i
k
is called the
standard parameterization
of the pwl curve p. If s, t Œ [0,1] and s £ t, then
define a pwl curve q, called the pwl curve
induced by [s,t]
with respect to the standard
parameterization, as follows:
Case s = t:
Set q = (r(s), r(t)).
i
k
i
+
1
j
k
j
+
1
È
Í
ˆ
¯
Ê
Ë
˘
˙
Case s < t:
Define i and j by the condition that
s
Œ
,
and t
Œ
,
.
k
k
If i = k - 1, then q = (r(s), r(t)). Otherwise, q = (r(s),
p
i+1
,
p
i+2
,
...,
p
j
,r(t)).
15.3.2.1
Lemma.
Let p = (
p
0
,
p
1
,...,
p
k
) be a pwl curve and r its standard
parameterization.