[metapost] workaround for turningnumber bug
Giuseppe Bilotta
gip.bilotta at iol.it
Mon Jan 31 17:33:51 CET 2005
Sunday, January 30, 2005 Werner LEMBERG wrote:
> What are the constraints for a curve (P, P+, Q-, Q) so that there is a
> self-intersection?
There is no simple condition that I know of. There are some
rather complex ones, though.
Start by writing the curve in canonical polynomial form
\gamma(t) = K0 + K1 t + K2 t^2 + K3 t^3
(where
K0 = P
K1 = 3 (P+ - P)
K2 = 3 (Q- - 2P+ + P)
K3 = Q - 3 Q- + 3 P+ - P
)
The conditions for self-intersection are given by the existence
of solutions in [0,1] of the equation
(*) (K2 x K3)^2 t^2 +
(K1 x K3)(K2 x K3) t +
(K1 x K3)^2 - (K1 x K2)(K2 x K3) = 0
(where "x" here marks the cross product with the
two-dimensional convention that
v x w = v1 w2 - v2 w1
for v=(v1, v2) and w=(w1, w2)
)
[Proof: solve \gamma(t1) - \gamma(t2) = 0: you will be able to
simplify a t1-t2 (since t1=t2 is always a solution), and
you can write the rest as a set of two equations in t1+t2,
t1*t2, with solutions
t1+t2 = - K1 x K3 / K2 x K3
t1*t2 = [(K1 x K3)^2 - (K1 x K2)(K2 x K3)] / (K2 x K3)^2
Now, we want to have solutions (if two and coincidental, they
give us the cusp time), hence it must be
(a) 4(K1 x K2)(K2 x K3) - 3(K1 x K3)^2 >= 0
(I call this the "knot factor" of the curve).
We want both the solutions to be >= 0, so it must be
(b) (K1 x K3)(K2 x K3) <= 0
(c) (K1 x K3)^2 - (K1 x K2)(K2 x K3) >= 0
(because of Pascal's rule of signs). The solutions must also be
<= 1, so it must be
(d) (K1 x K3)(K2 x K3) + 2(K2 x K3)^2 >=0
(e) (K2 x K3)^2 + (K1 x K3)(K2 x K3) +
(K1 x K3)^2 - (K1 x K2)(K2 x K3) >=0
(Why? Because if t1, t2 are the solutions of
a t^2 + b t + c =0
then 1-t1 and 1-t2 are the solution of
a t^2 - (b + 2a) t + (a + b + c) = 0
and again for Pascal's rule of signs)
The required conditions are (a-e) above, which I have not been
able to simplify in any sensible way. IMHO it's easier to just
solve (*) (if (a) is verified) and then check manually if the
solutions are both between 0 and 1.
OTOH, notice if
K2 x K3 = 0
the conditions simplify to
-2 <= (K1 x K2 / K1 x K3) <= -1
(I haven't checked what kind of curve is this, though)
HTH (and let me know if I busted some of the math in there ...
I often do)
--
Giuseppe "Oblomov" Bilotta
More information about the metapost
mailing list