search

d3 / d3-delaunay

Compute the Voronoi diagram of a set of two-dimensional points.
https://d3js.org/d3-delaunay
ISC License
611 stars 57 forks source link

Adding points incrementally without retriangulating #105

Closed Kebabrulle4869 closed 4 years ago

Kebabrulle4869 commented 4 years ago

Hello!

I've been using this library for my "gymnasiearbete", a final work during Swedish high school, and I've had great success in doing so. However, I can't quite figure out how to add points incrementally to the triangulation without redoing the entire thing. I'm guessing that this is possible with this library somehow, based on the demo. I would imagine you're using some functionality I've missed in the library, and if you're not and you're just retriangulating after every new point, I think a function that could add a single point quickly to an existing triangulation would be very welcome.

More specifically, I'm using this library to randomly place points in the plane with a minimum distance between them. Using this library, I can make a triangulation of the existing points, then find the nearest point to the new candidate point, and check the distance between them. I think this would be more effective if I could figure out how to add points incrementally, and be able to execute other functions between adding points. I've already tried using .update(), but it seems to only work when moving points, not adding points.

Sorry if this is the wrong place to ask this sort of thing - I'm not too familiar with using github, and thank you in advance.

mbostock commented 4 years ago

I don’t think that’s possible with the sweep-line algorithm used by this library, but the place to file this request would be over in mapbox/delaunator.

mbostock commented 4 years ago

(Also this library is very fast, so unless you have a lot of points, recomputing the triangulation from scratch is unlikely to be a problem.)

Fil commented 4 years ago

A small addition: if you want to use delaunay.update(), it's true that you need to make sure that the number of points does not increase. But it doesn't means you can't "add" points: the trick is to reserve enough space by instantiating the coordinates array with enough duplicates of (for instance) the first point; then you can inject the new points in those reserved slots.