Menu
▾
▴
lib2geom-devel
|
From: Sunburned S. <sun...@gm...> - 2007-04-20 17:36:49
|
Hey guys. I always try to sketch out a basic design for my code before a start writing classes. It usually helps to think about the problem I'm trying to solve and what basic requirements my code will need to meet. I wanted to share what I thought would be some good requirements for a 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. At a minimum, it should be able to expand in size. If possible, it should be able to contract in size. (I'm not speaking of computer memory consumed when I say "size" in this context. I mean the limits of the space or area being indexed.) Requirement #2: The spatial index should offer the ability for efficient updates. In other words, you shouldn't have to determine where every geometry belongs in the index when a geometry is (a) added to the index (b) removed from the index, or (c) a geometry in the index is modified. 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. What do you guys think? Am I missing anything? Scott Huey P.S. - Do you guys have a class template I can use for lib2geom? If not, could I make one? |
|
From: mgsloan <mg...@gm...> - 2007-04-21 19:20:02
|
> Hey guys. I always try to sketch out a basic design for my code before a > start writing classes. It usually helps to think about the problem I'm > trying to solve and what basic requirements my code will need to meet. I > wanted to share what I thought would be some good requirements for a > lib2geom spatial index. I want to have these in mind when I start to look at > the existing quadtree class. > Sounds good - we tend to jump into coding, and then design it right, but your strategy is likely better. Requirement #1: The spatial index should not be limited to a fixed size. At > a minimum, it should be able to expand in size. If possible, it should be > able to contract in size. (I'm not speaking of computer memory consumed when > I say "size" in this context. I mean the limits of the space or area being > indexed.) > Good! Requirement #2: The spatial index should offer the ability for efficient > updates. In other words, you shouldn't have to determine where every > geometry belongs in the index when a geometry is (a) added to the index (b) > removed from the index, or (c) a geometry in the index is modified. > Hmm, I'm not sure if A is feasible. B and C could be implemented with a hash table. I suppose C could also be implemented with pointers and mutability, though mutability in general could easily throw off a spatial index. Really C is just a combination of B and A. 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. > What do you guys think? Am I missing anything? > Sounds like you have a pretty good plan/design going, I'd implement what you've thought up - what's needed later can be added. P.S. - Do you guys have a class template I can use for lib2geom? If not, > could I make one? > We don't - C++ isn't necessarily one class per file. Functions don't even need to be in classes. Still, might be a good idea - it could include the license (with spots to insert creator and date), an include guard, the namespace decl, a class decl, and the editor footer. |
|
From: mgsloan <mg...@gm...> - 2007-04-21 19:30:14
|
Doh, forgot to write anything for #3: 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. > Defintely a good idea. Another query function might be nearest geometry (to a point). I suppose this one might require that the geometry implements functions to perform this. It might be valuable to have 3 listing functions - one for containment, one for partial intersection, and one for containment or intersection. For now just the containment+intersection one may be enough, but for a renderer it may be valuable to treat the geometries which require culling/triming specially. -Michael Sloan |
|
From: njh <nj...@nj...> - 2007-04-22 01:33:58
|
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
|
|
From: njh <nj...@nj...> - 2007-04-22 03:17:56
|
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
>
|
|
From: Sunburned S. <sun...@gm...> - 2007-04-22 14:25:17
|
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
>
|
×
Want the latest updates on software, tech news, and AI?
Get latest updates about software, tech news, and AI from SourceForge directly in your inbox once a month.
Thanks for helping keep SourceForge clean.
X