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

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

Sorry, that sounds a bit cranky - I am not normally like this (actually, 
maybe I am).  I blame my stupid cold that kept me up all night.

njh

On Sun, 22 Apr 2007, njh wrote:

> 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
>
> -------------------------------------------------------------------------
> This SF.net email is sponsored by DB2 Express
> Download DB2 Express C - the FREE version of DB2 express and take
> control of your XML. No limits. Just data. Click to get it now.
> http://sourceforge.net/powerbar/db2/
> _______________________________________________
> Lib2geom-devel mailing list
> Lib...@li...
> https://lists.sourceforge.net/lists/listinfo/lib2geom-devel
>