[metapost] workaround for turningnumber bug

[Giuseppe Bilotta]

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