Right, that makes sense. When I asked about rescaling I was wondering about how floating point roundoff affects the consistency of predicates before and after transforming points by a scaling/offset to put the coordinates into the range 1-2. I think what you're saying is that yes, consistency can be changed in rare cases, but it doesn't actually matter for most use cases.
Very cool picture by the way :) On Sat, Oct 11, 2014 at 6:17 PM, Ariel Keselman <skar...@gmail.com> wrote: > Good questions, I think I have some answers: > > 1) The problem using an integer lattice is that Int64s would regularly > overflow. In order to not overflow, for the 2D case, you would need to use > at most 16-bits for coordinate information. Of course it is worse for the 3D > case. So a fast and simple solution is to use Floats :) that way you get 53 > bits of precision for both 2D and 3D. The cost is tracking errors and using > BigInts when needed (hopefully in rare cases only) > > 2) Scaling a set of points preserves the consistency of predicates. This > means that all scaled primitives will agree among them on the > incircle/intriangle tests, and the geometrical algorithms remain robust. I > agree that in rare cases an unscaled incircle/intriangle result may differ > from the scaled one (lets call this "precision"), but I can't think of any > use-case requiring this. Still, in those cases, limiting yourself to the > range 1.0<=x<2.0 would suffice. And you still enjoy the better performance > :) > >