views:

44

answers:

1

I'm putting together a small library that consumes Geographic Information System (GIS) data and allows for fast point in feature, point near feature, and line of sight queries. Much of this data will consist of big areal features with enormous numbers of vertices.

An R Tree variant might work, though I wonder how those perform on the point in areal queries. I also suspect the line of sight queries would destroy most of the performance gains.

A quad tree with variable sized children is the next thing that pops to mind. That would allow linking between various child levels, perhaps, and speed the line of site queries.

Kd trees pop to mind as well, though again, the line of site queries might prove problematic.

So the question is, what algorithm would you recommend?

A: 

Isn't this the sort of thing raytracers use octrees for?

Rafe
Yes, that's in the class of spatial subdivision algorithms that I'm looking at. An octree would be for 3-space, where the equivalent quadtree would be for 2-space. There are also a class of algorithms that organize 2D (or N-d) data better for certain classes of problems. It's those that I'm contemplating.
mousebird