CS Grammar

[mje]

Hi Gang,

I need some help with some computer science grammar.

Say I have a 2D surface and an array of rectangles in that geometry. For an arbitrary coordinate I need to determine which rectangle, if any, contains the coordinate.

I have a simple solution that just tackles it via brute force, and it works just fine because I typically don't have to track more than a thousand features.

However I think this is a good learning experience. I imagine how one can do much better than iterating over each element by building a branching data structure and stepping through the hierarchy. I know this is a common problem in math and CS but I have no idea what this is called, so I'm not having much luck with blind searching. Does anyone at least know the name of what it is I'm trying to do?

[Phillip Brooks]

I have no idea, but I did read this post on the dark side just the other day and wondered what the heck a quadtree was...

[mje]

Thanks Phillip! That quadtree is pretty much what I imagined in a 2D space. New words are fun!

What I'm really after I imagine is simply extending a binary search into N-dimensions, but the fact that's I'm dealing with areas, volumes, or N-dimensional volumes does add a slight kink. That seems like a good start.

[ShaunR]

I've not come accross Quad-tree but I have come accross R-Tree

Edited March 23, 2012 by ShaunR

[mje]

Nice. I had no idea there was a built in optimized index for that in SQLite. That should be very interesting to explore...