Re: incremental triangulation for 2D collision detection broadphase
"Simon Fenney" <[email protected]>
| Newsgroups | gmane.games.devel.algorithms |
|---|---|
| Message-ID | <[email protected]> |
[email protected] 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 ------------------------------------------------------------------------------ The Planet: dedicated and managed hosting, cloud storage, colocation Stay online with enterprise data centers and the best network in the business Choose flexible plans and management services without long-term contracts Personal 24x7 support from experience hosting pros just a phone call away. http://p.sf.net/sfu/theplanet-com _______________________________________________ GDAlgorithms-list mailing list [email protected] https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list Archives: http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list