4 ms·
> My understanding is that all operations are carried numerically and the only way that would prevent accumulation of errors would be to perform them symbolical
by bsder 10y ago
> My understanding is that all operations are carried numerically and the only way that would prevent accumulation of errors would be to perform them symbolically and solve them numerically just at the end but I suppose that would be extremely inefficient.
You can solve the problem with extended integers, but not as easily as you would expect. In 2D, it takes something like 2n+logn bits of computation to accurately calculate things for n bits of coordinates. So you need more than 70 bits just to calculate 32 bits accurately. And we almost always need 64 bits, nowadays.
And this requires "binning" which breaks things like measurements of "parallel". It's not an easy problem, and it requires lots of test cases.
- plafl 10y agoSo basically the most accurate approach that is near something practical is using arbitrary precision. What I was wondering is if there is any implementation capable of detecting for example that the three bisectors of a triangle meet exactly at the same point, the incenter. My guess is that maybe for pedagogical purposes but not for anything more complex.
- bsder 10y agoAu contraire. It's quite useful and you can handle more complex things. "Practical Segment Intersection with Finite Precision Output" http://ect.bell-labs.com/who/hobby/93_2-27.pdf http://ect.bell-labs.com/who/hobby/93_2-27.pdf The problem is that once you start dealing with the actual coordinates of intersections, you have to start picking what properties you wish to keep and which you wish to abandon. Things like parallelism, inside vs outside, winding, handedness, etc. often get very murky once you start dealing with finite precision.