擅长:python、mysql、java
<p>您可以使用<a href="https://docs.scipy.org/doc/scipy/reference/generated/scipy.spatial.cKDTree.html#scipy.spatial.cKDTree" rel="nofollow noreferrer">scipy.spatial.cKDTree</a>。
使用KD树,您可以在大约O(N*log(M)*k)的情况下解决问题,其中N是点云中的点数,M是网格中的顶点数,k是一个顶点的“相邻”三角形的平均数</p>
<ol>
<li>在网格顶点上构建KD树:</li>
</ol>
<pre><code>tr = cKDTree(Mesh_vertexs)
</code></pre>
<ol start=“2”>
<li>构建哈希表<code>vertex -> list of "adjoining" triangles</code></li>
<li>学习找出点和三角形之间的距离(如果你不能)
那么该算法的伪码是非常简单的:</li>
</ol>
<pre><code>for point in point_cloud:
d,idx_of_point_in_mesh = tree.query(point)
for triangle in Mesh_Triangles_near_vertex[idx_of_point_in_mesh]:
d = min(d, distance(triangle,point))
min_distance[point] = d
</code></pre>
<p>为了估计性能,对于网格中的10^6个顶点,一个查询<code>tree.query (point)</code>在我的笔记本电脑上进行<code>27.5 µs ± 235 ns</code>。
对于10^6个点的云,时间将是<code>27.5 µs * 10 ^ 6 = 27sec</code>+计算每个点的距离(三角形,点)的成本</p>