Skip to content

Instantly share code, notes, and snippets.

@arlyon
Created April 6, 2018 13:03
Show Gist options
  • Save arlyon/d4bea495f6f9564dd4463c2301e992d8 to your computer and use it in GitHub Desktop.
Save arlyon/d4bea495f6f9564dd4463c2301e992d8 to your computer and use it in GitHub Desktop.
Gets the n closest points to a target point.
from typing import List, Tuple
from math import sqrt
from collections import defaultdict
from itertools import chain
def n_closest_points(n: int, target: Tuple[int, int], points: List[Tuple[int, int]]) -> int:
lengths = defaultdict(list)
for point in points:
lengths[sqrt((target[0] - point[0])**2 + (target[1] - point[1])**2)].append(point)
closest = chain.from_iterable(lengths[key] for key in sorted(lengths.keys()))
return list(closest)[:n]
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment