构建节点间距离相等的路径的最佳方法是什么？

Question

我在2D空间中有一条路径.但节点之间的距离不相等.我正在寻找一种算法,将节点添加到源路径,以便节点之间的距离相等.什么是最佳做法？

示例图片:

Answer 1

几何上不可能为多个任意路径段生成等距点 - 只有当它们的长度共享一个公约数时才有可能.

但是,您可以使用以下方法生成最接近的匹配点集:

1. 您需要首先N在路径段上设置所需的最大点数.这是为了阻止算法无限循环 - 因为在一般情况下,只有无数个分区才能给出确切的答案,而这不是我们想要的.
   • 然而,在可以应用之前,我们需要检查它N + 1是否不小于最长路径与最短路径的比率.如果是,那么我们需要调整它.
2. 对于每个路径段迭代到最大点数N,计算L每个数字的除法长度.对于每个迭代值,我们将Cost变量定义为计算解与理想之间的总差值之和.
3. 然后遍历每个其他路径段.除以它的长度M通过L得到比R:
   • 如果R是整数,那么对于该段,已找到精确解.添加零到Cost
   • 否则拿A = floor(R), B = ceil(R).计算两个单独的成本cost_A = abs(M - L * A)和类似的B.
   • 如果cost_A < cost_B,将C = A此段视为最佳分割计数,反之亦然.记录C.
   • 采取min(cost_A, cost_B)并添加Cost.继续.
4. 请记住跟踪C每个路径段的最佳值列表,以及记录当前计算的"工作列表".还要跟踪min_Cost变量.
   • 如果在每个段的主循环结束时Cost < min_Cost,则更新min_Cost和最佳列表.

以上描述可能看起来有点模糊.这里有一些C#代码 - 道歉,因为我不熟悉C#Mono/Unity的细节,所以你可能不得不在这里或那里替换一些类型名称/函数名称,但算法的要点是希望你想要的.

public static int[] calculateOptimalSplitNumbers(Point[] path, int N)
{
   int no_segs = path.Length - 1;
   if (no_segs <= 1) return null;

   double[] lengths = new double[no_segs];
   for (int i = 0; i < no_segs; i++)
      lengths[i] = Vector.LengthOf(path[i + 1] - path[i]); // replace with the correct unity function?

   int max_ratio = Math.Floor(Math.Max(lengths) / Math.Min(lengths)) - 1;
   if (N < max_ratio)
      N = max_ratio;

   double min_Cost = double.MaxValue;
   int[] min_List = new int[no_segs];

   int[] cur_List = new int[no_segs];
   for (int i = 0; i < no_segs; i++)
   {
      double cost = 0.0;
      for (int j = 0; j < N; j++)
      {
         double L = lengths[i] / (j + 2);
         cur_list[i] = j + 1;

         for (int k = 0; k < no_segs; k++)
         {
            if (k == i) continue;

            double M = lengths[k],
                   R = M / L;
            // path is too short - put no points
            if (R < 1.0) {
               cur_list[k] = 0;
               cost += M - L;
            }

            int A = Math.Floor(R), 
                B = Math.Ceiling(R);
            double cost_A = Math.Abs(M - L * A),
                   cost_B = Math.Abs(M - L * B);
            if (cost_A < cost_B) {
               cur_list[k] = A;
               cost += cost_A;
            }
            else {
               cur_list[k] = B;
               cost += cost_B;
            }
         }
      }

      if (cost < min_Cost) {
         min_Cost = cost;
         System.Array.Copy(cur_List, min_List, no_segs);
      }
   }

   return min_List;
}

该代码采用一系列路径点并返回要放在每个路径段上的点数.如果您需要更多的代码说明,请告诉我,我将编辑更多的评论.