graphics - 从多边形网格中寻找唯一边的算法

Question

我正在寻找一种好的算法，它可以从一组多边形数据中为我提供独特的边缘。在这种情况下，多边形由两个数组定义。一个数组是每个多边形的点数，另一个数组是顶点索引列表。

我有一个正在运行的版本，但是当达到超过 500,000 个多边形时性能会变慢。我的版本遍历每个面并将每个边的排序顶点添加到 stl::set。我的数据集将主要是三角形和四边形，并且大多数边将被共享。

有没有更聪明的算法呢？

score 4 · Accepted Answer

只是为了澄清，你想要这样的多边形列表：

A +-----+ B
   \    |\
    \ 1 | \
     \  |  \
      \ | 2 \
       \|    \
      C +-----+ D

然后不是这样的边缘：

A - B -+
B - C  +- first polygon
C - A -+

B - D -+
D - C  +- second polygon
C - B -+

那么您要删除重复的 B - C 与 C - B 边缘并共享它吗？

您的算法遇到了什么样的性能问题？我想说一个具有合理哈希实现的集合应该执行得很好。另一方面，如果您的哈希对数据不是最佳的，您将遇到很多可能严重影响性能的冲突。

score 4 · Accepted Answer

是
使用双哈希映射。
每条边都有两个索引 A，B。假设 A > B。
第一个顶级哈希映射将 A 映射到另一个哈希映射，该哈希映射又将 B 映射到某个值，该值表示您想要的关于每条边的信息。（或者如果您不需要保留边缘信息，则只是一个布尔值）。
本质上，这创建了一个由哈希映射组成的两级树。

要在这个结构中查找一个边，你需要更大的索引，在顶层查找它并最终得到一个哈希映射。然后取较小的索引并在第二个哈希图中查找它。

score 2 · Accepted Answer

你俩都是对的。使用良好的哈希集已使性能远远超出所需水平。我最终滚动了我自己的小哈希集。

边的总数将在 N/2 和 N 之间。N 是网格中唯一顶点的数量。所有共享边都是 N/2，所有唯一边都是 N。从那里我分配一个 uint64 缓冲区并将我的索引打包到这些值中。使用一小组独特的表格，我可以快速找到独特的边缘！

score 1 · Accepted Answer

这是 Blender 中使用的边缘散列的 C 实现，正是为了从面快速创建边缘，可能会为其他人制作自己的边缘提供一些提示。

score 0 · Accepted Answer

首先，您需要确保您的顶点是唯一的。也就是说，如果您只想在某个位置有一条边。然后我使用这个数据结构

typedef std::pair<int, int> Edge;

Edge sampleEdge;

std::map<Edge, bool> uniqueEdges;

边包含按排序顺序构成边的顶点索引。因此，如果 sampleEdge 是由索引号为 12 和 5 的顶点组成的边，则 sampleEdge.first = 5 和 sampleEdge.12

然后你可以做

uniqueEdges[sampleEdge] = true;

对于所有的边缘。uniqueEdges 将保存所有独特的边缘。

5 回答 5