algorithm - 从多边形计算对偶图

Question

任务

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

示例

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

数据

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

想法

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

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

问题

该算法效率不高，因为它的运行时间为 O(E²)，其中 E 表示集合 < 的边数em>S 多边形。

改进思路

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

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

问题

• 我走的路正确吗？
• 是否有任何经批准的算法可用于此任务？

Answer 1

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