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?