Results 1 to 11 of 11
 05182010, 02:34 AM #1Member
 Join Date
 Jan 2008
 Posts
 8
 Rep Power
 0
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?
 05182010, 07:14 AM #2
 Join Date
 Sep 2008
 Location
 Voorschoten, the Netherlands
 Posts
 13,820
 Blog Entries
 7
 Rep Power
 21
Is that bounding box orthogonal to the X and Y axes?
kind regards,
Jos
 05182010, 08:00 AM #3Member
 Join Date
 Jan 2008
 Posts
 8
 Rep Power
 0
Thank you for your response. No the box is not orthogonal to xyplane, it is all within two dimensional space. The points lie on the xyplane and I must query using upperY, upperX, lowerY, and lowerX of a 2Dbounding 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?Last edited by Hollywood; 05182010 at 08:11 AM. Reason: Add Thanks!
 05182010, 05:09 PM #4
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.
 05182010, 05:48 PM #5
 Join Date
 Sep 2008
 Location
 Voorschoten, the Netherlands
 Posts
 13,820
 Blog Entries
 7
 Rep Power
 21
 05182010, 06:58 PM #6Senior Member
 Join Date
 Mar 2010
 Posts
 266
 Rep Power
 5
i think KDtrees would be a good fit for you. Read this: kdtree  Wikipedia, the free encyclopedia
 05192010, 01:34 AM #7Member
 Join Date
 Mar 2010
 Posts
 13
 Rep Power
 0
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.
 05192010, 07:53 AM #8
 Join Date
 Sep 2008
 Location
 Voorschoten, the Netherlands
 Posts
 13,820
 Blog Entries
 7
 Rep Power
 21
 05192010, 08:01 AM #9Member
 Join Date
 Jan 2008
 Posts
 8
 Rep Power
 0
The KDtrees 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.
 05192010, 03:27 PM #10
What are the ranges of the x,y values?
Are you interested in an efficient solution or an easy one to code?
 05202010, 12:47 AM #11Member
 Join Date
 Mar 2010
 Posts
 13
 Rep Power
 0
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....
Similar Threads

need some urgent help for drawing random points inside a rectangle
By pranav21_1983 in forum Java AppletsReplies: 2Last Post: 04102010, 06:35 PM 
given number of points(cordinates) , find max points lie on the same line ?
By Hayzam in forum New To JavaReplies: 2Last Post: 08242008, 12:30 AM 
To find the Maximum and Minimum in an Array of Strings
By luscious in forum JavaServer Pages (JSP) and JSTLReplies: 9Last Post: 07312008, 01:51 PM 
To get the points on the perimeter of a Rounded Rectangle
By rashibahal in forum New To JavaReplies: 6Last Post: 06122008, 09:14 AM 
Recursive Method ==> find minimum value from array
By NatNat in forum New To JavaReplies: 1Last Post: 02162008, 10:10 PM
Bookmarks