Closest points
Never
import math from random import random, seed import timeit class Point: def __init__(self, x, y): self.x = x self.y = y def __repr__(self): return "(%s, %s)" % (self.x, self.y) # Used to count the number of comparisons being done. class DistanceCalc: def __init__(self): self.count = 0 def dist(self, a, b): self.count += 1 # Not using sqrt due to all comparisons being relative each other means I don't need the actual distance, just # the magnitude. return math.pow(b.x - a.x, 2) + math.pow(b.y - a.y, 2) def reset(self): self.count = 0 # Just a bit easier to manage than a tuple class BestPair: def __init__(self, p1, p2, dist): self.p1 = p1 self.p2 = p2 self.dist = dist def brute_force(points, first_i, last_i, calc): best = BestPair(None, None, float("inf")) for i in range(first_i, last_i + 1, 1): for j in range(first_i, last_i + 1, 1): if i == j: continue dist = calc.dist(points[i], points[j]) if dist < best.dist: best = BestPair(points[i], points[j], dist) return best def planar_version(points, calc): sorted_points = sorted(points, key=lambda single_point: single_point.x) def recurse(first_i, last_i): nonlocal sorted_points # if last_i - first_i == 1: # return BestPair(sorted_points[first_i], sorted_points[last_i], calc.dist(sorted_points[first_i], sorted_points[last_i])) if last_i - first_i <= 2: return brute_force(sorted_points, first_i, last_i, calc) mid_i = (last_i + first_i) // 2 best = recurse(first_i, mid_i) right_best = recurse(mid_i, last_i) if best is None or right_best.dist < best.dist: best = right_best # Since we're sorted by X, find the first element within best_dist of mid point. mid_left_i = first_i while mid_left_i < mid_i and math.fabs(sorted_points[mid_i].x - sorted_points[mid_left_i].x) > best.dist: mid_left_i += 1 mid_right_i = last_i while mid_right_i > mid_i and math.fabs(sorted_points[mid_right_i].x - sorted_points[mid_i].x) > best.dist: mid_right_i -= 1 # Moon elf magic: Sort central region by Y-coordinate and then compare by Y-coordinate # This isn't always returning the same answer as the raw brute force method... but sometimes it does. # (smells like an off-by-one error) mid_best = BestPair(None, None, float("inf")) sorted_y_slice = sorted(sorted_points[mid_left_i:mid_right_i+1], key=lambda single_point: single_point.y) for i in range(0, len(sorted_y_slice), 1): j = i + 1 while j < len(sorted_y_slice) and sorted_y_slice[j].y - sorted_y_slice[i].y < mid_best.dist: dist = calc.dist(sorted_y_slice[i], sorted_y_slice[j]) if dist < mid_best.dist: mid_best = BestPair(sorted_y_slice[j], sorted_y_slice[i], dist) j += 1 # # Brute force the central region. Much slower. # mid_best = brute_force(sorted_points, mid_left_i, mid_right_i, calc) if mid_best.dist < best.dist: best = mid_best return best best = recurse(0, len(sorted_points)-1) return best seed(103) points = [] for i in range(0, 100, 1): points.append(Point(random() * 10000.0, random() * 10000.0)) calc = DistanceCalc() best = brute_force(points, 0, len(points)-1, calc) print("%s, %s %s" % (best.p1, best.p2, calc.count)) calc.reset() best = planar_version(points, calc) print("%s, %s %s" % (best.p1, best.p2, calc.count)) # print(timeit.timeit(lambda: brute_force(points, 0, len(points)-1, calc), number=1000)) # print(timeit.timeit(lambda: planar_version(points, calc), number=1000))
Raw Text
-
Untitled
11 min ago
-
đŸ”¥namorada rabuda dando o cuzinho de 4
11 min ago
-
Untitled
29 min ago
-
DTFsluts - Petite Blonde Babe Riley Star Sucks and Fucks James Deen's Big Dick
41 min ago
-
dsfsdf sd dfsdfs dsf dsdsf sdfdsfdf
1 hour ago
-
asdfbdasdfgbdasdf
1 hour ago
-
Vacation Accident With Hot Step Mom - Gigi Dior - Family Therapy - Alex Adams
1 hour ago
-
Threesome at the Hair Salon - Cuckold Boyfriend Picks Her Up (English Subtitles) - DivinaMaruuu
1 hour ago
-
Sister's best friend got my eggs for breakfast - the perfect friend
2 hours ago
-
No Deposit Bonus
2 hours ago