[metapost] workaround for turningnumber bug
Giuseppe Bilotta
gip.bilotta at iol.it
Sun Feb 6 00:12:57 CET 2005
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
More information about the metapost
mailing list