Re: [Lib2geom-devel] Requirements for lib2geom spatial index...

[njh <nj...@nj...>]

On Fri, 20 Apr 2007, Sunburned Surveyor wrote:

> lib2geom spatial index. I want to have these in mind when I start to look at
> the existing quadtree class.
>
> Requirement #1: The spatial index should not be limited to a fixed size.

The existing quadtree does this.

> Requirement #2: The spatial index should offer the ability for efficient
> updates.

It does this.

> Requirement #3: The spatial index should present a simple API for its basic
> functionality. In other words it shoud have a method that accepts a
> rectangle or envelope and returns a list of the geometries that are
> contained or intersected by that argument.

And this.

> What do you guys think? Am I missing anything?

>From the manual:

\chapter{2D databases}

2Geom provides an implementation of a 2D database using quad trees and
using a list.  Quad trees aren't the best data-structure for queries,
but they usually out perform the linear list.  We provide a
standard interface for object databases with performance guarantees
and provide a set of useful operations Operations:

\begin{description}
\item[Insert:] given a bounding box and a 'reference', insert into the db
\item[Delete:] given a bounding box and a 'reference', delete from the db
\item[Search:] given a box, find all objects that may interact with this 
box
\item[Cast:] given a path (including rays) return a list of objects that 
interact with the path, roughly sorted by path order
\item[Shape query:] given a closed path, find all objects whose bounding 
boxes intersect path.  (this and cast are nearly the same)
\item[Nearest:] given a point (or maybe box) find the nearest objects, 
perhaps as a generator to get all objects in order.  To do this, we walk 
around the quad tree neighbourhood, pushing all the elements into a 
priority queue, while the queue is empty, move out a bit.  Nearest could 
be manhattan, max norm or euc?
\item[Binary:] take two dbs, generate all pairs that have intersecting 
boxes.
\item[Sweep:] traverse the tree in say y order, maintaining a y-range of 
relevant objects. (to implement sweepline algorithms)
\item[Walk:] traverse the tree in an arbitrary order.
\end{description}

njh