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