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

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

您发现您的算法存在什么样的性能问题？我想说，具有合理哈希实现的集合应该表现得相当不错。另一方面，如果您的哈希对于数据来说不是最佳的，则会出现大量冲突，这可能会严重影响性能。

Answer 2

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

要查找此结构中的边缘，您需要使用较大的索引，在顶层查找它并最终得到哈希图。然后采用较小的索引并在第二个哈希图中查找它。