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

[mgsloan <mg...@gm...>]

> 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.