[metapost] workaround for turningnumber bug

[Giuseppe Bilotta]

Friday, February 4, 2005 Werner LEMBERG wrote:

>> \gamma(t) = K0 + K1 t + K2 t^2 + K3 t^3
>>
>> 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
>>
>> 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.

> Your formulae are very useful, thanks!  What about the following: We
> either have two different solutions (a real self-intersection) or a
> double-solution (a cusp) in (*):

>                      +           +
>              ---------+---------+---------
>                         +     +
>                            +

>                      +           +
>                       +         +
>                         +     +
>              --------------+--------------


> The first derivate of (*), set to zero, gives the point where the
> tangent is parallel to the x axis, and this point must be in the
> interval ]0,1[, between the two solutions.  After some simple math we
> have the constraint

>           K1 x K3
>     0 < - ------- < 2
>           K2 x K3

> as a quick first test whether a self-intersection does exist.

I'm starting to explore the magic of reciprocals, since it
helps reducing the number of relations :) For example, your
relation can be written as

(K2 x K3)/(K1 x K3) < -1/2

which is a single test.

Likewise, we can use this reciprocal property to reduce by one
the number of complete conditions. Indeed, since a number is in
]0,1[ iff its reciprocal is > 1, the conditions for the
solutions of

a t^2 - b t + c

to be "time parameters" can be written as

2 a / ( b \pm \sqrt{b^2 - 4ac} ) > 1

or

(b \pm \sqrt{b^2 - 4ac})/2c > 1

In our case we have a > 0, so it must be b > 0, c > 0 and

b - \sqrt{b^2 - 4ac} > 2c

or again

\sqrt{b^2 - 4ac} < b - 2c

which means

b-2c > 0
b^2 - 4ac < b^2 - 4bc + 4c^2

or

2c < b < a+c

Putting it all together, we must have

b^2 - 4ac > 0

0 < 2c < b < a+c

which is one condition less than in my previous mail (still
pretty long though ...)

-- 
Giuseppe "Oblomov" Bilotta