Re: [boost] Congratulations to the Successful Summer of CodeStudents!

From: Michael Fawcett (michael.fawcett_at_[hidden])
Date: 2008-04-23 15:24:49

On Wed, Apr 23, 2008 at 12:15 PM, Phil Endecott
<spam_from_boost_dev_at_[hidden]> 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