Page 1 of 3 123 Last
  • Jump to page:
    #1
  1. No Profile Picture
    Junior Member
    Devshed Newbie (0 - 499 posts)

    Join Date
    Dec 2001
    Posts
    28
    Rep Power
    0

    efficient way to find only the closest objects


    I've got an array of objects. Each object has two properties: x and y, which are its coordinates on a plane.

    If I want to find all of the objects in the array that are less than 20 units away from a given object, what is the most efficient way to do it?

    All that I know to do is loop through the array, and for each object use the distance formula to find its distance from the given object.

    Is there a better way? Is this the only way?
  2. #2
  3. No Profile Picture
    Contributing User
    Devshed Intermediate (1500 - 1999 posts)

    Join Date
    Jul 2001
    Location
    Oslo
    Posts
    1,516
    Rep Power
    15
    No. You need to check each node at least once, which is what you do by iterating through the array. The algorithm is O(N), which is pretty good...
    --
    Regards
    André Næss

    Puritanism: The haunting fear that someone, somewhere may be having fun
  4. #3
  5. No Profile Picture
    Junior Member
    Devshed Newbie (0 - 499 posts)

    Join Date
    Dec 2001
    Posts
    28
    Rep Power
    0
    thanks for the reply... I'm kind of disappointed, though. I was hoping that there was some sort of short cut, though I can't imagine what it would be.

    That'll have to do.

    thanks.
  6. #4
  7. No Profile Picture
    Contributing User
    Devshed Intermediate (1500 - 1999 posts)

    Join Date
    Jul 2001
    Location
    Oslo
    Posts
    1,516
    Rep Power
    15
    Well, unless you have a psychic computer that's gonna be hard.

    It's probably possioble to improve the data structure, for example, you can store the objects in "buckets", that is, you split the coordinate plane into square areas, and think of them as buckets. If you choose the bucketsize so that you only have to check the buckets surrounding the bucket in which the object you're testing from is located you might save some time. It depends on your data.

    Of course, improving the datastructure will cost you time, so you might end up with no total gain, even if the algorithm in itself is greatly speeded up...
    --
    Regards
    André Næss

    Puritanism: The haunting fear that someone, somewhere may be having fun
  8. #5
  9. No Profile Picture
    Junior Member
    Devshed Newbie (0 - 499 posts)

    Join Date
    Dec 2001
    Posts
    28
    Rep Power
    0
    I think that I'll just stick with looping through the array... although your bucket idea is interesting, and something that never would have occurred to me. I may play around with that, too.

    thanks for your help.


    -will
  10. #6
  11. No Profile Picture
    Gödelian monster
    Devshed Regular (2000 - 2499 posts)

    Join Date
    Jul 1999
    Location
    Central Florida, USA
    Posts
    2,307
    Rep Power
    61
    One question I might ask, though: is the nature of the data random, or is there some order to it? In other words, what is the mechanism by which these points are assigned in the first place? Knowing that, there might be some kind of a way of quickly "disqualifying" some sets of points. I don't have a specific idea in mind; just pushing this around in my head. I love geometrical problems.

    Whenever I think about computer problems, I try to think a little more about how I would solve it without a computer. For example, how would you or I optimize that search if we were doing it manually?

    First we would glance quickly at the points on the plane to determine which ones seem too far away to bother with. We would also not waste time on the ones that are obviously too close to worry about. We would then estimate the general radius of our search, and start checking those which seem to be around that border.

    But of course, this is because we have two ways of checking distance: one is an inaccurate estimate with our eyes, while the second is an accurate reading with a ruler or string. Can a computer do something similar? Let's think about it some. Maybe there is a method of doing a quick low-accuracy search to eliminate a great number of candidates on the first pass, and then we pick up the hard numbers on the second pass. Or it could even be a multipass optimization, if there is an extremely large array of numbers.

    In a way, this is what andnaess's buckets provide, but maybe more is possible. What is the actual distance formula, and what do you mean by "twenty units"?
    The real n-tier system:

    FreeBSD -> PostgreSQL -> [any_language] -> Apache -> Mozilla/XUL

    Amazon wishlist -- rycamor (at) gmail.com
  12. #7
  13. No Profile Picture
    Junior Member
    Devshed Newbie (0 - 499 posts)

    Join Date
    Dec 2001
    Posts
    28
    Rep Power
    0
    Let's say for our purposes the objects are travelling on randomly-chosen paths... sine waves, or something similar.

    I want the objects to be aware of the other objects that are within a certain radius of them... that's what the 20 units is. It's actually 20 pixels on the screen, I guess.

    I haven't tried to do anything with andnaess' bucket idea yet, but it has really intrigued me.

    The distance formula I was going to use is just the one that I have always used in math class:
    Code:
          _________________________
    d = \/(x2 - x1)^2 + (y2 - y1)^2
    is there another one?
  14. #8
  15. No Profile Picture
    Contributing User
    Devshed Intermediate (1500 - 1999 posts)

    Join Date
    Jul 2001
    Location
    Oslo
    Posts
    1,516
    Rep Power
    15
    My hunch when reading your first post was that this was a collision detection like problem, and now I'm quite positive that is, so maybe you could get some ideas from this webpage on collision detection:
    http://www.permutationcity.co.uk/pro...collision.html
    (You'll find two bucket solutions there)

    And I'm sure there are plenty more available, so do a search on Google for collision detection algorithms.

    The bucket solution is the closest you can get to the computer doing a quick "low-accuracy searching".
    --
    Regards
    André Næss

    Puritanism: The haunting fear that someone, somewhere may be having fun
  16. #9
  17. No Profile Picture
    Canta como rafaé
    Devshed Newbie (0 - 499 posts)

    Join Date
    Feb 2001
    Location
    Barcelona
    Posts
    74
    Rep Power
    14
    There is an easy solution which uses kind of bucketing but in its simplest way.

    You are using the square root formula to get all the points within the radius. Still use it but with a little modification.

    Suppose you have (18, 47) and (97, 45). You should not use the sqrt formula, because you can test at first that

    abs (97 - 18) > 20

    The distance is greater than 20 in a single coordinate, so the real distance between the points is greater than 20.

    So first you check the distance between points in each coordinate, and if you get that the distances are between your treshold, then use the sqrt.

    With this, your algorithm is still O(n), because you have to check all the points, but in fact would be a liiiitle faster because you won't be using the costly sqrt function too much.


    If you want a little more of improvement, sort the array using as key the value of the coordinate with more dispersion on it, and then do a dicotomical search to find where the point that you are analizing is (or would fit).

    Then, look and test for all the surrounding points in the array (in both ways, right and left). Whenever you find a point which is outside or the range in the key axis, stop there. When you have found all two "outside" points, it's finished.
    Last edited by Thrasher; February 22nd, 2002 at 03:40 AM.
    Thrasher



    'Y se ahogaron los dooos
    No eran duros pa pagar, cuñaaoo !!'
    El vagamundo - El risitas y su cuñao
  18. #10
  19. No Profile Picture
    Junior Member
    Devshed Newbie (0 - 499 posts)

    Join Date
    Dec 2001
    Posts
    28
    Rep Power
    0
    Thanks, guys, for your input. I have decided to just loop through each item, the boring, slow way.

    I think that figuring out how to tie a 'bucket' sort of system in to what I'm doing would be too much for me, at this point.

    But, thanks to your suggestions, I won't actually be taking the square root, which will save me some time, I expect. It probably would not have occurred to me to do it this way without your help.

    So, thanks.


    -Will
  20. #11
  21. No Profile Picture
    Junior Member
    Devshed Newbie (0 - 499 posts)

    Join Date
    Mar 2002
    Posts
    1
    Rep Power
    0

    hash function?


    I admit, I may not know what I'm talking about since I'm only learning about this right now, but how'bout applying a hash function to this? Will that work in this instance?


    They're O(1)....
  22. #12
  23. No Profile Picture
    Canta como rafaé
    Devshed Newbie (0 - 499 posts)

    Join Date
    Feb 2001
    Location
    Barcelona
    Posts
    74
    Rep Power
    14
    You are right, a hash table is O(1), but as you have to go through every node, you would do N queries, so N * O(1) = O (N).
    Thrasher



    'Y se ahogaron los dooos
    No eran duros pa pagar, cuñaaoo !!'
    El vagamundo - El risitas y su cuñao
  24. #13
  25. No Profile Picture
    Junior Member
    Devshed Newbie (0 - 499 posts)

    Join Date
    Mar 2002
    Location
    Indiana
    Posts
    1
    Rep Power
    0
    You could use a method similar to buckets, but a little faster to code.

    The distance formula packs a punch on your cpu compared to basic math (+ ,-,) because of all its squares and squareroots.

    The most effective (codetime and runtime) I have personaly used is a multi-pass method to eliminate obvious points.

    Pass 1:
    Search via the X-axis and eliminate points more than 20 points from the test-point
    Code:
    for(i=0;i<size(points);i++){
      if(Math.abs(points[test].x - points[i].x)<=20){
        points_pass2[] = points[i];
      }
    }
    Pass 2:
    Search the accepted points from the last pass via the Y-axis and eliminate points more than 20 points from the test-point
    Code:
    for(i=0;i<size(points_pass2);i++){
      if(Math.abs(points[test].y - points_pass2[i].x)<=20){
        points_pass3[] = points_pass2[i];
      }
    }
    Pass 3:
    Apply the distance formula to the final remaining points to get an accurate read
    Code:
    for(i=0;i<size(points_pass3);i++){
      if(Math.sqrt((points[test].y-points_pass3[i].y)(points[test].y-points_pass3[i].y)+(points[test].x-points_pass3[i].x)(points[test].x-points_pass3[i].x))<=20){
        points_within20[] = points_pass3[i];
      }
    }
    You then have your final array: points_within20 That contains all of the points at or closer to 20 units from your central point.

    Since you eliminated the points more than 20 from the x and y axis first used a very low-profile quick-execution equation your loop with the distance formula contained much less points, and therefore used much less cpu-time.

    I hope this helped

    [eko]
  26. #14
  27. No Profile Picture
    Junior Member
    Devshed Newbie (0 - 499 posts)

    Join Date
    Dec 2001
    Posts
    28
    Rep Power
    0
    Eko-

    Is it usually faster to do the quick distance comparison in two loops, one for x and one for y, than in one, that will compare both x and y at once?

    I haven't done any testing on my own, yet. It just seemed to me like it may be as fast to do both comparisons in one loop.

    I like your idea, though, and I've used it. Thanks.


    -will
  28. #15
  29. No Profile Picture
    Canta como rafaé
    Devshed Newbie (0 - 499 posts)

    Join Date
    Feb 2001
    Location
    Barcelona
    Posts
    74
    Rep Power
    14
    Well, Ekostudios has shown an implementation of the first part of the method that I explained some posts ago.

    I think that explaining the method as text is not as clear as source code, so sorry guys.

    Does someone wants to "pseudoimplement" the second part of my method ?
    Thrasher



    'Y se ahogaron los dooos
    No eran duros pa pagar, cuñaaoo !!'
    El vagamundo - El risitas y su cuñao
Page 1 of 3 123 Last
  • Jump to page:

IMN logo majestic logo threadwatch logo seochat tools logo