algorithm - 将一组点与水平对齐的折线连接起来，但不相交

Question

我有一组 2D 点，其中所有值都是整数。没有点是相同的。我想通过所有点绘制折线/路径/任何东西，但有一些限制：

1：一条线应始终沿正 x 方向移动。p1.x < p2.x < ...

2：线可能永远不会相互交叉。

3：所有多段线都需要从 x = 0 开始，并在 x-max 结束。

4：它应该使用尽可能少的折线（或我定义的数字）。

我附上了一组样本点的图像。我用铅笔和尺子画了一个手工制作的解决方案。

手动找到解决方案是微不足道的，但我不知道如何用逻辑术语来描述我的过程。我不需要最佳解决方案（无论这意味着什么）。它不需要很快。

点集（忽略颜色）

连接点

我目前的解决方案是沿 x 轴逐步遍历该集合，然后尝试所有可行的组合并选择总垂直运动最低的组合。这在某些情况下有效，但不是全部。而且这似乎使问题过于复杂。

我的下一个想法是在发生碰撞时使用回溯进行蛮力方法。但这似乎也有点多。

对于任何想知道这些点的人实际上是乐谱上的音符。x 轴是时间，y 轴是音高。折线代表机器人手指弹奏钢琴的运动。

标签： algorithmlanguage-agnosticpath-findingrobotics

Answer 1

我们将找到一个使用最少数量的机器人手指（最少多段线）的解决方案。诀窍是将您的输入视为部分有序集（或 poset）。输入中的每个点都是poset的一个元素，并且当且仅当p1.x < p2.x时，关系（p1.x，p1.y）<（p2.x，p2.y）。这基本上意味着具有相同 x 坐标的两个点彼此无法比较。

现在，让我们忘记这个约束：“线可能永远不会相互交叉”。我们会在最后回到它。

您正在寻找的是这个 poset 到链中的分区。这是使用Dilworth 定理完成的。应该清楚的是，如果有 5 个点具有相同的 x 坐标，那么我们至少需要 5 条不同的折线。Dilworth 的说法是，如果没有超过 5 个点的 x 坐标，那么我们可以得到 5 条覆盖所有点的折线（链）。它还为我们提供了一种找到这些折线的方法，我在这里总结一下：

您只需创建一个二分图 G = (U,V,E)，其中 U = V = 所有输入点的集合，如果 ux < vx，则 (u,v) 是 G 中的一条边然后找到最大匹配M，在这个图，并考虑当 M 中有一条边 (u,v) 时，将 u 和 v 包含在同一条折线上形成的折线集。

现在唯一的问题是，其中一些折线可能会相互交叉。我们将看到如何解决这个问题：

首先，让我们假设只有两条折线，L1 和 L2。您会找到它们交叉的第一个实例（最小 x 坐标）。假设两条相交的线段分别是 AB 和 CD：

我们删除 AB 和 CD 并添加 AD 和 CB：

多段线仍然相互交叉，但它们的交叉点已延迟。所以我们可以不断重复这个过程，直到没有交叉点为止。这最多需要 n 次迭代。因此，我们知道如何“解开”两条折线。

[B 位于段 CD 上的边缘情况也以完全相同的方式处理]

现在，假设我们有 k 个不同的折线，最大匹配给了我们：L1，L2，...，Lk。WLOG，让我们假设在 x = 0 时，L1 的 y 坐标低于 L2 的 y 坐标，L2 的 y 坐标低于 L3，依此类推。

取 L1 并找到它第一次与任何其他折线相交的时间。在那个路口，应用上述交换操作。继续重复此操作，直到 L1 不与任何其他折线相交。现在，L1 位于“底部”，并且不与任何其他线交叉。我们现在输出 L1 作为最终折线之一，并将其​​从我们的算法中删除。然后我们对 L2 重复相同的过程，输出后删除它，然后对 L3 重复，以此类推。