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

[Simon F. <sim...@po...>]

Pau...@sc... wrote:
> -----BEGIN PGP SIGNED MESSAGE-----
> Hash: SHA256
> 
>> The triangulation is maintained incrementally -- normally it doesn't
>> change, so it only needs to be checked if it is still valid every
>> frame. If it changes, it only needs to be recalculated partially.
>> This is an O(n+something for the changed part) operation.
> 
> 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?  

Drifting a bit OT, but from what I've read, the O(n) triangulation
algorithm of simple polygons is said to be very complicated. Although
wikipedia does have a link to a claimed simple, linear time,
triangulation algorithm, until I someone posts a copy of the paper that
is in English, I'll take it with a grain of salt. :)

FWIW, there are O(n log* n) algorithms (the star is important) which are
fairly simple to implement and are pretty much indistinguishable from
O(n). 

Again, apologies for going a little OT.

Simon