| Computers Forum Index » Computer - Graphics (Algorithms) » Intersections of two lines - limited precision problem... |
|
Page 1 of 1 |
|
| Author |
Message |
| Void... |
 Posted: Mon Nov 02, 2009 8:31 pm |
|
|
|
Guest
|
Hi all,
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! |
|
|
| Back to top |
|
|
|
| Dave Eberly... |
| Posted: Mon Nov 02, 2009 11:31 pm |
|
|
|
Guest
|
"Void" <x at (no spam) y.z> wrote in message news:hcmu49$bss$1 at (no spam) news1.carnet.hr...
Quote: 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?
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 |
|
|
| Back to top |
|
|
|
| Nicolas Bonneel... |
| Posted: Tue Nov 03, 2009 12:03 am |
|
|
|
Guest
|
Void a écrit :
Quote: Hi all,
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!
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/ |
|
|
| Back to top |
|
|
|
| Void... |
| Posted: Tue Nov 03, 2009 1:01 am |
|
|
|
Guest
|
Quote: 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 ?
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) |
|
|
| Back to top |
|
|
|
| Kaba... |
| Posted: Tue Nov 03, 2009 1:32 am |
|
|
|
Guest
|
Void wrote:
Quote: 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?
--
http://kaba.hilvi.org |
|
|
| Back to top |
|
|
|
| mike... |
| Posted: Tue Nov 03, 2009 1:46 am |
|
|
|
Guest
|
In article <hcndu1$41o$1 at (no spam) news1.carnet.hr>, x at (no spam) y.z says...
Quote: 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 ?
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)
The formula is 'exact' in the mathematical sense that teh number on the
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 |
|
|
| Back to top |
|
|
|
| Void... |
| Posted: Tue Nov 03, 2009 1:49 am |
|
|
|
Guest
|
"Kaba" <none at (no spam) here.com> wrote in message
news:MPG.25596e789a649466989870 at (no spam) news.cc.tut.fi...
Quote: 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. |
|
|
| Back to top |
|
|
|
| Kaba... |
| Posted: Tue Nov 03, 2009 2:38 am |
|
|
|
Guest
|
Void wrote:
Quote: 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?
--
http://kaba.hilvi.org |
|
|
| Back to top |
|
|
|
| Lorenzo Gatti... |
| Posted: Tue Nov 03, 2009 8:52 am |
|
|
|
Guest
|
On Nov 2, 9:49 pm, "Void" <x... at (no spam) y.z> wrote:
Quote: 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 |
|
|
| Back to top |
|
|
|
| Clement Courbet... |
| Posted: Tue Nov 03, 2009 11:46 am |
|
|
|
Guest
|
Void wrote:
Quote: Hi all,
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!
Hi,
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 |
|
|
| Back to top |
|
|
|
| Nils... |
| Posted: Tue Nov 03, 2009 5:07 pm |
|
|
|
Guest
|
Lorenzo Gatti wrote:
Quote: 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..
Quote: 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. |
|
|
| Back to top |
|
|
|
|
