spatial index for large objects

Question

I have a moderately large area (a few dozen square kilometers) that can contain thousands of objects. Most objects are small, a square meter, so they could almost be considered points. However, some of the objects are quite large, up to the same order of magnitude as the entire area.

I would like to perform some simple spatial queries on these objects (e.g. 'find all objects overlapping this rectangle'). I've been playing around with R-trees a bit, and that seems to work well for the small objects. But I'm not sure if an R-tree is still the best choice once I include my larger objects.

So the question is: what kind of spatial index would be most appropriate here? Bonus points if there's a Java implementation that features fast add/remove of objects.

Answer 1

If you're looking for a java specific implementation of a spatial index, the JTS library is fairly lightweight, and provides two spatial index implementations: QuadTree and STRTree. STRTree is just a specific space-optimized implementation of an R-Tree. Due to their hierarchical nature, both approaches (QuadTree and R-Tree) support objects at different scale, from small to big.

One limitation of R-Tree is that inserts are difficult (the JTS implementation doesn't allow inserts) because the index hierarchy is determined by the data, and may need to be changed when data is inserted, while the quadtree hierarchy is fixed regardless of how the data is distributed. This will probably affect your implementation more than feature size.

The Oracle Spatial documentation has good information about which type of spatial indexes work best in specific situations, although some of it is Oracle DB-specific. See the Indexing of Spatial Data section at http://docs.oracle.com/html/A88805_01/sdo_intr.htm

Answer 2

1. Your question is more over related to a topic called Geographic information system which is huge and has a set of its own rules of how to create databases and manage them.
2. One example of GIS-Geographic information system is Google Maps.
3. GIS projects have many tools to work on the project , examples
4. Java is not the language of choice when dealing with GIS for managing data , GIS projects normally work on C language refer