从多边形计算对偶图

Question

任务

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

例子

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

数据

我有一组S多边形。每个多边形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)时间内创建从边（作为键）到多边形的映射。迭代所有多边形的所有边（顺序并不重要）并将值插入到地图中。当插入新值时，如果键已经存在，则您已经找到了一个相邻的多边形 - 将此多边形对放入一个集合中。完成后，该集合将保存所有相邻的多边形对。