Re: [Algorithms] incremental triangulation for 2D collision detection broadphase

[Ben Sunshine-H. <sn...@gm...>]

On Tue, Feb 2, 2010 at 7:54 PM, Samuel Moll <sam...@go...> wrote:
> What I need now is an (efficient :D) algorithm for updating the
> triangulation when the points move. i.e. given a valid triangulation
> (no triangles overlap, triangulates the convex hull of all points) and
> movement vectors for all points, how can I "repair" the old
> triangulation?

Take a look at "Voronoi Diagrams of Moving Points", link below.
Remember that the Voronoi tessellation is the dual of the Delaunay
triangulation, which in general tends not to produce many slivers.

http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.45.8944

Ben