从多边形计算对偶图

Question

任务

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

例子

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

数据

我有一组 S 多边形。每个多边形 P_i 都表示为有序的坐标列表。多边形的边 a — b P_i 表示为 P_i,(a,b)

想法

多边形表示面，因此表示对偶图的节点。要识别多边形 P_i 的相邻面，只需比较 P_{i[=82= 的每条边]} 与每个其他多边形的每条边 P_j。如果边被另一个多边形共享，则 P_i 和 P_j 相邻。

这将创建大量的多边，以后可以将其删除。

问题

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

改进意见

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

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

问题

• 我走的路对吗？
• 这个任务是否有任何批准的算法？

Answer 1

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