5

私のプログラムは、次のリスト (抜粋) を生成します。

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'}]

すでに「x」キーの値でソートされています。特定の座標に対してこのリストの2つの要素のタプルを返すメソッドを作成しようとしています(xPos, yPos):

  • 左に最も近い要素 ( x <= xPos)
  • 右に最も近い要素 ( x > xPos)

距離は単にユークリッド距離 (「ピタゴラス」) です。関数の 2 番目のパラメーターは、許可される最大距離です。

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

検索領域を絞り込むために、bisect 関数を使用しxPosて、xPos - maxDistance(case 'left') および(case 'right) にそれぞれ最も近い要素の挿入ポイントを取得しようとしました。xPos + maxDistance次に、このスライスされたリストの残りのすべての要素の距離を計算しました

なんというか、これは非常に非エレガントに感じます。これを行うより良い方法はありますか？

編集: たぶん、私の意図はあまり明確ではありませんでした: リストの 2 つの要素が必要です。'2D ペイン' 内の最も近い要素が左に、もう 1 つが右にあります。したがって、y 座標も考慮する必要があります。

x座標に関して最も近い要素が、近くのy座標を持つ要素よりもはるかに離れていることが（実際にはほぼ毎回）発生する可能性があります。

4

3 に答える 3

1

ユークリッド距離に関して、min()の両側で最も近い要素を見つけるために使用できます。posX

>>>import math
>>>def getNearest(noteList, posX, posY):
...    leftElement = min([i for i in my_list if i['x'] <= posX], key=lambda x:abs(math.sqrt((x['x']- posX)**2+(x['y']- posY)**2)))
...    rightElement = min([i for i in my_list if i['x'] > posX], key=lambda x:abs(math.sqrt((x['x']- posX)**2+(x['y']- posY)**2)))
...    return (leftElement, rightElement)


>>> getNearest(my_list, 2000, 2000)
({'y': 12650, 'x': 1807, 'class': 'note', 'id': 'd1e1362'}, {'y': 10040, 'x': 2707, 'class': 'note', 'id': 'd1e1194'})

>>> getNearest(my_list, 2000, 20000)
({'y': 20030, 'x': 1764, 'class': 'note', 'id': 'd1e2591'}, {'y': 20120, 'x': 2243, 'class': 'note', 'id': 'd1e2609'})

ここで、Keyは 2D ペインの各要素と関数に渡される要素の間のユークリッド距離(posX, PosY)です。

于 2015-07-24T09:43:48.863 に答える
1

それは良い解決策のように思えますが、あなたが説明した方法から、2つ以上の二分法を行う必要はないと思います。

bisect_left最初の条件が満たされるような要素のインデックスを既に返します ( x <= xPos - maxDistance)。そこから、 に到達するまで、要素を 1 つずつ右に繰り返しますx > xPos + maxDistance。

ジャンプするのではなく、隣接する位置を反復しているため、CPU キャッシュを考慮すると、おそらくパフォーマンスが向上します。

多数のポイントまたは の処理を​​開始する場合maxDistance、このアルゴリズムではおそらく十分ではありません。その場合、wenzul が提案したように、 kd-tree の使用を検討する必要があります。

于 2015-07-24T09:38:06.177 に答える
0

最初のアイデアと回答からのいくつかの提案をマージしようとしました。これは私が思いついたものです：

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))

symbolListを使用するために をよりスマートに変換する方法があるのではないbisect()でしょうか?

私がo(log*n)知る限り、私は比較するだけで実際の距離には興味がないので、ユークリッド距離を計算する必要さえありません。

于 2015-07-24T11:37:10.527 に答える