无自交单笔画连接Voronoi曲线的算法及实现问题求助

我有一台无法像常规FDM打印机那样轻易停机的材料挤出机器人，需要生成无自交的单笔画路径来连接Voronoi等图案的顶点。目前已经生成了Voronoi图案，并用C#脚本（基于Grasshopper/Rhino）通过暴力迭代的2-opt方法求解TSP来连接中心点，但生成的路径会穿过多余的几何结构，求解决办法。

现有代码如下：

public class Script_Instance : GH_ScriptInstance
{
#region Utility functions
  /// <summary>Print a String to the [Out] Parameter of the Script component.</summary>
  /// <param name="text">String to print.</param>
  private void Print(string text) { /* Implementation hidden. */ }
  /// <summary>Print a formatted String to the [Out] Parameter of the Script component.</summary>
  /// <param name="format">String format.</param>
  /// <param name="args">Formatting parameters.</param>
  private void Print(string format, params object[] args) { /* Implementation hidden. */ }
  /// <summary>Print useful information about an object instance to the [Out] Parameter of the Script component. </summary>
  /// <param name="obj">Object instance to parse.</param>
  private void Reflect(object obj) { /* Implementation hidden. */ }
  /// <summary>Print the signatures of all the overloads of a specific method to the [Out] Parameter of the Script component. </summary>
  /// <param name="obj">Object instance to parse.</param>
  private void Reflect(object obj, string method_name) { /* Implementation hidden. */ }
#endregion

#region Members
  /// <summary>Gets the current Rhino document.</summary>
  private readonly RhinoDoc RhinoDocument;
  /// <summary>Gets the Grasshopper document that owns this script.</summary>
  private readonly GH_Document GrasshopperDocument;
  /// <summary>Gets the Grasshopper script component that owns this script.</summary>
  private readonly IGH_Component Component;
  /// <summary>
  /// Gets the current iteration count. The first call to RunScript() is associated with Iteration==0.
  /// Any subsequent call within the same solution will increment the Iteration count.
  /// </summary>
  private readonly int Iteration;
#endregion

  /// <summary>
  /// This procedure contains the user code. Input parameters are provided as regular arguments,
  /// Output parameters as ref arguments. You don't have to assign output parameters,
  /// they will have a default value.
  /// </summary>
  private void RunScript(List<Point3d> pts, int n, ref object A)
  {
    pts.Add(pts[0]);
    var route = pts.ToArray();
    var shortest = Length(route);
    for (var k = 0; k < n; k++)
      for (var i = 1; i < route.Length - 1; i++)
        for (var j = i + 1; j < route.Length; j++)
          route = Swap(route, ref shortest, i, j);
    A = route;
  }

  // <Custom additional code> 
  double Length(Point3d[] route)
  {
    var d = 0.0;
    for(var i = 0; i < route.Length - 1; i++)
      d += route[i].DistanceTo(route[i + 1]);
    return d;
  }
  Point3d[] Swap(Point3d[] route, ref double shortest, int i, int j)
  {
    var swapped = (Point3d[]) route.Clone();
    Array.Reverse(swapped, i, j - i);
    var len = Length(swapped);
    if (len < shortest)
    {
      shortest = len;
      return swapped;
    }
    return route;
  }
  // </Custom additional code> 
}

问题根源 #

现有代码是多次迭代的2-opt局部搜索算法，只以路径总长度最短为目标，完全没考虑路径与Voronoi几何结构的碰撞/穿越问题，暴力交换顶点顺序必然导致路径直接穿过Voronoi的边或单元格，不符合机器人运动的几何约束。

解决方案 #

1. 基于Voronoi图的欧拉路径生成（最优单笔画方案）

Voronoi图是平面嵌入图，若构造欧拉回路/路径，能直接得到无自交的单笔画路径，无需TSP：

• 检查Voronoi图顶点度数：所有顶点度数为偶数则存在欧拉回路；恰好两个顶点度数为奇数则存在欧拉路径
• 实现步骤：
  • 提取Voronoi图的边结构，而非只取中心点
  • 用Hierholzer算法遍历所有边，生成欧拉路径/回路
  • 若必须仅连接中心点，可调整路径为沿Voronoi边连接相邻中心点

2. 带几何约束的TSP改进

若要保留TSP逻辑，需加入路径不穿越Voronoi结构的约束：

• 修改2-opt交换的判断条件：除了比较长度，还要检查交换后的路径段是否与Voronoi边/单元格边界相交
• 修改后的代码示例（新增几何约束检查）：

public class Script_Instance : GH_ScriptInstance
{
#region Utility functions
  private void Print(string text) { /* Implementation hidden. */ }
  private void Print(string format, params object[] args) { /* Implementation hidden. */ }
  private void Reflect(object obj) { /* Implementation hidden. */ }
  private void Reflect(object obj, string method_name) { /* Implementation hidden. */ }
#endregion

#region Members
  private readonly RhinoDoc RhinoDocument;
  private readonly GH_Document GrasshopperDocument;
  private readonly IGH_Component Component;
  private readonly int Iteration;
#endregion

  // 新增Voronoi边列表作为输入约束
  private void RunScript(List<Point3d> pts, List<Line> voronoiEdges, int n, ref object A)
  {
    pts.Add(pts[0]);
    var route = pts.ToArray();
    var shortest = Length(route);
    for (var k = 0; k < n; k++)
      for (var i = 1; i < route.Length - 1; i++)
        for (var j = i + 1; j < route.Length; j++)
          route = SwapWithConstraint(route, ref shortest, i, j, voronoiEdges);
    A = route;
  }

  double Length(Point3d[] route)
  {
    var d = 0.0;
    for(var i = 0; i < route.Length - 1; i++)
      d += route[i].DistanceTo(route[i + 1]);
    return d;
  }

  // 带几何约束的交换方法
  Point3d[] SwapWithConstraint(Point3d[] route, ref double shortest, int i, int j, List<Line> voronoiEdges)
  {
    var swapped = (Point3d[]) route.Clone();
    Array.Reverse(swapped, i, j - i);
    
    // 检查交换后的路径段是否与Voronoi边相交
    bool hasIntersection = false;
    // 检查交换产生的新路径段
    if(i > 0)
    {
      hasIntersection |= IsSegmentIntersectVoronoi(route[i-1], swapped[i], voronoiEdges);
    }
    if(j < route.Length - 1)
    {
      hasIntersection |= IsSegmentIntersectVoronoi(swapped[j-1], route[j], voronoiEdges);
    }
    // 检查交换区间内的路径段
    for(int m = i; m < j-1; m++)
    {
      hasIntersection |= IsSegmentIntersectVoronoi(swapped[m], swapped[m+1], voronoiEdges);
    }

    if(!hasIntersection)
    {
      var len = Length(swapped);
      if (len < shortest)
      {
        shortest = len;
        return swapped;
      }
    }
    return route;
  }

  // 判断线段是否与Voronoi边相交（排除端点重合情况）
  bool IsSegmentIntersectVoronoi(Point3d p1, Point3d p2, List<Line> voronoiEdges)
  {
    foreach(var edge in voronoiEdges)
    {
      var seg1 = new Line(p1, p2);
      if(Rhino.Geometry.Intersect.Intersection.LineLine(edge, seg1, out double t, out double s))
      {
        // 用微小阈值避免浮点精度问题
        if(t > 1e-6 && t < 1 - 1e-6 && s > 1e-6 && s < 1 - 1e-6)
          return true;
      }
    }
    return false;
  }
}

3. 街道TSP变体（沿Voronoi边移动）

将问题转化为街道TSP，路径只能沿Voronoi边移动，自然不会穿过多余结构：

• 构建中心点之间的最短路径（沿Voronoi边的路径）作为TSP的距离矩阵，替代欧氏距离
• 用带约束的距离矩阵求解TSP，得到的路径会沿Voronoi边移动，无穿越问题

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