How do I find two dimensional points in a minimum bounding rectangle?
I have a list of approx 100,000 two dimensional points (i.e. x and y coordinates), which are locations in space, and locality is very important.
I need to quickly retrieve points from a so called bounding box or minimum bounding rectangle which contains them. (Note: Linear search and normal hashing is not an option)
My overall goal is to just add all the points to a structure and then retrieve a list of points that lie within the provided min and max corner points.
Does java support anything to implement this?
What should I use to load the points into and to retrieve them?
Can I utilize anything from the java.awt.geom library as a datastructure (i.e. Rectangle2D)? If so how can I retrieve the points I want?