7
\$\begingroup\$

Suppose there are a set of given points (represented by x and y two dimensional coordinates), and for any given point A, I want to find the nearest distance point among the given set of point.

My current solution is straightforward: just find min among all distances. The issue of my implementation is, if we want to calculate nearest point among the given set of points for another point B, I need to calculate distance again.

My question is, suppose the given set of points are fixed, is there any way to optimize (e.g. pre-process), so that search nearest point is much faster?

import sys
import random
def distance(p1, p2):
    return (p1[0]-p2[0])**2 + (p1[1]-p2[1])**2
def search_point(points, target_point):
    result = sys.maxint
    nearest_point = -1
    for p in points:
        d = distance(p, target_point)
        if d < result:
            result = d
            nearest_point = p
    return nearest_point

if __name__ == "__main__":
    points = []
    for i in range(10):
        points.append((random.randint(0,20),random.randint(0,20)))
    target_point = (random.randint(0,20), random.randint(0,20))
    print 'result', search_point(points, target_point)
    print 'target_point', target_point
    print 'raw points', points
    print 'distances', [distance(p, target_point) for p in points]
\$\endgroup\$
  • 3
    \$\begingroup\$ It's called "nearest neighbour search". Googling that will get you some ideas. In addition to writing your own code, it might be helpful to learn how to use the scikit, which interfaces with numpy and scipy. Exploring this library will not only give you something to compare your own code to, but will also lead you in a straightforward manner to machine learning in Python. \$\endgroup\$ – Ryan Mills Feb 20 '17 at 0:15
  • \$\begingroup\$ @RyanMills, I know this library, my specific question is, if the set of candidate nearest neighbor points are fixed, how to optimize? I think scikit learn does not optimize on it? \$\endgroup\$ – Lin Ma Feb 20 '17 at 0:49
  • 1
    \$\begingroup\$ Sci-kit includes both KD-tree and Ball-tree as classes, which are used to speed up the nearest neighbour search. You should use one of these structures, or some other binary search tree structure, to make your own search code go faster. \$\endgroup\$ – Ryan Mills Feb 20 '17 at 2:56
  • \$\begingroup\$ @RyanMills, for ball tree, do you mean algorithm similar to the envelop idea posted by sds? \$\endgroup\$ – Lin Ma Feb 21 '17 at 2:03
  • \$\begingroup\$ Pretty much. Just with more levels. For your case of 2 dimensions, a KD-tree would use slices to split the area (as sds describes) into narrower and narrower areas, while a ball-tree would use circles of smaller and smaller radius, each of which contains some of the points. \$\endgroup\$ – Ryan Mills Feb 21 '17 at 7:57
5
\$\begingroup\$

It makes no sense to save the distances to disk (disk i/o is slower than the computation), but it might make sense to "memoize" your function:

distance2_cache = {}
def distance2(p1,p2):
    "Compute the distance squared, using cache."
    try:
        return distance2_cache[(p1,p2)]
    except KeyError:
        distance2_cache[(p1,p2)] = d2 = (p1[0]-p2[0])**2 + (p1[1]-p2[1])**2
        return d2

Note that this might actually be slower than your original function because dictionary lookup may be more expensive than 2 multiplications (which dwarf two subtractions and an addition).

Edit: envelopes

If your pool of points is huge, and you have a stream of point that have to be matched against the pool (i.e., find the pool element which is the closest to input point), you can use lattices/envelopes: suppose your pool points have coordinates from 0 to 1. You can split them into 100 boxes by splitting each coordinate into 10. E.g., the box number 35 will have 0.2<=x<0.3 and 0.4<=y<0.5. Then for each new point you only need to check "very few" boxes (instead of all 100).

Specifically, you need to find the closest point in the box where the point landed, and then compare the distance to that closest point to the distance to the boundary of the box.

If the closest point is closer than the boundary, you are done.

Otherwise you need to check those neighboring boxes that are closer than the closest point (up to 11! if the target point and its closest point are almost in the opposite diagonal nodes). However, this should not happen if the number of points in the box is "large".

A good rule of thumb is that each box should contain as many points as there are boxes, e.g., if you have 10,000 points, there should be 100 boxes.

PS. The further development of this approach results in K-d tree.

\$\endgroup\$
  • \$\begingroup\$ Thanks sds, vote up. My specific question is, if the set of candidate nearest neighbor points are fixed (but the input point are different), how to optimize? I think your code does not help if input points are different from each time? \$\endgroup\$ – Lin Ma Feb 20 '17 at 0:50
  • 1
    \$\begingroup\$ I see. You have a huge pool of points and a stream of inputs what must be matched with the pool. right? \$\endgroup\$ – sds Feb 20 '17 at 0:52
  • \$\begingroup\$ Yes, sds. Any new idea to resolve this issue in a smarter way, without brute force compare min distance? \$\endgroup\$ – Lin Ma Feb 21 '17 at 1:02
  • 1
    \$\begingroup\$ did you read the edit? \$\endgroup\$ – sds Feb 21 '17 at 1:12
  • 1
    \$\begingroup\$ you are overly conservative. If you follow the rule of thumb and your boxes are well populated, you might need to check only one box. I will clarify my edit. \$\endgroup\$ – sds Feb 21 '17 at 1:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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