Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

I have a question about the efficiency of an algorithm:

You have a list of x,y points

Now I want to get all the points that are up to 5 units away from a reference x,y point

How do you calculate it in the most efficient way?

I just go over each point and calculate distance, and if that distance is less than 5, I add it to the answer

If you know how this algorithm is called - I'd be happy if you post that too.

share|improve this question
1  
Nearest neighbor –  MichaelT Nov 15 '13 at 3:15
1  
Many games work in x^2 space so that distance calculations can avoid expensive sqrt operations. –  Steve Evers Nov 15 '13 at 3:58
    
You probably want to use a quadtree. –  Jerry Coffin Nov 15 '13 at 4:12
3  
@nurne: every algorithm has to visit each point just once, you cannot be more efficient. Of course, if you have to do the search more than once for different reference points, while the list of points is fixed, then the situation becomes different, and there is room for improvement. But you did not describe if that is your situation. –  Doc Brown Nov 15 '13 at 4:32
    
Notice that there is a difference between making an algorithm more efficient and choosing a more efficient algorithm. –  Cephalopod Nov 15 '13 at 12:26

2 Answers 2

While you cannot avoid having to check every point, there are techniques you can use to check quickly or check only once.

For example, most points you can tell if they are too far away without calculating the exact distance. For example, if I have a point whose x component is 100 away from the point of reference, you don't have to calculate distance. You already know that the point is too far away. Likewise if the x and y deltas are less than 5*2*sqrt(2) away from the point of reference, you know they are close enough. See the diagram below for a visual example:

Diagram describing algorithm

If P is your point of origin and the circle represents the farthest away that a point can be from point P (in your case radius of 5 units), then A and C represents places where points are definitely out or definitely in. Therefore, you can optimize your algorithm by checking x and y deltas. Only points which lie in the gray area B should have their distance calculated because you cannot know without performing a more sophisticated calculation.

Also, it would not hurt to sort your points by distance to P. If you have to perform this calculation often, you could optimize calculation by sorting once, then finding the farthest point within 5 units from P. Unless point positions change, you know that all points after that point must be closer.

I hope that helps!

share|improve this answer
    
OVerkill, really. The amount of extra code does not outweigh the small savings. –  MSalters Nov 15 '13 at 12:36
    
@MSalters I think trying to optimize for this sort of thing in general is overkill, however that is precisely what he is asking, and I am giving it to him. –  Neil Nov 15 '13 at 12:49
    
I'm fairly sure that this is not at all an optimization on any modern architecture. Yes, you do save some checks on y by checking x first, but that just does not make the code faster. x and y will be adjacent in memory, so they're probably both in the same cache line. –  MSalters Nov 15 '13 at 12:55
    
@MSalters The optimization was not "avoiding to read y". Please read my answer more carefully. The optimization is to be able to discard points with little more than a couple subtraction operations. You said it yourself in your own answer: "This saves you an expensive sqrt call per point", except my answer also saves you from having to square x delta and y delta as well. Also, I don't appreciate trying to put my answer in a bad light just so that your answer will get more reputation votes. –  Neil Nov 15 '13 at 13:10
1  
@MSalters So you're talking about micromanaging pipeline stalls and unpredicted memory reads, and my answer is overkill? Also, I appreciate that you added your answer just to fix mine. That was very altruistic of you. –  Neil Nov 15 '13 at 16:41

This is a common problem, and there's exactly one known optimization for the one-shot case: check if the distance squared is smaller than 25. This saves you an expensive sqrt call per point. Squaring and adding coordinates is almost free, in comparison to the time it takes to retrieve the data from memory.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.