时间戳

首页 > 解决方案 > 寻找三角形镶嵌的最近邻

python - 寻找三角形镶嵌的最近邻

问题描述

我有一个如图所示的三角形镶嵌。在此处输入图像描述

给定N曲面细分中的三角形数量，我有一个N X 3 X 3数组，用于存储(x, y, z)每个三角形的所有三个顶点的坐标。我的目标是为每个三角形找到共享相同边的相邻三角形。这是一个复杂的部分是我不重复邻居计数的整个设置。也就是说，如果三角形j已经算作三角形的邻居i，那么三角形i不应再算作三角形的邻居j。这样，我想要一个地图存储每个索引三角形的邻居列表。如果我从 index 中的三角形开始i，那么 indexi将有三个邻居，而所有其他人将有两个或更少。作为一个例子，假设我有一个存储三角形顶点的数组：

import numpy as np
vertices = np.array([[[2.0, 1.0, 3.0],[3.0, 1.0, 2.0],[1.2, 2.5, -2.0]],
                     [[3.0, 1.0, 2.0],[1.0, 2.0, 3.0],[1.2, -2.5, -2.0]],
                     [[1.0, 2.0, 3.0],[2.0, 1.0, 3.0],[3.0, 1.0, 2.0]],
                     [[1.0, 2.0, 3.0],[2.0, 1.0, 3.0],[2.2, 2.0, 1.0]],
                     [[1.0, 2.0, 3.0],[2.2, 2.0, 1.0],[4.0, 1.0, 0.0]],
                     [[2.0, 1.0, 3.0],[2.2, 2.0, 1.0],[-4.0, 1.0, 0.0]]])

假设我从 vertex index 开始计数2，即带有 vertices 的那个[[1.0, 2.0, 3.0],[2.0, 1.0, 3.0],[3.0, 1.0, 2.0]]，那么，我希望我的输出类似于：

neighbour = [[], [], [0, 1, 3], [4, 5], [], []].

更新： 根据@Ajax1234 的回答，我认为存储输出的好方法就像@Ajax1234 所展示的那样。但是，该输出存在歧义，从某种意义上说，不可能知道谁的邻居是谁。虽然示例数组不好，但我有一个来自二十面体的实际顶点，那么如果我从一个给定的三角形开始，我保证第一个有 3 个邻居，其余两个邻居（直到所有三角形计数耗尽） . 在这方面，假设我有以下数组：

vertices1 = [[[2, 1, 3], [3, 1, 2], [1, 2, -2]], 
            [[3, 1, 2], [1, 2, 3], [1, -2, 2]], 
            [[1, 2, 3], [2, 1, 3], [3, 1, 2]], 
            [[1, 2, 3], [2, 1, 3], [2, 2, 1]],
            [[1, 2, 3], [2, 2, 1], [4, 1, 0]], 
            [[2, 1, 3], [2, 2, 1], [-4, 1, 0]],
            [[3, 1, 3], [2, 2, 1], [-4, 1, 0]],
            [[8, 1, 2], [1, 2, 3], [1, -2, 2]]]

@Ajax1234 在下面的答案中显示的 BFS 算法给出了输出

[0, 1, 3, 7, 4, 5, 6]

而如果我只是交换最后一个元素的位置，这样

vertices2 = [[[2, 1, 3], [3, 1, 2], [1, 2, -2]], 
            [[3, 1, 2], [1, 2, 3], [1, -2, 2]], 
            [[1, 2, 3], [2, 1, 3], [3, 1, 2]], 
            [[1, 2, 3], [2, 1, 3], [2, 2, 1]],
            [[1, 2, 3], [2, 2, 1], [4, 1, 0]], 
            [[8, 1, 2], [1, 2, 3], [1, -2, 2]],
            [[2, 1, 3], [2, 2, 1], [-4, 1, 0]],
            [[3, 1, 3], [2, 2, 1], [-4, 1, 0]]]

这给出了一个输出

[0, 1, 3, 4, 5, 6, 7].

这有点模棱两可，因为网格中的位置根本没有改变，它们只是交换了。因此，我希望有一个一致的搜索方式。例如，第一次在索引 2 处搜索邻居时[0, 1, 3]同时给出vertices1和vertices2，现在我希望搜索在索引 0 处，它什么也没找到，因此转到下一个元素 1 应该找到 的索引和7的vertices1索引5。vertices2因此，电流输出应分别为[0, 1, 3, 7]、[0, 1, 3, 5]forvertices1和vertices2。接下来我们去 index 3，依此类推。在我们用尽所有搜索之后，第一个的最终输出应该是

[0, 1, 3, 7, 4, 5, 6]

第二个应该

[0, 1, 3, 5, 4, 6, 7].

实现这一目标的有效方法是什么？

标签： pythonperformancegraph-algorithmtriangulationnumba

解决方案

感谢@Ajax1234的指导，我找到了答案。根据您比较列表元素的方式，有一个小的复杂性。这是一种工作方法：

import numpy as np
from collections import deque
import time
d = [[[2, 1, 3], [3, 1, 2], [1, 2, -2]], 
     [[3, 1, 2], [1, 2, 3], [1, -2, 2]], 
     [[1, 2, 3], [2, 1, 3], [3, 1, 2]], 
     [[1, 2, 3], [2, 1, 3], [2, 2, 1]],
     [[1, 2, 3], [2, 2, 1], [4, 1, 0]],
     [[2, 1, 3], [2, 2, 1], [-4, 1, 0]],
     [[3, 1, 3], [2, 2, 1], [-4, 1, 0]]]
def bfs(d, start):
  queue = deque([d[start]])
  seen = [start]
  results = []
  while queue:
    _vertices = queue.popleft()
    current = [[i, a] for i, a in enumerate(d) if len([x for x in a if x in _vertices])==2 and i not in seen]
    if len(current)>0:
        current_array = np.array(current, dtype=object)
        current0 = list(current_array[:, 0])
        current1 = list(current_array[:, 1])
        results.extend(current0)
        queue.extend(current1)
        seen.extend(current0)
  return results

time1 = time.time()
xo = bfs(d, 2)
print(time.time()-time1)
print(bfs(d, 2))

对于 size 的数组(3000, 3, 3)，代码当前需要18几秒钟才能运行。如果我添加@numba.jit(parallel = True, error_model='numpy')，那么它实际上需要30几秒钟。可能是因为queue不支持numba。如果有人能建议如何使这段代码更快，我会很高兴。

更新

代码中有一些冗余，现在已被删除，代码在14几秒钟内运行，而不是30几秒钟，对于 a 的dsize (4000 X 3 X 3)。仍然不是很出色，但取得了不错的进展，现在代码看起来更干净了。

推荐阅读