Intersections of two lines - limited precision problem
Void
I need a very precise algorithm for determining the intersection point of
two lines. The lines are given by their endpoints.
Obviously, I can calculate it using something like the below
http://local.wasp.uwa.edu.au/~pbourke/geometry/lineline2d/
but the result is very inprecise when calculated on a computer using 32-bit
floating point numbers due to limited precision.
Is there another (possibly slower, but more accurate) way?
Thanks in advance!
Dave Eberly
Represent the 32-bit floating-point endpoints as exact rational
numbers. Use exact rational arithmetic to compute the intersection
(if any). Naturally, if the endpoints were generated by an inexact
process (that is, the endpoints have some error from the "true" values),
then the exactly computed intersection is still considered to have "error"
in it.
--
Dave Eberly
http://www.geometrictools.com
Nicolas Bonneel
Hi,
what do you mean by "very inprecise" ? Do you mean that you have an
error of 10^-8 and you cannot tolerate that in your particular
application, or do you mean that you have an error of 5 in most cases
(ie. non almost parallel lines) which would just mean you have a bug ?
--
Nicolas Bonneel
http://www-sop.inria.fr/reves/Nicolas.Bonneel/
Void
> of 10^-8 and you cannot tolerate that in your particular application, or
> do you mean that you have an error of 5 in most cases (ie. non almost
> parallel lines) which would just mean you have a bug ?
>
Somewhere around 10^-5 to 10^-4 for coordinates in range +/-100, also
depending on the compiler settings (I was shocked to find that compiling the
release version of C++ project in MS Visual Studio by default causes it to
handle floating point numbers less precisely, but that's somewhat besides
the point, I'd like to improve the accuracy regardless of the compiler)
Kaba
> Somewhere around 10^-5 to 10^-4 for coordinates in range +/-100, also
> depending on the compiler settings (I was shocked to find that compiling the
> release version of C++ project in MS Visual Studio by default causes it to
> handle floating point numbers less precisely, but that's somewhat besides
> the point, I'd like to improve the accuracy regardless of the compiler)
Hmm.. Wouldn't that be easily achieved by using double-precision
floating point?
mike
left hand side of the '=' sign is precisely equal to the formula on the
right hand side. I think that if you want more precision, then all you
can do is move from 32 bit fp to a more precise fp number such as IEEE
754 decimal64 or decimal128, which should give you an answer that is
correct to in the region of 15-16 and 33-34 decimal places respectively.
If you need better accuracy then there are 'bignum' packages available
in most languages that can provide you with answers to arbitrary
precision.
Note that in the real world, decimal128 is probably sufficient to
calculate the intersection of arbitrarily positioned lines on a plane
anywhere in the visible universe (i.e. within a circular region roughly
13 billion light years in radius) to an accuracy of approximately +/- 10
nanometres so, unless you have 'unworldly' requirements for precision,
this (sometimes known as 'extended' precision) should be sufficient for
most practical purposes.
Mike
Void
news:MPG.25596e789...@news.cc.tut.fi...
> Hmm.. Wouldn't that be easily achieved by using double-precision
> floating point?
>
It would, but at this point I'm exploring other solutions.
Although double is more precise, IMHO it's still better to have more precise
algorithms in case errors start accumulating.
Kaba
> It would, but at this point I'm exploring other solutions.
> Although double is more precise, IMHO it's still better to have more precise
> algorithms in case errors start accumulating.
Ok. What kinds of figures are you getting for the errors?
Clement Courbet
You may be interested in this article, which adresses a slightly more
difficult problem, but nevertheless has the idea:
Fast, Exact, Linear Booleans
Gilbert Bernstein and Don Fussell
else, CGAL (http://www.cgal.org) does exact intersection
(http://www.cgal.org/philosophy.html).
--
Cl�ment Courbet
Lorenzo Gatti
> Although double is more precise, IMHO it's still better to have more precise
> algorithms in case errors start accumulating.
If your application accumulates errors until they become a problem,
you should use exact rational numbers: wider floating point merely
limits the precision problems to a smaller class of worst cases, and
proving or ensuring that they cannot happen might be more expensive
than straightforward and low-performance calculations.
The required number of digits in rational numbers might (at worst)
double at every arithmetic operation, but often the blowup stops and
at some point you might be able to harmlessly round values with a
known (acceptable) error; for example you might round screen-space
coordinates to whole pixels.
Regards,
Lorenzo Gatti
Nils
> If your application accumulates errors until they become a problem,
> you should use exact rational numbers: wider floating point merely
> limits the precision problems to a smaller class of worst cases, and
> proving or ensuring that they cannot happen might be more expensive
> than straightforward and low-performance calculations.
Amen..
> The required number of digits in rational numbers might (at worst)
> double at every arithmetic operation, but often the blowup stops and
> at some point you might be able to harmlessly round values with a
> known (acceptable) error; for example you might round screen-space
> coordinates to whole pixels.
I've tackled the same problem in a different way. Instead of using
rational numbers I mapped the floating-point input data to integers
normalized to 2^30.
With integers it's easy to keep track of reminders, and you never run
into any precision problems.
I did that for a polygon tesselation algorithm for GIS applications.
With my input data normalized to 2^29 I got a granularity of roughly 12
centimeters with respect to the circumflex of this planet. Worked for me.
If I at one day I get a call that the library fails I'll just raise the
precision to 63 bit and call it a day.
Nice side-effect: The software run on a low-end portable ARM system
without floating-point unit. Solving everything in integers not only
solved all my precision problems but gave a nice speedup as well.
Performance on a modern PC ain't shabby either.
Cheers,
Nils Pipenbrinck
Btw - I played with the idea to map my coordinates into a space that
maps the order of the coordinates along the two axis to integers while
preserving convexity of the edges. That way I would have been able to
deal with integers of much smaller range as the range is not fixed
anymore but now depends on the number of vertices and the shapes convexity.
Unfortunately I never had the time to work out the details of this
coordinate transformation, but I'm still sure it would work and let me
solve all practical tesselation problems for GIS applications without
ever going beyond basic 32 bit integer arithmetic.