Performance about d3-geo-voronoi HOT 10 CLOSED

Here's a notebook that seems to work, built on top of d3-delaunay. https://beta.observablehq.com/@fil/geo-delaunay

Computations are several orders of magnitude faster than the current d3-geo-voronoi.

(The notebook is not that fast, because rendering is slow.)

from d3-geo-voronoi.

See if we can apply the sweep-hull technique of https://github.com/mapbox/delaunator / https://github.com/d3/d3-delaunay to our 3D model. Or use D. Sinclair's newer algorithm https://arxiv.org/pdf/1602.04707.pdf

from d3-geo-voronoi.

I added a mesh computation to my notebook, too. Edit: Ah, I see you’d already done this, too, and that I can simplify my code. 👍

from d3-geo-voronoi.

Nice! I massaged your code a little bit to construct the spherical Voronoi of the Fibonacci lattice. It does seem to be a little brittle depending on the inputs—perhaps because I broke something in my attempts to “simplify” the code—but I’m excited to see your progress here!

https://beta.observablehq.com/@mbostock/spherical-voronoi

from d3-geo-voronoi.

Do you mean when n is small? This should be fixed now — in the sense that the code shouldn't break anymore when n <= 3.
https://beta.observablehq.com/@fil/spherical-voronoi

I'm still working on the n=3 case to build the correct polygons (LineStrings connecting antipodal points… that doesn't work well).

from d3-geo-voronoi.

I think I just borked something in my simplification of your code. I switched to importing your notebook directly (using with {points} to replace the input) and it works great!

from d3-geo-voronoi.

My code from yesterday was not working that well :-) There are quite a bit of difficult issues when n is small and the points are clumped together in one spot.

from d3-geo-voronoi.

I think I've solved the outstanding issues (edge cases with n=1, 2 and 3)
https://beta.observablehq.com/d/85fbdef16ebd12aa

Now, to add sugar…

from d3-geo-voronoi.

In terms of capacity, it looks like the maximum on my computer is n = 125578 points. The polygons are still computed in a few seconds.

I don't know why it breaks with n = 125579, observable catches the error and the console does not report. Not d3-delaunay's fault, it can go much higher than that (10 million points and more).

Edit: "RangeError: Maximum call stack size exceeded."

Edit: fixed!

from d3-geo-voronoi.

I just published release 1.0.0 based on d3-delaunay (wooohooo)

from d3-geo-voronoi.