|
|||||||||
|
|||||||||
| |||||||||
|
|||||||||
|
|||||||||
| |||||||||
|
|
|
| |||||||||
 |
|
|
«
Previous Thread
|
Next Thread
»
|
Thread Tools | Search this Thread | Rate Thread | Display Modes |
Dev Shed Forums Sponsor:
|
|
|
|
#1
February 19th, 2002, 12:56 PM
|
|||
|
|||
|
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
February 19th, 2002, 01:18 PM
|
|||
|
|||
|
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
|
|
#3
February 19th, 2002, 04:30 PM
|
|||
|
|||
|
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
February 19th, 2002, 05:56 PM
|
|||
|
|||
|
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
February 19th, 2002, 08:09 PM
|
|||
|
|||
|
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
|
|
#6
February 20th, 2002, 01:22 AM
|
|||
|
|||
|
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
|
|
#7
February 20th, 2002, 10:07 PM
|
|||
|
|||
|
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
February 21st, 2002, 06:20 AM
|
|||
|
|||
|
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/pr.../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
February 22nd, 2002, 04:36 AM
|
|||
|
|||
|
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.
__________________
Thrasher  'Y se ahogaron los dooos No eran duros pa pagar, cuñaaoo !!' El vagamundo - El risitas y su cuñao Last edited by Thrasher : February 22nd, 2002 at 04:40 AM.
|
|
#10
March 4th, 2002, 05:24 PM
|
|||
|
|||
|
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
March 7th, 2002, 02:29 AM
|
|||
|
|||
|
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)....
|
|
#13
March 8th, 2002, 10:07 AM
|
|||
|
|||
|
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
March 12th, 2002, 09:07 PM
|
|||
|
|||
|
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
March 13th, 2002, 04:12 AM
|
|||
|
|||
|
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 ?
|
|
| Viewing: Dev Shed Forums > Programming Languages - More > Software Design > efficient way to find only the closest objects |
| Thread Tools | Search this Thread |
| Display Modes | Rate This Thread |
Del.icio.us
Digg
Google
Spurl
Blink
Furl
Simpy
Y! MyWeb
Linear Mode
