Sign in to follow this  
l0calh05t

Best spatial data structure for my needs?

Recommended Posts

Ok, basically what I need is a data structure for storing 2D points and line segments between said points (read: edges). The order of addition of these points and lines should not affect the resulting structure too much (they will be added more or less radially around a starting point, which is pretty bad for a basic point quadtree for example) and ideally require no rebalancing in the process, it should be efficient to find the points that lie inside a specified (axis-aligned) rectangle (or a circle) and it should be efficient to find all lines that lie (completely or partially) inside a specified axis-aligned rectangle. ideally a fast method for finding the nearest neighbour of a particular point would be usefull as well, but not necessary, as selecting a rectangle around it first should speed it up enough that a trivial O(n^2) algorithm would works ok as well, and the selection will probably have to be done anyways. I read a bit in Samet's Design and Analysis of Spatial Data Structures today and it would seem a PM3-Tree might work. (Although i'd probably extend it to use buckets for the points) Have you got any other (better?) ideas? I'm mainly looking for good asymptotic behaviour as the numbers of points will definitely exceed 10000, and the number of lines will probably be a little more than twice the number of points. Memory behaviour should of course be as good as possible as well (don't want the potential performance gains to be lost again to excessive paging).

Share this post


Link to post
Share on other sites
I'm actually looking into something similar:

A data structure holding 'sparse' data like lines and points, but I also require some kind of LOD system (in searching as well as visualising) and a way to order this data so it can be streamed into memory if it doesn't fit.

The only kind of applications that I am able to find that do something similar, are route-planners like map24. But finding information on how they are built is pretty hard.

According to Wikipedia the R-Tree structure is the most commonly used spatial datastructure. Perhaps you could find some useful information at these locations:

Site with Java applets demonstrating various algorithms

Site with a spatial index library in C/C++

Share this post


Link to post
Share on other sites
I'm not an expert on this branch of algorithms and data structures, but I have a feeling there just aren't that many compiled sources of spatial algorithms and data structures. There are, however, a few books that may contain the information you are looking for. Code search engines could prove to be useful also.

Here are a few books (both links take to Amazon).

Foundations of Multidimensional and Metric Data Structures
Level of Detail for 3D Graphics

Of course algorithms dealing with multidimensional databases use the same concepts, for instance.

[Edited by - Naurava kulkuri on July 15, 2007 3:27:02 AM]

Share this post


Link to post
Share on other sites
Are the points able to move, or do they move frequently?
This obviously greatly affects the amount of precalculation you can do.
Are all points added before you perform queries on the dataset, or do you add them as you go?

If all points are present from the beginning and they don't move, then you can divide things up into a grid and do a lot of precalculation about which points and lines are partially inside each cell, and hence potentially inside a rectangle covering part of that cell.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this