Results 1 to 11 of 11
  1. #1
    Hollywood is offline Member
    Join Date
    Jan 2008
    Posts
    8
    Rep Power
    0

    Default 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?

  2. #2
    JosAH's Avatar
    JosAH is offline Moderator
    Join Date
    Sep 2008
    Location
    Voorschoten, the Netherlands
    Posts
    13,560
    Blog Entries
    7
    Rep Power
    21

    Default

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

    kind regards,

    Jos

  3. #3
    Hollywood is offline Member
    Join Date
    Jan 2008
    Posts
    8
    Rep Power
    0

    Default

    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?
    Last edited by Hollywood; 05-18-2010 at 08:11 AM. Reason: Add Thanks!

  4. #4
    Norm's Avatar
    Norm is online now Moderator
    Join Date
    Jun 2008
    Location
    SW Missouri
    Posts
    17,516
    Rep Power
    25

    Default

    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.

  5. #5
    JosAH's Avatar
    JosAH is offline Moderator
    Join Date
    Sep 2008
    Location
    Voorschoten, the Netherlands
    Posts
    13,560
    Blog Entries
    7
    Rep Power
    21

    Default

    Quote Originally Posted by Hollywood View Post
    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

  6. #6
    iluxa is offline Senior Member
    Join Date
    Mar 2010
    Posts
    266
    Rep Power
    5

    Default

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

  7. #7
    viewer is offline Member
    Join Date
    Mar 2010
    Posts
    13
    Rep Power
    0

    Default

    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.

  8. #8
    JosAH's Avatar
    JosAH is offline Moderator
    Join Date
    Sep 2008
    Location
    Voorschoten, the Netherlands
    Posts
    13,560
    Blog Entries
    7
    Rep Power
    21

    Default

    Quote Originally Posted by viewer View Post
    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

  9. #9
    Hollywood is offline Member
    Join Date
    Jan 2008
    Posts
    8
    Rep Power
    0

    Default

    Quote Originally Posted by iluxa View Post
    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.

  10. #10
    Norm's Avatar
    Norm is online now Moderator
    Join Date
    Jun 2008
    Location
    SW Missouri
    Posts
    17,516
    Rep Power
    25

    Default

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

  11. #11
    viewer is offline Member
    Join Date
    Mar 2010
    Posts
    13
    Rep Power
    0

    Default

    Quote Originally Posted by JosAH View Post
    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....

Similar Threads

  1. Replies: 2
    Last Post: 04-10-2010, 06:35 PM
  2. Replies: 2
    Last Post: 08-24-2008, 12:30 AM
  3. To find the Maximum and Minimum in an Array of Strings
    By luscious in forum JavaServer Pages (JSP) and JSTL
    Replies: 9
    Last Post: 07-31-2008, 01:51 PM
  4. Replies: 6
    Last Post: 06-12-2008, 09:14 AM
  5. Replies: 1
    Last Post: 02-16-2008, 09:10 PM

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •