algorithm - 从多边形计算对偶图

Question

任务

从一组不重叠（但接触）的多边形计算对偶图。

例子

多边形A、B和C，它们的部分共享坐标 1-22（黄色）和对偶图（蓝色）。

数据

我有一组多边形。每个多边形P _i都表示为坐标的有序列表。多边形P _i的边a - b记为P _i,(a,b)

主意

多边形代表面，因此代表对偶图的节点。要识别多边形P _i的相邻面，只需将P _i的每条边与每个其他多边形P _j的每条边进行比较。如果边由另一个多边形共享，则P _i和P _j是相邻的。

这将创建大量的多个边缘，这些边缘可以在以后移除。

问题

该算法不是很有效，因为它在O(E ² )中运行，其中E表示多边形集合S的边数。

改进思路

在第一步中创建一个边缘索引。这会将运行时间减少到O(2×E) = O(E)

删除每个度数为 2 的节点。（我认为这不会影响对偶图？）

问题

• 我在正确的轨道上吗？
• 是否有任何批准的算法用于此任务？

Answer 1

您可以在O(n)时间内创建从边缘（作为键）到多边形的映射。迭代所有多边形的所有边（顺序不重要）并将值插入到地图中。插入新值时，如果键已存在，则您找到了一个相邻的多边形 - 将此多边形对放入一个集合中。完成后，该集合包含所有相邻的多边形对。