2d collision data structure question

Original Post

Jan 22, 2008 at 2:47 AM

Hi I have a large set of arbitrary rectangles and I have to test them all against a given rectangle for collision FAST. Does anyone know an efficient data structure and/or algorithm to do this? I want to avoid looping thru the whole rectangle database, so they have to be sorted somehow. Dividing the whole region into subregions would be one solution, but I wonder if there are other solutions that lead to near-logarithmic complexity.

Falken42

Jan 22, 2008 at 3:34 AM

Sounds like a quadtree would be perfectly suited for this.

Edit: Also found a nice Flash demo showing quadtree processing running in realtime. There are lots of other good links, just Google. :)

riserbar

Jan 22, 2008 at 4:53 AM

Rectangle quadtree seems to be what I needed, thanks! :)

Topic Locked