-
Notifications
You must be signed in to change notification settings - Fork 65
Voronoi.find(x,y) #17
Comments
Neat! |
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? |
In the meantime, I think
-- Fil |
diagram.find(x,y)
returns the closest site to pointx,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#L116The text was updated successfully, but these errors were encountered: