Voronoi diagram

[mourner]

Shouldn't be too much work to extend Delaunator to calculate a Voronoi diagram after triangulation.

[mbostock]

I’ve mostly got this working, using the connect-circumcenters technique, and I hope to share something soon.

The blue edges are the special cases for the hull. My remaining tasks are to clip the line segments to the viewport using Liang–Barsky and then to connect the appropriate line segments into polygons (while introducing edge segments due to the viewport clipping).

[mourner]

@mbostock this looks great, looking forward to the code!

[mbostock]

Haven’t had much time to work on this lately as I have been focusing on Observable. But, I have created a voronator repo where I will share my work as I go. Here’s my initial code for drawing the Voronoi diagram (but not yet clipping and stitching it):

https://github.com/observablehq/voronator/blob/v0.0.1/index.js

[redblobgames]

Note that delaunator has a circumcenter function but doesn't expose it. You and I both ended up writing our own. :-) For my use case I didn't need to clip the line segments (the hard part) and I got away with only having to do the easy part (traversing the half edges). Looking forward to having voronator for future projects.

[mourner]

@mbostock this looks great, thanks for sharing! I didn't realize there would be so few lines of code.

Re circumcenters — I'm thinking of adding a method to precalculate all circumcenters and circumradii into another public flat array. This is helpful not only for Voronoi but for some other algorithms like alpha shapes as well.

[mbostock]

I’ve got this working, hooray! 🎺

I’ll publish an Observable notebook and a README soon. Here is the code:

https://github.com/observablehq/voronator/blob/master/src/index.js

My remaining tasks are primarily performance optimizations and documentation. The gist of it is:

let delaunay = new Delaunator(points);
let voronoi = new Voronator(delaunay);

From there, you can look at voronoi.cells, and each cell has an array cell.triangles which is similar to delaunay.halfedges. The triangle indexes can be used with delaunay.triangles or voronoi.circumcenters.

There’s also a cell.path(context) method which is provided for convenient rendering. I might add an additional method for materializing the coordinates of the clipped cell polygon but I’m not sure such an API is needed. (You can use cell.path in conjunction with d3-path to render to SVG; I’ll probably just have cell.path return an SVG string if you don’t pass in a context.)

Stay tuned!

[mourner]

@mbostock really excited to see this! Thank you so much for sharing! Looking forward to a notebook and some projects based on it too. :)

[mourner]

This is now live at https://github.com/d3/d3-delaunay! 🎉

However I'd like to keep the issue open — the more I think about this, the more it seems to make sense to have all the pure Voronoi diagram logic (without clipping/rendering stuff) moved from d3-delaunay to Delaunator. Specifically, cell generation I wrote here https://github.com/d3/d3-delaunay/pull/23, and keeping flat cell data as described here https://github.com/d3/d3-delaunay/issues/24. @mbostock would you be open to this kind of refactoring?

[redblobgames]

Cool! Would this code work if the circumcenters array were different points (e.g. centroids or some other type of triangle center)?

[mourner]

On a second thought, maybe that's not necessary. Perhaps it's better to just expose more helper functions like getCircumcenters, getCircumradii, prev/nextTriangleEdge, prev/nextVertexEdge — this will make it easier to traverse the triangulation and do things like drawing Voronoi cells.

[mourner]

@redblobgames I think so. A cell is basically a collection of triangles around a vertex, and when you have those, you can connect them differently (although infinite edges / clipping / etc. would need a special handling).

[torvalamo]

I assume that every triangle at some point has its circumcenter calculated during the triangulation, so why not just also store that in its own array (where [n] is the circumcenter coordinates [x,y] of the triangle starting at [3n])? There shouldn't be a need to calculate it several times for the same triangle...

[mourner]

@torvalamo no. Delaunator only calls inCircle tests on every triangle. I tried adding circumcenter precalculation by default but it brings a significant performance overhead.

Closing the issue since the original issue was addressed by d3-delaunay.