用水平对齐的多段线连接一组点而不交叉
Connecting a set of points with horizontally aligned polylines without them crossing
我有一组二维点，其中所有值都是整数。没有点是相同的。我想通过所有点绘制 polylines/paths/whatever，但有一些限制：
1: 一条线应该总是在正 x 方向上移动。 p1.x < p2.x < ...
2：线永远不会交叉。
3：所有折线都需要从 x = 0 开始，到 x-max 结束。
4：折线越少越好（或者我定义的数字）。
我附上了一组示例点的图像。还有我用铅笔和尺子画的手工解决方案。
手动找到解决方案很简单，但我不知道如何用逻辑术语描述我的过程。我不需要最佳解决方案（无论那意味着什么）。不需要很快。
Point set (Disregard colors)
Connected Points
我目前的解决方案是沿着 x 轴遍历集合，然后尝试所有可行的组合并选择总垂直移动量最低的组合。这在某些情况下有效，但并非全部。它似乎使问题过于复杂。
我的下一个想法是在发生碰撞时使用带有回溯的蛮力方法。但这也似乎有点过分了。
对于任何想知道这些点实际上是 sheet 音乐的音符的人。 x 轴是时间，y 轴是音高。多段线表示弹钢琴的机器人手指的运动。
我们将找到一个使用最少数量的机器人手指（最少数量的折线）的解决方案。诀窍是将您的输入视为 Partially ordered set（或偏序集）。输入中的每个点都是偏序集的一个元素，并且关系 (p1.x, p1.y) < (p2.x , p2.y) 当且仅当 p1.x < p2.x。这基本上意味着具有相同 x 坐标的两个点彼此无法比较。
现在，让我们忘记这个约束："Lines may never cross each other"。我们最后再讲。
你要找的是将这个偏序集划分成链。这是使用 Dilworth's Theorem. It should be clear that if there are 5 points with the same x-coordinate, then we need at least 5 different polylines. What Dilworth's says is that if there is no x-coordinate with more than 5 points on it, then we can get 5 polylines (chains) which cover all the points. And it also gives us a way 找到这些多段线来完成的，我在这里总结一下：
您只需创建一个二分图 G = (U,V,E)，其中 U = V = 所有输入点的集合，其中 (u,v) 是 G 中的一条边，如果 u.x < v.x。然后在这个图中找到一个maximum matching, M, 考虑只要在M.
中有一条边(u,v)，把u和v都包含在同一条折线中形成的折线集合
现在唯一的问题是，其中一些折线可能会相互交叉。我们将看看如何解决这个问题：
首先，让我们假设只有两条折线，L1 和 L2。您找到他们交叉的第一个实例（最小 x 坐标）。假设相交的两条线段是AB和CD：
我们删除 AB 和 CD 并添加 AD 和 CB：
多段线仍然相互交叉，但交叉点已延迟。所以我们可以不断重复这个过程，直到没有交叉路口为止。这最多需要 n 次迭代。因此我们知道如何 'untangle' 两条折线。
[B位于CD段的边缘情况也以完全相同的方式处理]
现在，假设我们有k条不同的折线，最大匹配给了我们：L1，L2，...，Lk。 WLOG，让我们假设在x = 0时，L1的y坐标低于L2的y坐标，L2的y坐标低于L3的，依此类推。
取 L1 并找到它与任何其他折线的第一次交叉。在那个十字路口，如上所述应用交换操作。不断重复此操作，直到 L1 不与任何其他多段线交叉。现在，L1 位于 'bottom'，并且不与任何其他线相交。我们现在输出 L1 作为最终折线之一，并将其从我们的算法中删除。然后我们对L2重复同样的过程，输出后删除，对L3重复，以此类推。
我有一组二维点，其中所有值都是整数。没有点是相同的。我想通过所有点绘制 polylines/paths/whatever，但有一些限制：
1: 一条线应该总是在正 x 方向上移动。 p1.x < p2.x < ...
2：线永远不会交叉。
3：所有折线都需要从 x = 0 开始，到 x-max 结束。
4：折线越少越好（或者我定义的数字）。
我附上了一组示例点的图像。还有我用铅笔和尺子画的手工解决方案。
手动找到解决方案很简单，但我不知道如何用逻辑术语描述我的过程。我不需要最佳解决方案（无论那意味着什么）。不需要很快。
Point set (Disregard colors)
Connected Points
我目前的解决方案是沿着 x 轴遍历集合，然后尝试所有可行的组合并选择总垂直移动量最低的组合。这在某些情况下有效，但并非全部。它似乎使问题过于复杂。
我的下一个想法是在发生碰撞时使用带有回溯的蛮力方法。但这也似乎有点过分了。
对于任何想知道这些点实际上是 sheet 音乐的音符的人。 x 轴是时间，y 轴是音高。多段线表示弹钢琴的机器人手指的运动。
我们将找到一个使用最少数量的机器人手指（最少数量的折线）的解决方案。诀窍是将您的输入视为 Partially ordered set（或偏序集）。输入中的每个点都是偏序集的一个元素，并且关系 (p1.x, p1.y) < (p2.x , p2.y) 当且仅当 p1.x < p2.x。这基本上意味着具有相同 x 坐标的两个点彼此无法比较。
现在，让我们忘记这个约束："Lines may never cross each other"。我们最后再讲。
你要找的是将这个偏序集划分成链。这是使用 Dilworth's Theorem. It should be clear that if there are 5 points with the same x-coordinate, then we need at least 5 different polylines. What Dilworth's says is that if there is no x-coordinate with more than 5 points on it, then we can get 5 polylines (chains) which cover all the points. And it also gives us a way 找到这些多段线来完成的，我在这里总结一下：
您只需创建一个二分图 G = (U,V,E)，其中 U = V = 所有输入点的集合，其中 (u,v) 是 G 中的一条边，如果 u.x < v.x。然后在这个图中找到一个maximum matching, M, 考虑只要在M.
中有一条边(u,v)，把u和v都包含在同一条折线中形成的折线集合现在唯一的问题是，其中一些折线可能会相互交叉。我们将看看如何解决这个问题：
首先，让我们假设只有两条折线，L1 和 L2。您找到他们交叉的第一个实例（最小 x 坐标）。假设相交的两条线段是AB和CD：
我们删除 AB 和 CD 并添加 AD 和 CB：
多段线仍然相互交叉，但交叉点已延迟。所以我们可以不断重复这个过程，直到没有交叉路口为止。这最多需要 n 次迭代。因此我们知道如何 'untangle' 两条折线。
[B位于CD段的边缘情况也以完全相同的方式处理]
现在，假设我们有k条不同的折线，最大匹配给了我们：L1，L2，...，Lk。 WLOG，让我们假设在x = 0时，L1的y坐标低于L2的y坐标，L2的y坐标低于L3的，依此类推。
取 L1 并找到它与任何其他折线的第一次交叉。在那个十字路口，如上所述应用交换操作。不断重复此操作，直到 L1 不与任何其他多段线交叉。现在，L1 位于 'bottom'，并且不与任何其他线相交。我们现在输出 L1 作为最终折线之一，并将其从我们的算法中删除。然后我们对L2重复同样的过程，输出后删除，对L3重复，以此类推。