连接无交叉点的二维多边形的算法

Question

我正在寻找一种生成连接多边形的线（或多段线，如果需要）的算法。

输入：包含 N 个多边形及其顶点坐标。多边形不相交，但可能在彼此内部。
输出：连接

的 N-1 条线（或折线，如有必要）的顶点

规则：

• 连接线不能相交
• 连接线不能与多边形相交
• 连接线可以触及lines/vertices个多边形

示例图片：

有什么建议吗？

Answer 1

借用Kruskal的剧本，多一个多边形，

1. 找到最近的一对多边形（一般来说，一个多边形实际上可以是一组有连接桥的多边形）；

2. 用直线段将它们在最近的点连接起来。

通过采用最近的连接，我们可以保证它的内部不会接触任何不应该接触的东西（否则交叉会产生更短的连接）。