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

[Sunburned S. <sun...@gm...>]

njh told me this didn't make it to the list.

Sorry about that.

Scott Huey

---------- Forwarded message ----------
From: Sunburned Surveyor <sun...@gm...>
Date: Apr 21, 2007 7:19 PM
Subject: Re: [Lib2geom-devel] Requirements for lib2geom spatial index...
To: njh <nj...@nj...>


Perhaps the quadtree class doesn't need any work and I can help with
something else? Is there another simple feature of the library that I can
get started with?

Or perhaps I should just work on some API documentation for the existing
quadtree class?

I did put together a simple API documentation in HTML that could be used to
document any type of object-oriented language. I could put together a sample
of the documentation using this html format and also in PDF.

What do you guys think?

Scott Huey

P.S. - I still need to figure out how to compile the manual. Maybe I need to
do that next Friday before I do anything else. Then I won't irritate anybody
with needless questions.


 On 4/21/07, njh <nj...@nj...> 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
>