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

Question

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

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

有没有更聪明的算法呢？

Answer 1

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

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 边缘并共享它吗？

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