0

我有一个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)并将它们与集合中其他三角形中的一对点进行比较

实现此目的的最佳和最有效的算法是什么？我可以使用哈希树、哈希图吗？

4

2 回答 2

1

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

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

应该是所有不同点的pnt列表（索引排序以提高高点计数的速度）。应该包含三角形中使用的 3 个点的tri索引。对它们进行排序（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[]如果是的话，将它的索引用于 new triangle。如果不添加 new并将其索引用于pointnew 。当所有 3 点完成后添加新的.pnttriangletriangletri

提高pnt[]性能

pnt[]例如，为按任何坐标排序添加索引排序，x并提高检查是否point已经存在于pnt.

因此，在通过二进制搜索添加到具有最大(xi,yi,zi)点pnt[]的查找索引时，然后扫描所有点直到交叉，这样您就不需要检查所有点。xxi>=pnt[i0][0]pntxxixi<pnt[i1][0]

如果这太慢（通常如果点数大于 40000），您可以通过分段索引排序来提高性能（将索引排序划分为有限大小的分段页面，如 8192 点）

提高tri[]性能

您还可以对tri[]by进行排序，tri[i][0]以便您可以使用类似于pnt[].

于 2017-02-10T15:10:11.317 回答
0

我建议使用hashmapwhere值（sets基于树）对_等于 (b,a) 的哈希值。TringlesPointsSidesSide

某种算法：

  1. 阅读 3Points并从中创建 3Sides和Triangle.
  2. 将所有内容添加到hashmap：map[side[i]].insert(tringle)
  3. 重复 1-2 直到读完所有数据

现在您有了一个包含填充数据的地图。关于填充的复杂性：插入平均hashmap是常数时间（它也取决于散列函数）并且插入 a 的复杂度set是对数的，因此填充数据的完整复杂度是O(n*logm)其中n的数量Sides和平均m数量Tringles一样Side。

通常每个set将包含大约 4 Triangles: 1 + 3 个边邻，因此logm相对较小（与 相比n）并且可以不考虑（假设它是一个常数）。这些建议使我们得出某种结论：填充的最佳情况复杂度是O(n)（没有冲突，没有重新散列等），最坏情况是O(n*logn)（最坏情况下在 map 中插入平均情况并通过n Sides情况插入一组意味着所有共享一样）。1lognTringlesSide

现在让所有的邻居获得一些Triangle：

  1. 获取所有 3sets个Side（Triangle例如set[i] = map[triangle.sides[i]].
  2. 获取这 3 个的交集sets（排除triangle仅获取其旁边的邻居）。
  3. 完毕。

关于获取边邻的复杂性：线性依赖于的大小，sets并且与正常情况下的“n”相比相对较小。

注意：要获得不是边-neighbours 而是点-neighbours（假设邻居被称为任何 2Triangles与 common Pointnot Side）只需填写sets而Points不是Sides。上述关于时间复杂度的假设适用于常数。

于 2017-02-10T15:32:41.723 回答