邻居搜索算法

Question

我有一个STL文件，其中包含坐标(x,y,z) 3点(p0, p1, p2)的一个三角形。这些三角形代表3D表面f(x,y,z)。 STL文件可能有超过1000个三角形来表示复杂的几何图形。

对于我的应用程序，我需要知道stl文件中每个三角形条目的相邻三角形。这意味着对于每个三角形，我必须挑选3对点pair1=(p0,p1), pair2=(p0,p2), pair3= (p1,p2)并将它们与集合中其他三角形中的一对点进行比较

实现此目的的最佳和最有效的算法是什么？我可以使用hashtree，hashmap吗？

Answer 1

将网格表示更改为点表和三角面对表。 STL要求所有三角形都连接在它们的顶点上，因此不会切割边缘，这意味着相邻三角形总是共享一个完整边缘。

double pnt[points][3]; 
int tri[triangles][3]; 

的pnt应该是所有不同点的列表（索引排序它来提高速度的高点数量）。 tri应该包含3个用于三角形的点的索引。对它们进行排序（asc或desc）以提高匹配速度。

现在，如果任何三角形tri[i]共享相同的边缘，如tri[j]，那么这两个是相邻的三角形。

if ((tri[i][0]==tri[j][0])&&(tri[i][1]==tri[j][1]) 
    ||(tri[i][0]==tri[j][1])&&(tri[i][1]==tri[j][2])) triangles i,j are neighbors 

添加所有的组合...

如果你只需要邻近的点，然后找到包含这些三角形使用点和所有其他的点是邻居所有三角形

要加载STL这样的结构做到这一点：

1. 明确pnt[],tri[]列表/表个
2. 过程STL

3. 的每个三角形的三角形的每个点

   看它是否在pnt[]如果是使用其指数新triangle。如果不添加新的point到pnt并使用其新索引triangle。当所有3分完成时，新增triangle至tri。

提高pnt[]性能

添加索引排序为pnt[]通过检查point已经存在于pnt的任何坐标例如x并提高性能来分类的。

因此，尽管加点以来最大的x这是xi>=pnt[i0][0]通过二进制搜索，然后扫描所有点pnt直到x十字架xi所以xi<pnt[i1][0]这样就不需要检查所有点的(xi,yi,zi)到pnt[]发现指数。

如果这是太慢了（通常如果点的数量是更大然后40000），您可以通过细分指数进一步提高性能排序（将索引排序到尺寸有限的部分页面，如8192点）

提高tri[]性能

您还可以按tri[i][0]对tri[]进行排序，因此您可以使用类似于pnt[]的二分查找。

Answer 2

我建议用hashmap要去哪里值是sets（基于树）到Tringles，键引用的是那些对Points（让我们称之为这些对简单Sides），并会考虑到一些散列函数考虑到Side（a，b）的散列应该等于（b，a）的散列的属性。

某种算法：

1. 读3 Points并从他们3 Sides和Triangle创建。
2. 添加一切都交给hashmap：map[side[i]].insert(tringle)
3. 重复1-2，直到你读所有的数据

现在你有一个充满数据的地图。关于填充的复杂性：插入hashmap是常数时间在平均（它也依赖于哈希函数）和插入的复杂性成set是对数所以filleng数据的完整复杂性是O(n*logm)其中n是Sides和m的数目是Tringles的平均数，具有相同的Side。

通常每个set将包含约4 Triangles：1 + 3侧邻居，因此logm相对较小（比较n），并且可以不考虑（假设它是一个常数）。这些建议导致我们得出某种结论：填充的最佳情况复杂度为O(n)（无碰撞，无重整等），最差为O(n*logn)（最差情况下插入nSides,1平均情况在地图中并按logn情况插入成一组意味着所有Tringles共享相同的Side）。

我们得到所有侧邻居一些Triangle：

1. 获取所有3 sets的每个Side是Triangle（如set[i] = map[triangle.sides[i]]
的3 sets的
2. 获取路口（不含triangle只拿到。它的旁边邻居）
3. 完成

关于获得旁边邻居的复杂性：线性相关关于sets的大小并且与正常情况下的'n'相比相对较小。

注：要获得不侧 -neighbours但点 -neighbours（假设邻居被称为任意2 Triangles与普通Point不Side）只需填写sets与Points而不是Sides。上述有关时间复杂性的假设对常量保持不变。