检查点之间最近距离的最快方法

Question

我有两本字典。它们都有索引和世界空间位置的键值对。在

比如：

{
  "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中找到离它最近的点。最快的方法是什么？对于dictionary 1中的每个条目，循环遍历dictionary 2中的所有条目并返回最近的条目。在

一些未经测试的伪代码：

^{pr2}$

我想这样的事情会奏效的。问题是，如果dictionary 1中有100个条目，它将是100x1000=1000000次迭代。对我来说，这似乎不太快也不优雅。在

在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树在搜索上更具性能，但构建速度较慢，而且可能更难编写代码。另外，由于八叉树是空间的而不是二进制的，所以它们可以使做一些琐碎的测试变得更容易。在

你可以在这里得到一个python八叉树：http://code.activestate.com/recipes/498121-python-octree-implementation/

如果你要做很多距离检查，你肯定会希望使用mayaapi向量类来进行实际的数学比较，这将比等效的python快得多。如果您对API不太了解，可以从pymel.datatypes获得这些，尽管使用更新的API2版本非常简单。在

Answer 2

你需要一个叫做KD树的东西。用第二个字典中的点构建一个KD树，并查询第一个字典中每个点最近的点。在

我不熟悉maya，如果可以使用scipy，则可以使用this。在

PS：在C++ +{A2}中似乎有一个实现。在