On Wed, Apr 23, 2008 at 12:15 PM, Phil Endecott <spam_from_boost_dev@chezphil.org> wrote:
Federico J. Fern?ndez wrote:
In my case, I'll be working in Spatial Indexes with Hartmut Kaiser.
Congratulations Federico. I'll be really interested to hear how you get on.
Here's my spatial index problem of the day: I have a time-ordered series of GPS fixes which I'm inserting into a spatial container. Their locations are highly correlated with time, so I'd like to be able to use a hint to say that each point I insert is adjacent to the previous one (like we can do when inserting into a std::map). If I can find a good way to do this I could improve this code from O(n log n) to O(n), which would be very worthwhile.
I had a very similar problem. I had many thousands of GPS coordinates coming in, with position and time stamp that needed to be spatially indexed so that you could later query for all points within M distance and N hours/minutes/seconds of another spatio-temporal point. I ended up using a Bounding Interval Hierarchy that had a bucket of points at each leaf, rather than a single point at each leaf, and that bucket was sorted temporally (hashed by timestamp). This was because the order I received the points was not necessarily in temporal order. In your case, Phil, it might make sense to reverse the ordering (i.e. hash by time, then use a spatially indexed bucket). A Spatio-Temporal data structure would be a great addition to boost. --Michael Fawcett