javaalgorithmdata-structuresinterval-tree

Java implementation of 2 dimensional interval tree

I need a 2 dimensional interval tree for storing rectangular regions in a canvas.
I need to identify the regions which contain the point clicked or the regions overlapping with a rectangular selection.

Is there any standard implementation of 2 dimensional interval tree for this purpose ?

Solution

  • It seems that R-tree or it's variants are suitable.

    Implementation may be found here

    Edit: Now rtreeportal.org site does not work (2005 snapshot), but seems there is no comparable aggregator site that contains information and implementations for different kinds of R-trees.