Find the nearest point of a given set of points (part 2)

Question

This is a continued discussion from here, and I use new a approach (bounding box/or envelop algorithm) to improve the algorithm efficiency. Any code bugs, algorithm time complexity improvement or general code advice is highly appreciated.

Major structure of my code:

1. assign_box is used to build the bounding box or envelop
2. find_min is finding min points among all candidate points for a given target point. It first uses a bounding box/envelop solution. If it cannot find an answer, it will use a brute force solution
3. bruce_force is a brute force solution which is used to check the correctness of find_min
4. distance is a utility method used to check the distance between two points

import sys
import random
from collections import defaultdict
def assign_box(box_map, points, k):
 x_min = min([p[0] for p in points])
 x_max = max([p[0] for p in points])
 y_min = min([p[1] for p in points])
 y_max = max([p[1] for p in points])
 x_distance = (x_max - x_min) / k
 y_distance = (y_max - y_min) / k
 for p in points:
 i = (p[0]-x_min)/x_distance
 j = (p[1]-y_min)/y_distance
 box_map[(i,j)].append(p)
 return (x_min, x_distance, y_min, y_distance)
def distance(p1, p2):
 return (p1[0]-p2[0]) ** 2 + (p1[1]-p2[1]) ** 2
def find_min(points, box_map, target_point, x_min, x_distance, y_min, y_distance):
 # try 9 neighbour first
 row = (target_point[0] - x_min) / x_distance
 col = (target_point[1] - y_min) / y_distance
 result = sys.maxint
 result_point = None
 for r in range(row-1, row+2):
 for c in range(col-1, col+2):
 if (r,c) in box_map:
 for p in box_map[(r,c)]:
 d = distance(p, target_point)
 if d < result:
 result = d
 result_point = p
 if result_point:
 return (result, result_point)
 else:
 # try brute force solution
 result = sys.maxint
 result_point = None
 for p in points:
 d = distance(p, target_point)
 if d < result:
 result = d
 result_point = p
 return (result, result_point)
def bruce_force(points, target_point):
 result = sys.maxint
 result_point = None
 for p in points:
 d = distance(p, target_point)
 if d < result:
 result = d
 result_point = p
 return (result, result_point)
if __name__ == "__main__":
 # key is a tuple, (box row index, box col index)
 # value is a list of points fall into it
 box_map = defaultdict(list)
 points = []
 for i in range(100):
 points.append((random.randint(0,10), random.randint(0,10)))
 x_min, x_distance, y_min, y_distance = assign_box(box_map, points, 5)
 target_point = (random.randint(0,10), random.randint(0,10))
 print 'target point, ', target_point
 print 'find min result, ', find_min(points, box_map, target_point, x_min, x_distance, y_min, y_distance)
 print 'brute force result, ', bruce_force(points, target_point)

Answer 1

Mostly this looks good.

1. assign_box is used to build the bounding box or envelope

I benchmarked the speed of assign_box. Please see https://github.com/jhanley634/testing-tools/blob/master/problem/bench/min_of_copied_list.py#L104..L109 . It turns out one can compute a pair of min's / max's slightly faster:

0.017s scan_manually_with_if
0.019s scan_with_two_copies
0.030s assign_box
0.049s scan_with_key
0.078s scan_manually_with_min_max

The first two scan approaches are faster than your code.

2. find_min

A comment of # try 8 neighbors first would be more natural than 9, since distance won't be less when row & column offsets are zero.

3. bruce_force

Maybe this is a Bruce Lee joke. I recommend renaming it def brute_force.

4. distance is a utility method ...

I recommend renaming it def distance_squared, as it clearly does not compute Euclidean distance. It's only used in comparisons, and N^2 is monotonic w.r.t. N, so there's no harm done. But you should say what you mean, and mean what you say.