### Thread: efficient way to find only the closest objects

Page 1 of 3 123 Last
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. No Profile Picture
Contributing User
Devshed Intermediate (1500 - 1999 posts)

Join Date
Jul 2001
Location
Oslo
Posts
1,516
Rep Power
18
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...
3. 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.
4. No Profile Picture
Contributing User
Devshed Intermediate (1500 - 1999 posts)

Join Date
Jul 2001
Location
Oslo
Posts
1,516
Rep Power
18
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...
5. 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.

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

Join Date
Jul 1999
Location
Central Florida, USA
Posts
2,307
Rep Power
65
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"?
7. 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?
8. No Profile Picture
Contributing User
Devshed Intermediate (1500 - 1999 posts)

Join Date
Jul 2001
Location
Oslo
Posts
1,516
Rep Power
18
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".
9. No Profile Picture
Canta como rafaé
Devshed Newbie (0 - 499 posts)

Join Date
Feb 2001
Location
Barcelona
Posts
74
Rep Power
18
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.
10. 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
11. 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)....
12. No Profile Picture
Canta como rafaé
Devshed Newbie (0 - 499 posts)

Join Date
Feb 2001
Location
Barcelona
Posts
74
Rep Power
18
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).
13. 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]
14. 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
15. No Profile Picture
Canta como rafaé
Devshed Newbie (0 - 499 posts)

Join Date
Feb 2001
Location
Barcelona
Posts
74
Rep Power
18
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 ?
Page 1 of 3 123 Last