Python: Function to Find 2 Closest Points Among [x,y] Coordinates

I'm writing some code in Python that takes a set of [x,y] coordinates (in a list of tuples) and also an x-value. I need to find the two closest x coordinates to my x-value.

To find the closest x, I created a list of all the x-coordinates, used that list to create a lambda function that found the closest x to my x-value, and then found the index of that x.

Finding the 2nd closest value was a bit trickier. I created a new list that excluded the closest x and followed the same process.

Code is below. Any suggestions on how to improve this or make it more efficient?

def closest_2_points(list_of_tuples, x_value):

x_points = []

for i in list_of_tuples:
x_points.append(i)

# find closest point
closest_xpoint_1 = min(x_points, key=lambda z:abs(z-x_value))
closest_xpoint_1_idx = x_points.index(closest_xpoint_1)

# find 2nd closest point
x_points_2 = [x for x in x_points if x != closest_xpoint_1]
closest_xpoint_2 = min(x_points_2, key=lambda z:abs(z-x_value))
closest_xpoint_2_idx = x_points.index(closest_xpoint_2)

closest_points = [(list_of_tuples[closest_xpoint_1_idx], list_of_tuples[closest_xpoint_1_idx]), (list_of_tuples[closest_xpoint_2_idx], list_of_tuples[closest_xpoint_2_idx]) ]

return closest_points

When running the function, it should look something like this:

closest_2_points([(4,6),(2,5),(0,4),(-2,3)], 6)

And return something like this:

[(4, 6), (2, 5)]

If there are duplicate points in your list, and the closest point turns out to be one of these points, this line of code will remove all of the duplicates:

x_points_2 = [x for x in x_points if x != closest_xpoint_1]

So, instead of returning the 2 closest points, it may return just one of the closest, and some other nearby point.

Finding the n-smallest, n-closest, etc is usually best done using Python's heapq.nsmallest(n, iterable, key=None) function.

Return a list with the n smallest elements from the dataset defined by iterable. key, if provided, specifies a function of one argument that is used to extract a comparison key from each element in iterable (for example, key=str.lower). Equivalent to: sorted(iterable, key=key)[:n].

[This function] perform best for smaller values of n. For larger values, it is more efficient to use the sorted() function. Also, when n==1, it is more efficient to use the built-in min() and max() functions. If repeated usage of these functions is required, consider turning the iterable into an actual heap.

Example: a closest n points function, with n defaulting to 2:

import heapq

def closest_points(list_of_tuples, x_value, n=2):
return heapq.nsmallest(n, list_of_tuples, lambda pnt:abs(pnt - x_value))

Example:

>>> closest_points([(4, 6), (2, 5), (0, 4), (-2, 3)], 6)
[(4, 6), (2, 5)]
• Thanks for the feedback. In this particular instance, removing duplicates would not be an issue (in fact I'd want to remove them), but I neglected to mention that particular assumption in the original post. Thanks for your answer; I was not aware of the heapq library. Apr 24 '20 at 18:53

Welcome to codereview Ragnar! This was a fun one

Using list comprehensions, you can create a list that contains a tuple with 3 values:

1. Distance to x
2. Index of the tuple
3. x value

So then you can order the list, and take as many items from the tuple as desired

x = 6
points = [(4,6),(2,5),(0,4),(-2,3)]
closest_points = sorted([(x-xvalue, index, xvalue)
for index, xvalue in enumerate(points)])

Then you can slice the list and take values from there

closest_points[:2]
> [(2, 0, 4), (4, 1, 2)]

In this example, you would take:

• 0 as index of first element, 4 as the x value
• Then 1 as index of second element, 2 as value
• Please explain how this is better than the OPs. Can you also explain why $O(n\log n)$ time is better than $O(n)$. Apr 24 '20 at 12:59