ANN: GeometricalPredicates.jl

[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

[Iain Dunning]

Would be nice to have this registered in METADATA.jl when you get a chance!

[Stefan Karpinski]

Yes, this looks very nice.

[Ariel Keselman]

just opened the PR for METADATA.jl

[Chris Foster]

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<=x<2.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

[Ariel Keselman]

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 :)

[Simon Danisch]

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

[Kevin Squire]

+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 

[Job van der Zwan]

On Thursday, 9 October 2014 21:34:21 UTC+2, Ariel Keselman wrote:

This is used in a Delaunay/Voronoi implementation which I'll also package which is faster than CGAL.

Any updates on this? Also, would it support weighted voronoi maps?

[Ariel Keselman]

The Delaunay/Voronoi package is almost ready. All functionality is in place, in a few days I'll publish (when I manage to write some basic documentation and better tests)

Weighted Voronoi is definitely in the todo list :)

See attached image created with this package, and this post for some more info

[Stefan Karpinski]

That image is so cool!

[Jason Merrill]

Agreed, that is a very cool image. But what is at the center of the voronoi cells that are not inside the logo? Did you add some random points or something?

[Chris Foster]

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 :)

[Job van der Zwan]

Fantastic!

Question: how does the algorithm that you used compare to Fortune's algorithm in the 2D case?

By the way, since we're on the topic of Voronoi diagrams: I happened across this algorithm for quickly computing Voronoi treemaps by Arlind Nocaj and Ulrik Brandes. Java implementation here, JavaScript version here. Might make a cool plotting addition?

[Ariel Keselman]

About the image - it's all random points, the text has higher density of them

A comparison with Fortune's algorithm - the Julia implementation is somewhat faster than CGAL, and CGAL is faster than Boost Voronoi which uses Fortune's algorithm, see here: http://www.boost.org/doc/libs/1_56_0/libs/polygon/doc/voronoi_benchmark.htm

Treemaps - I agree it is a very nice plotting addition, it can be implemented once we have weighted generators. It should belong to a different package though...

[Job van der Zwan]

On Tuesday, 14 October 2014 14:44:06 UTC+2, Ariel Keselman wrote:

A comparison with Fortune's algorithm - the Julia implementation is somewhat faster than CGAL, and CGAL is faster than Boost Voronoi which uses Fortune's algorithm, see here: http://www.boost.org/doc/libs/1_56_0/libs/polygon/doc/voronoi_benchmark.htm

 
I'm officially hyped.

[Simon Byrne]

Very cool package, I learnt quite a bit about computational geometry.

I was trying to think about how you could avoid the BigInt calls. As I understand it, for 2d orientation checks, you need to compare:

(ax - cx)*(by - cy) vs. (ay - cy)*(bx - cx)

If you're restricting yourself to values on the interval [1.0,2.0], then the subtraction operations are all exact. For the multiplications, you can then either use double-double arithmetic [1], or convert to Int64s and use widemul to get an exact Int128 value.

Of course, this doesn't work directly for the incircle or 3d checks, but this might be a good reason for me to implement triple- and quad-double arithmetic...

-Simon

[1] https://github.com/simonbyrne/DoubleDouble.jl

[Stefan Karpinski]

I wonder if the relatively new Ufixed8 types would be useful here. They use integer operations but present a convenient real-number interface.

[Job van der Zwan]

On Tuesday, 14 October 2014 14:44:06 UTC+2, Ariel Keselman wrote:

Treemaps - I agree it is a very nice plotting addition, it can be implemented once we have weighted generators. It should belong to a different package though...

Oh certainly, just thought I'd share.

BTW, near the end of the linked paper the authors also a nice little speedup heuristic for Lloyd's algorithm when using weighted generators - they claim it has about 70% faster convergence.

[Ariel Keselman]

Traits/Interfaces can easily solve the redefinition of points in geometry packages. All I want is to use something that has getx and gety, I don't rally care about the it's type hierarchy! see for e.g. this: https://github.com/mauro3/Traits.jl

About replacing BigInts with (some small number) X 64 bit ints -- so the thing is tha BigInts are not the bottleneck here since they are only rarely used... so I think it won't pay for the effort