The Java Spatial Index project aims to maintain a high performance Java version of the RTree spatial indexing algorithm. as described in the 1984 paper "R-trees: A Dynamic Index Structure for Spatial Searching" by Antonin Guttman. (PDF on CiteSeerX)
The code is open source, and released under the GNU Lesser General Public License, version 2.1 or later.
See the SourceForge project page for downloads. Javadoc documentation is available online.
The JSI spatial index is deliberately limited in features, and does a small number of things well. It particular, it is fast. On a test machine, it takes about 500ms to add 10,000 entries to the spatial index. By comparison, an alternative implementation (that seems to be unmaintained now) takes over 6000ms (but it has more features).
The current release is 1.0, available at http://sourceforge.net/projects/jsi/files/m2_repo/net/sourceforge/jsi/jsi/1.0/jsi-1.0-project.zip/download. You will need maven2 installed and a working internet connection to build this. The source is included in the download zip file, but the CVS and SVN repositories on sourceforge are well out of date. Development now happens at http://github.com/aled/jsi.
In addition, you can download the binary jar at http://sourceforge.net/projects/jsi/files/m2_repo/net/sourceforge/jsi/jsi/1.0/jsi-1.0.jar/download.
The API includes the following operations:
YourKit is kindly supporting open source projects with its full-featured Java Profiler. YourKit, LLC is the creator of innovative and intelligent tools for profiling Java and .NET applications. Take a look at YourKit's leading software products: YourKit Java Profiler and YourKit .NET Profiler."