Voronoi.find(x,y)

[Fil]

diagram.find(x,y) returns the closest site to point x,y — in other words a cell that contains said point, except if we are out of the extent. http://bl.ocks.org/Fil/1b7ddbcd71454d685d1259781968aefc

The algorithm is quite simple (I invented it, but probably someone already did before me!). It seems to converge in about sqrt(n) steps, involving a few distance computations each time.

The API is similar to d3-force simulation.find() https://github.com/d3/d3-force/blob/master/src/simulation.js#L116

[Fil]

I have just added a few blocks to demonstrate what I'm trying to achieve:

Compute a voronoi spanning tree

Compute a better spanning tree

Traverse it

[mbostock]

Neat!

[Fil]

Another application: Voronoi binning

[mbostock]

I found a small bug in your optimization. Instead of this:

next = diagram.find.found || Math.floor(Math.random() * diagram.cells.length);

You want to say this:

next = diagram.find.found == null ? Math.floor(Math.random() * diagram.cells.length) : diagram.find.found;

Because sometimes the last-found index can be zero, and you want to treat that differently from it being undefined. Example here: http://bl.ocks.org/mbostock/76d0346147b55a08b91dcccf8da58291

Also, I think diagram._found would be a better place to stash the last-found index than putting it on the diagram.find method, especially since if this is implemented on Diagram.prototype the find function would be shared by all diagram instances.

Do you want to open a pull request to add this feature? Or do you want me to implement your suggested algorithm and add tests?

[Fil]

sometimes the last-found index can be zero, and you want to treat that differently from it being undefined. Example here: http://bl.ocks.org/mbostock/76d0346147b55a08b91dcccf8da58291

Math.random() is useless here — I put it because I tend to like it better when things are evenly distributed, and to highlight that any starting point will work. The only thing is to start with an existing site. On this issue, I wonder if at some point the site with index 0 might disappear, for example when we find a way to constructively add and remove sites from the Diagram. Then we'll need to pop one site from the list.

In the meantime, I think diagram.find.found || 0 is more than enough.

Also, I think diagram._found would be a better place to stash the last-found index than putting it on the diagram.find method, especially since if this is implemented on Diagram.prototype https://github.com/d3/d3-voronoi/blob/master/src/Diagram.js the find function would be shared by all diagram instances.

right

Do you want to open a pull request to add this feature? Or do you want me to implement your suggested algorithm and add tests?

Will start a PR.

-- Fil