求可无交叉连接二维多边形的相关算法建议

以下是三类经过验证、可稳定满足需求的算法方案：

1. 基于可见性图的最小生成树算法 #

• 实现逻辑：
  1. 先构建所有多边形顶点的可见性图：两个顶点之间存在有效边的判定条件为两点连线不穿过任意多边形内部，仅触碰边或顶点即符合要求
  2. 为每条可见边赋值权重为两点的欧氏距离
  3. 对所有顶点集合运行Kruskal或Prim算法求解最小生成树（MST），提取生成树中跨不同多边形的边，总数刚好为N-1条，天然满足无交叉、不穿过多边形的约束
  4. 若两个多边形之间不存在直接可见的线段，MST会自动选择可见性图中的多段边拼接为合法多段线
• 适用场景：对连接线总长度有最短要求、多边形数量不多的场景
• 优势：逻辑成熟稳定，输出结果最优

2. 基于嵌套层级树的逐层连接算法 #

• 实现逻辑：
  1. 先通过点-in-多边形测试确定所有多边形的嵌套关系：统计每个多边形的父多边形（直接包含它的外层多边形），构建嵌套关系树
  2. 对每一对父子多边形，寻找两点连线不穿过其他多边形的最短路径作为连接线：若两点直接连线合法则用单线段，否则沿着遮挡多边形的边界走最短路径生成多段线
  3. 所有父子对的连接线总数刚好为N-1条，且不会出现交叉，因为所有连接路径都在各自的嵌套层级空间内
• 适用场景：多边形嵌套关系明确、层级较深的场景
• 优势：运行效率远高于可见性图方案，输出的连接线逻辑清晰，不会出现跨层级的冗余长连线

3. 约束德劳内三角剖分算法 #

• 实现逻辑：
  1. 将所有多边形的顶点作为输入点集，执行约束德劳内三角剖分，把多边形的原有边作为约束边加入剖分规则，保证剖分得到的三角形不会穿过输入多边形内部
  2. 从剖分结果的边中过滤出跨不同多边形的合法边
  3. 基于过滤后的边集合构建生成树即可，需要最短总长度时可直接求解MST
• 适用场景：多边形顶点数量多、对运行效率要求高的场景
• 优势：构建效率远高于全量可见性图，输出结果接近最优

实用优化技巧 #

• 若不需要总长度最短的约束，可跳过MST求解步骤，直接用BFS遍历多边形连通关系生成连接边，速度可提升数倍
• 多段线生成可直接复用A*路径规划算法：将所有多边形内部设为障碍区域，起点和终点分别放在待连接的两个多边形边界上，直接搜索最短无碰撞路径即可，灵活度更高

内容的提问来源于stack exchange，提问作者mbison