Самый быстрый способ проверки наименьшего расстояния между точками

Question

У меня есть 2 словаря. Оба имеют пары ключ-значение индекса и местоположение в мировом пространстве.

Что-то вроде:

{
  "vertices" : 
  {
    1: "(0.004700, 130.417480, -13.546420)",
    2: "(0.1, 152.4, 13.521)",
    3: "(58.21, 998.412, -78.0051)"
  }
}

В словаре 1 всегда будет около 20–100 записей, в словаре 2 всегда будет около 10000 записей.

Для каждой точки в словаре 1 я хочу найти ближайшую к ней точку в словаре 2. Какой самый быстрый способ сделать это? Для каждой записи в словаре 1 просмотрите все записи в словаре 2 и верните ближайшую.

Некоторый непроверенный псевдокод:

for point, distance in dict_1.iteritems():
    closest_point = get_closest_point(dict_1.get(point))


def get_closest_point(self, start_point)

    furthest_distance = 2000000
    closest_point = 0

    for index, end_point in dict_1.iteritems():
        distance = get_distance(self, start_point, end_point)
        if distance < furthest_distance:
            furthest_distance = distance
            closest_point = closest_point

    return closest_point

Я думаю, что-то подобное будет работать. Проблема в том, что если в словаре 1 будет 100 записей, это будет 100 x 10 000 = 1 000 000 итераций. Это просто не кажется мне очень быстрым или элегантным.

Есть ли лучший способ сделать это в Maya/Python?

РЕДАКТИРОВАТЬ: Просто хочу прокомментировать, что я использовал узел closestPointOnMesh прежде, который работает очень хорошо и намного проще, если точки, по которым вы проверяете, на самом деле являются частью меша. Вы могли бы сделать что-то вроде этого:

selected_object = pm.PyNode(pm.selected()[0])
cpom = pm.createNode("closestPointOnMesh", name="cpom")

for vertex, distance in dict_1.iteritems():
    selected_object.worldMesh >> cpom.inMesh

    cpom.inPosition.set(dict_1.get(vertex))
    print "closest vertex is %s " % cpom.closestVertexIndex.get()

Мгновенный ответ от узла и все денди. Однако, если список точек, по которым вы проверяете, не является частью меша, вы не можете использовать это. Будет ли это возможно / быстрее:

• Построить сетку из точек в словаре 2
• Использовать сетку с узлом closestPointOnMesh
• Удалить сетку

Answer 1

Вам определенно нужна структура ускорения для нетривиального количества очков. Дерево KD или октодерево - это то, что вам нужно - деревья KD более производительны при поиске, но их создание медленнее и их сложнее кодировать. Также, поскольку Octrees являются пространственными, а не двоичными, они могут облегчить проведение тривиальных тестов.

Вы можете получить питон октре здесь: http://code.activestate.com/recipes/498121-python-octree-implementation/

Если вы выполняете много проверок на расстояние, вам определенно нужно использовать векторные классы Maya API для выполнения фактических математических сравнений, хотя это будет намного, намного быстрее, чем эквивалентный python. Вы можете получить это от pymel.datatypes если вы плохо знаете API, хотя использование более новых версий API2 довольно безболезненно.

Answer 2

Вам нужно то, что называется KD Tree. Создайте KD-дерево с точками во втором словаре и запросите ближайшую точку к каждой точке в первом словаре.

Я не знаком с майей, если вы можете использовать scipy, вы можете использовать это.

PS: Кажется, здесь есть реализация на C++.