News for hackers. Stuff that matters.
Re:Tutorial for Wykobi – A C++ Computational Geometry Library by alkonaut on Monday March 06, 2017 @05:51AM (#13801867)
So long as you are using floating point, most bets are off. What you can do with FP is use exact predicates which are always correct. That might, for example tell you if two lines intersect, or if a point is inside/outside a polygon without precision issues.

The problem with that is that you will soon want to construct geometrical entities. For example, if you intersect lines that have their ends on integer coordinates you can't represent the intersection on integers (You will need rationals, in that case). The same applies to floating point - two line segments with floating point coordinates will not have their intersection representable in floating point.

So for proper robustness in all situations you need "exact predicates and exact constructions". A middle ground is "exact predicates and inexact constructions". These modes are different kernels usable in e.g. CGAL. http://doc.cgal.org/latest/Kernel_23/group__kernel__predef.h...

Even something seemingly simple such as saying "is point C to the left or right of the line A->B" is very hard in floating point. It's possible without too much sweat to use kind of series expansion where the length of the expansion depends on the precision needed (you only go as far as you need to answer the predicate, so often only 2-3 terms) https://www.cs.cmu.edu/~quake/robust.html

Re:Tutorial for Wykobi – A C++ Computational Geometry Library by deadsy on Monday March 06, 2017 @10:43AM (#13803368)
>Even something seemingly simple such as saying "is point C to the left or right of the line A->B" is very hard in floating point.

Is it? ie - construct a normal and take a dot product. That'll work the vast majority of the time. Near the line you'll start running into the FP precision limits. With 64 (...or even 32) bit floats that sort of distance is likely way smaller than anything that represents a practical distance, so just call it and say you are on the line. Of late I've been messing about with problems of this nature and I can't say it's been all that difficult. https://github.com/deadsy/sdfx

Re:Tutorial for Wykobi – A C++ Computational Geometry Library by alkonaut on Monday March 06, 2017 @12:28PM (#13804258)
It comes back to bite you in a hurry. You don't need arbitrary precision to represent arbitrarily small things but to not have algorithms break down. Simple things like "is p inside the polygon" changes from true to false by moving both point and polygon 1 unit to the right. See under the heading "geometric predicates can FAIL" here http://groups.csail.mit.edu/graphics/classes/6.838/S98/meeti...

You are right that this happens only in edge cases. But you don't want that in a cad program if you have anything doing e.g point-in-polygon, triangulation or other such algorithms.

I know from experience that you really should bake this into the very foundation of a cad package (if you see 2003 me, let him know)

Re:Tutorial for Wykobi – A C++ Computational Geometry Library by willangley on Monday March 06, 2017 @01:00PM (#13804567)
The link didn't work when I tried it. I found "Robust Predicates and Degeneracy" with a search: http://groups.csail.mit.edu/graphics/classes/6.838/S98/meeti...
Re:Tutorial for Wykobi – A C++ Computational Geometry Library by alkonaut on Monday March 06, 2017 @01:06PM (#13804617)
Thanks, not sure why my iOS clipboard pasted a link I copied a week ago... (corrected the link now)