Search code examples
pythonpython-3.xbisection

Get closest element from list of dictionaries

My program generates the following list (excerpt):

my_list = [{'x': 1764, 'y': 18320, 'class': 'note', 'id': 'd1e2443'},
           {'x': 1764, 'y': 20030, 'class': 'note', 'id': 'd1e2591'},
           {'x': 1807, 'y': 12650, 'class': 'note', 'id': 'd1e1362'},
           {'x': 2243, 'y': 20120, 'class': 'note', 'id': 'd1e2609'},
           {'x': 2243, 'y': 22685, 'class': 'note', 'id': 'd1e2769'},
           {'x': 2257, 'y': 12560, 'class': 'note', 'id': 'd1e1380'},
           {'x': 2688, 'y': 20210, 'class': 'note', 'id': 'd1e2625'},
           {'x': 2707, 'y': 10040, 'class': 'note', 'id': 'd1e1194'},
           {'x': 2707, 'y': 12650, 'class': 'note', 'id': 'd1e1398'},
           {'x': 2707, 'y': 14720, 'class': 'note', 'id': 'd1e1571'},
           {'x': 2901, 'y': 18140, 'class': 'note', 'id': 'd1e2475'}]

It is already sorted by the value of the 'x'-key. I am trying to write a method, that returns a tuple of two elements of this list for a given coordinate (xPos, yPos):

  • The nearest element to the left (x <= xPos)
  • The nearest element to the right (x > xPos)

The distance is simply the euclidean distance ("Pythagoras"). A second parameter for the function is the maximum distance allowed:

def getNearest(noteList, posX, posY, maxDistance):
    [...]
    return leftElement, rightElement

I have tried to use the bisect function to get the insertion point of the closest element to xPos as well as for xPos - maxDistance (case 'left') and xPos + maxDistance (case 'right) respectively in order to narrow down the search area. Then I calculated the distance for every remaining element in this sliced list

Somehow this feels very unelegant. Is there any better way of doing this?

EDIT: Maybe I was not very clear with my intention: I need two elements of the list. The nearest element in the '2D pane' to the left and one to the right. Thus I need to consider the y-coordinate as well.

It might happen (acutally almost every time) that the closest element in regard to its x-coordinate is way more far away than an element with a close-by y-coordinate.

Solution

  • I have tried to merge my initial idea with a few suggestions from the answers. This is what I came up with:

    class translatedDictList(object):
    def __init__(self, dictList, key):
        self.dictList = dictList
        self.key = key

    def __getitem__(self, item):
        return self.dictList[item][self.key]

    def __len__(self):
        return self.dictList.__len__()

def getNearest(self, symbolList, pos, maxDistance):
    translatedList = translatedDictList(symbolList, 'x')

    splitIndex = bisect.bisect(translatedList, pos[0])
    minIndex = bisect.bisect(translatedList, pos[0] - maxDistance)
    maxIndex = bisect.bisect(translatedList, pos[0] + maxDistance)

    # Euclidean distance acutally not needed anymore!
    leftElement = min(symbolList[minIndex:splitIndex],
                      key=lambda n: abs(n['x'] - pos[0]) +
                                    abs(n['y'] - pos[1]))
    rightElement = min(symbolList[splitIndex:maxIndex],
                       key=lambda n: abs(n['x'] - pos[0]) +
                                     abs(n['y'] - pos[1]))

    return leftElement, rightElement

print(getNearest(self.symbolsSorted, (1200, 1500), 1000))

    Maybe there is a smarter way of translating the symbolList in order to use bisect()?

    It should be o(log*n) and as far as I can tell I don't even need to calculate the euclidean distance anymore because I am only comparing and not interested in the actual distance.