An elegant way to find the closest value in a circular ordered list

Question

Given a sorted list such as [1.1, 2.2, 3.3] and a boundary value such as math.pi*2 , return the closest value for any given value from [0 - math.pi*2)

The function should return the index of the value, so f(1.2) returns 0 , and f(2.1) returns 1 , and f(6.0) should wrap around math.pi*2 and return 0 , being closer to 1.1 than to 3 , 3, taking into account the boundary value. To be completely explicit, this function must also be wrapped at the lower end, so f(1.0, [5.0, 6.0], bound = math.pi*2) returns 1 .

A use case is to compare an arbitrary angle in radians with the nearest effective angle in the list. I wrote this function several times in python with bisect , but the code always ends up insulting my aesthetic feelings. The high complexity and the number of edge cases seem disproportionate to the intuitive simplicity of the function. So I ask if anyone can come up with a nice implementation, both in terms of efficiency and grace.

Answer 1

Here's a more elegant approach. Eliminate the edges by wrapping a number string around:

 from bisect import bisect_right def circular_search(points, bound, value): ## ## normalize / sort input points to [0, bound) points = sorted(list(set([i % bound for i in points]))) ## ## normalize search value to [0, bound) value %= bound ## ## wrap the circle left and right ext_points = [i-bound for i in points] + points + [i+bound for i in points] ## ## identify the "nearest not less than" point; no ## edge cases since points always exist above & below index = bisect_right(ext_points, value) ## ## choose the nearest point; will always be either the ## index found by bisection, or the next-lower index if abs(ext_points[index]-value) >= abs(ext_points[index-1]-value): index -= 1 ## ## map index to [0, npoints) index %= len(points) ## ## done return points[index] 

As written, it works if the input is not winning, like no points, or connected == 0.

Answer 2

Use the bisect module as a base:

 from bisect import bisect_left import math def f(value, sorted_list, bound=math.pi * 2): value %= bound index = bisect_left(sorted_list, value) if index == 0 or index == len(sorted_list): return min((abs(bound + sorted_list[0] - value), 0), (abs(sorted_list[-1] - value), len(sorted_list) - 1))[1] return min((index - 1, index), key=lambda i: abs(sorted_list[i] - value) if i >= 0 else float('inf')) 

Demo:

 >>> sorted_list = [1.1, 2.2, 3.3] >>> f(1.2, sorted_list) 0 >>> f(2.1, sorted_list) 1 >>> f(6.0, sorted_list) 0 >>> f(5.0, sorted_list) 2 

Answer 3

The easiest way is to simply use min:

 def angular_distance(theta_1, theta_2, mod=2*math.pi): difference = abs(theta_1 % mod - theta_2 % mod) return min(difference, mod - difference) def nearest_angle(L, theta): return min(L, key=lambda theta_1: angular_distance(theta, theta_2)) In [11]: min(L, key=lambda theta: angular_distance(theta, 1)) Out[11]: 1.1 

Using list sorting, you can use the bisect module:

 from bisect import bisect_left def nearest_angle_b(theta, sorted_list, mod=2*math.pi): i1 = bisect_left(sorted_list, theta % mod) if i1 == 0: i1, i2 = len(sorted_list) - 1, 0 elif i1 == len(sorted_list): i1, i2 = i1 - 1, 0 else: i2 = (i1 + 1) % len(sorted_list) return min((angular_distance(theta, L[i], mod), i, L[i]) for i in [i1, i2]) 

Returns the distance, index, and angle in the list to which it is closest.