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

[Samuel M. <sam...@go...>]

> I thought triangulation was a O(n^2) problem at least? (looks it up on
> wikipedia) ahh, i see there is talk of triangulating a simple polygon in
> O(n), but i'm not sure a connected graph of all objects constitutes a
> simple polygon?

You can do Delaunay-Triangulation in O(n*logn), but the point is that
I need to maintain a triangulation of moving points -- that's entirely
different from constructing one from scratch.

> The most important thing to keep in mind is that a good broad-phase
> algorithm should do zero work when nothing moves in the world.
> Are all your objects always moving in your world? How many objects are you
> talking about?

I should have mentioned that I'm writing a 2D space shooter, so all
the objects are moving all the time. And I'll have like 200 objects or
so.

Samuel