search

mapbox / delaunator

An incredibly fast JavaScript library for Delaunay triangulation of 2D points
https://mapbox.github.io/delaunator/
ISC License
2.33k stars 142 forks source link

Speed up #22

Closed photopea closed 6 years ago

photopea commented 6 years ago

My program works in steps: I update the set S of 2D points, and then I need a triangulation of S. Your library works well, but it is a bit too slow for my case.

In each step, I update only a small subset of points of S (they usually lie in a circle). I was thinking, that maybe I could compute a triangulation for this subset of S, and then, combine it with an old triangulation of the whole S.

Do you think your library could be extended in this way?

mourner commented 6 years ago

What you're looking for is incremental triangulation — there are libraries for this, e.g. this one. Delaunator is designed for static use cases.

photopea commented 6 years ago

I always need to comptue a triangulation for the same number of points. I just "move" some of them.

The library that you mentioned does not allow removing points (I thought I could remove the old position of some point and insert a new position). What is your idea about using that library in my case?

BTW. I am the author of PolyK.js :) I made it like 6 years ago.