CODEWITHSUNDEEP
python
porgarmingduod
porgarmingduod

Reputation: 7878

An elegant way of finding the closest value in a circular ordered list

Given a sorted list such as [1.1, 2.2, 3.3] and a bounding 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 that f(1.2) returns 0 while f(2.1) returns 1, and f(6.0) should wrap around at math.pi*2 and return 0, being closer to 1.1 than to 3.3 given the bounding value. Just to be entirely explicit, this function should also wrap around on on the lower end, so that f(1.0, [5.0, 6.0], bound = math.pi*2) returns 1.

The use case is to map an arbitrary angle in radians to the nearest existing valid angle in the list. I've written this kind of function a couple of times in python with bisect, but the code always ends up offending my aesthetic senses. The high complexity and number of edge cases seems out of proportion with the intuitive simplicity of the function. So I am asking if anyone can come up with a pleasing implementation, both in terms of efficiency and elegance.

Upvotes: 4

Views: 1517

Answers (3)

Chris Johnson
Chris Johnson

Reputation: 21956

Here's a more elegant approach. Eliminate the edge cases by wrapping the number line 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, works unless inputs are wonky like no points, or bound==0.

Upvotes: 2

Andy Hayden
Andy Hayden

Reputation: 375535

The easiest way would be just to 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

Making use of the sorted-ness of the list 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, the index and the angle in the list to which it's closest to.

Upvotes: 0

Martijn Pieters
Martijn Pieters

Reputation: 1122182

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

Upvotes: 1

Related Questions