Re:Tutorial for Wykobi – A C++ Computational Geometry Library
by plafl on Tuesday March 07, 2017 @03:10AM
(#13808978)
So 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.
Re:Tutorial for Wykobi – A C++ Computational Geometry Library
by bsder on Tuesday March 07, 2017 @05:36AM
(#13809477)
Au 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
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.
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.