Performance

[Fil]

Loren Petrich's lib uses an algorithm that seems to be in O(n^2). It is unpractical for n > 1000. (d3-voronoi runs in O(n) log(n).)

See http://bl.ocks.org/Fil/704bdbac80ab2e5d741d5fa3662bdf82

Three possibilities:

• 1. “I'm sorry, Dave, I'm afraid I can't do that”: let geoVoronoi() log a warning if n > 500 (10s on my computer) and return an error if n > 2000 (2.5 min).
• 2. Switch to an approximate algorithm when n > 500 (If we accept bugs around the poles, we can piggy-back on d3-voronoi by using a specific cylindric projection.)
• 3. Find and implement a better algorithm.

[Fil]

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

[Fil]

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

[mbostock]

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

[Fil]

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

[mbostock]

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!

[Fil]

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.

[Fil]

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…

[mbostock]

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. 👍

[Fil]

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!

[Fil]

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