Very cool! I also dream of having a good Voronoi code in Julia. What I'm after in particular is dynamic construction (insertion and removal) of power diagrams<http://en.wikipedia.org/wiki/Power_diagram>(a generalization of Voronoi diagrams with weights on the generators). To that end, I started to try to write code to construct the exact conic hull of integer vectors in Julia, the current and very experimental version can be found here <https://github.com/toivoh/ConicHulls.jl>. Once you have the conic hull, it is easy to create Voronoi/power diagrams (also on the sphere). So far I have only addition of generators, but I would like to support removal as well.
My plan is to write the algorithms in a parametrized way so that it is easy to plug in different implementations of generators and predicates, hopefully I could interface your predicates as well, if I'm allowed to. On Monday, 12 May 2014 16:16:21 UTC+2, Ariel Keselman wrote: > > see here: > > https://gist.github.com/skariel/da85943803a6f57a52fd > > it implements fast and robust 2D and 3D orientation and in-circle tests > according to the algorithms described in this paper: > > http://arxiv.org/abs/0901.4107 > > i.e. calculate using regular Floats while constraining the error. If in > danger of getting a bad result repeat using exact calculation. > > this is good to implement fast Voronoy/Delaunay tessellations. See some > usage in the recent biggest cosmological simulation Illustris: > > http://www.illustris-project.org/ > > These should be faster than say- > > http://www.cs.cmu.edu/~quake/robust.html > > which use adaptive precision > > I intend to implement Voronoy algorithms on top of this, some day :) > > Feedback welcome! >
