Re: [julia-users] ANN: GeometricalPredicates.jl
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=x2.0 would suffice. And you still enjoy the better performance :)
Re: [julia-users] ANN: GeometricalPredicates.jl
+1 Definitely is a cool package, and I noticed the point types as well. I've been meaning to revive the geometry package discussion (again). Tim Holy's PR that Simon pointed to is a key part of that. I'll try to put some more coherent thoughts together this week. Cheers, Kevin On Sunday, October 12, 2014, Simon Danisch sdani...@gmail.com wrote: Hi, pretty cool package =) I saw, that you implemented your own point type. This is exactly the reason, why I pledge for good support of fixed size arrays, with different names and accessors, but all under the same interface. Right now, to use your package with my OpenGL packages, I'd need to write extra functions just to support your custom point type. If they'd be all under the same interface, with all of the linear algebra functions defined on them, it'd become completely painless to integrate your package, and you could still use custom point types with all the accessors you like. Here is a discussion on github concerning this: https://github.com/JuliaLang/julia/pull/7568 Hope we can solve this early on, before the fragmentation becomes even bigger. Best, Simon Am Donnerstag, 9. Oktober 2014 21:34:21 UTC+2 schrieb Ariel Keselman: Fast and robust 2D 3D geometrical predicates. For documentation see here: https://github.com/skariel/GeometricalPredicates.jl This is used in a Delaunay/Voronoi implementation which I'll also package which is faster than CGAL. In addition, it could be used as the basis for a fast and robust geometry library, much like CGAL. read about how here: https://www.cgal.org/philosophy.html
Re: [julia-users] ANN: GeometricalPredicates.jl
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=x2.0 would suffice. And you still enjoy the better performance :)
Re: [julia-users] ANN: GeometricalPredicates.jl
This is pretty cool. Writing a robust set of geometric predicates requires quite an attention to detail. Some questions: Restricting to the float range 1.0=x2.0 essentially makes the input a fixed point representation, with fixed point scaling factor eps(1.0) = 2.220446049250313e-16. How does this compare to telling the user to rescale their variables onto an integer lattice? Using an integer lattice arguably exposes the exact nature of the rescaling a little more clearly though it might just be a pain to work with. I expect that rescaling a set of points fails to preserve geometric predicates between them. If so, a comparison to CGAL performance may not be entirely fair if they keep their vertices in the original position. Having said that, I think it's a totally practical tradeoff - one that I'd certainly be willing to make for a bit of extra speed. ~Chris On Fri, Oct 10, 2014 at 5:34 AM, Ariel Keselman skar...@gmail.com wrote: Fast and robust 2D 3D geometrical predicates. For documentation see here: https://github.com/skariel/GeometricalPredicates.jl This is used in a Delaunay/Voronoi implementation which I'll also package which is faster than CGAL. In addition, it could be used as the basis for a fast and robust geometry library, much like CGAL. read about how here: https://www.cgal.org/philosophy.html
[julia-users] ANN: GeometricalPredicates.jl
Fast and robust 2D 3D geometrical predicates. For documentation see here: https://github.com/skariel/GeometricalPredicates.jl This is used in a Delaunay/Voronoi implementation which I'll also package which is faster than CGAL. In addition, it could be used as the basis for a fast and robust geometry library, much like CGAL. read about how here: https://www.cgal.org/philosophy.html
