Hi Denis,
That sounds like some very good ideas for making this method very accurate.
On the other hand, we're starting to get into the territory where an
advanced math package should be catering to these requirements. The
solveCubic was an internal helper function for implementing the hit
testing methods that I decided to make public back in 1.2 days. There's
a question on how much accuracy we should bother with.
Also, I wrote new hit testing code in jdk6 that used bezier recursion to
compute the values and it ran way faster than any root-finding methods
(mainly because all you have to worry about is subdividing enough that
the curve can be classified as above, below, or to the left or right and
you're done), so the containment methods could probably be fixed by
simply using the new code in sun.awt.geom.Curve and this method could be
updated with the new equations you found and left as an "approximate
method" like it always has been?
...jim
On 12/14/2010 5:57 PM, Denis Lila wrote:
Hi Jim.
How big are these errors expressed as multiples of the ULP of the
coefficients? Obviously 1e-17 is a lot smaller than 1e-4, but was
1e-17
representing "just a couple of bits of error" or was it still way off
with respect to the numbers being used? And were these fairly obscure
equations that were off?
The coefficients I used were eqn={-0.1, 0, 1, 1e-7} so compared to the ulps
of the coefficients, 1e-4 is pretty large.
I'm about to go now, but I would like to write this idea first:
it seems to me like the number of roots reported is much more
important than whether their accuracy is 1e-4 or 1e-17. So,
how about we solve for the roots of the derivative (which can be
done very quickly). Computing lim{x-->+/-inf}f(x) is very easy
(just a test on the most significant coefficient). We can then
evaluate the polynomial on the critical points and this would
allow us to very quickly compute the exact number of roots. If
the number computed using the closed form formula does not
match the real number, we do some refining work.
If we really wanted to optimize, we could also record how close
constants like D and q are to 0, and if they're within a certain
threshold, we could mark the roots they spawn as "suspicious",
and only do the test in the above paragraph (i.e. solving for
critical points) if there are suspicious roots. And if the
computed numbers of roots don't match up, we could concentrate
on refining only the "suspicious" roots.
Regards,
Denis.
