How do I find two dimensional points in a minimum bounding rectangle?

[Hollywood]

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?

[JosAH]

Is that bounding box orthogonal to the X and Y axes?

kind regards,

Jos

[Hollywood]

Thank you for your response. No the box is not orthogonal to xy-plane, it is all within two dimensional space. The points lie on the xy-plane and I must query using upperY, upperX, lowerY, and lowerX of a 2D-bounding rectangle to retrieve the Set of points that lie within that rectangle.

Is there anything in the Java library already that will allow me to accomplish this?

[Norm]

Pretty specific requirements. It might require you to write some code.

An approach: Read and sort the points by upper left x.
To find all points in a box, scan to first x that is in the box, then scan to the first x out of box, selecting those points whose y's are in box.

[JosAH]

Thank you for your response. No the box is not orthogonal to xy-plane, it is all within two dimensional space. The points lie on the xy-plane and I must query using upperY, upperX, lowerY, and lowerX of a 2D-bounding rectangle to retrieve the Set of points that lie within that rectangle.

Is there anything in the Java library already that will allow me to accomplish this?

Your remark makes me feel that the rectangle's sides are indeed parallel to the X and Y axis, right? If so find the lowest and highest x and y values of all the points and you have your bounding rectangle.

kind regards,

Jos

[iluxa]

i think KD-trees would be a good fit for you. Read this: kd-tree - Wikipedia, the free encyclopedia

[viewer]

you must sort your array two times. for each dimension.
you can choose any sort algorithms.i prefer buble sort.
you get max and min value of your every sorting array.
you need four value for find bounding rectangle.
max x, min x, max y and min y.
1. point of your rectangle min x, min y
2. point of your rectangle min x, max y
3. point of your rectangle max x, max y
4. point of your rectangle max x, min y

your all points inside this rectangle.

[JosAH]

you must sort your array two times.

That would be silly; sorting the array two times takes O(n*log(n)) steps; simply scanning it once for both minimum and maximum values takes only O(n) steps.

kind regards,

Jos

[Hollywood]

i think KD-trees would be a good fit for you. Read this: kd-tree - Wikipedia, the free encyclopedia

The KD-trees is kind of what I was looking for and I think will work, but it is crunch time and I am not strong with implementing trees. Because of time I had to come up with something so I am implementing the bounding box using spatial hashing.

I found a pretty good article on it.
Spatial hashing implementation for fast 2D collisions « The mind of Conkerjo

Thank you everyone for your input.

[Norm]

What are the ranges of the x,y values?
Are you interested in an efficient solution or an easy one to code?

[viewer]

That would be silly; sorting the array two times takes O(n*log(n)) steps; simply scanning it once for both minimum and maximum values takes only O(n) steps.

kind regards,

Jos

my dear friend jos.
i know just max and min values of each array is enough...
first, i said "sort" for understanding logic of code...
and sorting is good..
i can say this as a cartography (surveying) engineer and gis expert....
if you have a coordinat array...
you must need sort for other queries....