|
Posted by Brian Lindahl on August 24, 2004, 8:32 am
Please log in for more thread options > [F'up2 limited to one group --- should have been done by OP!]
>
> > What kinds of non-overlapping spatial index structures are out there?
> > I know of quadtrees/octrees and their linear versions, but are there
> > others that are more size effecient (coordinate-space compact)?
>
> Depends on what you count as "other", i.e. how wide your definition of
> an octree is. K-d trees and BSP trees would fit your bill, too, and
> will usually be more efficient for search applications on static data
> set because they adapt their splitting planes to the data
> distribution.
I should have mentioned that I'm using the structure to do range
searches on rectanglular objects. I also would like the capability of
storing objects at any node, not just the leaves - since a heirarchy
is very useful in my model.
In my current model, with a quadtree, I expand the rectangle to the
minimal bounding binary square (2 dimensions), and use that binary
square as a mapping to the quadtree node to where I would place my
rectangular object (objects cannot be split). In my implementation,
I'm using the spatial index structure to create atomicity for events
that modify objects within a coordinate region - so objects can't be
split, nor can nodes overlap.
K-d trees and BSP trees are for data points right? Or can they be
adapted to fit my needs?
I know that preprocessing (packing) can generate non-overlapping
R-Trees, but I do need to be able to do inserts (albeit very limited).
Is there a way to do an insert on R-Trees that guarantees
non-overlapping if the precondition was non-overlapping (fast inserts
aren't necessarily needed)?
| 
XML Sitemap