使用水平对齐的多段线连接一组点，而不使它们相交

Question

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

1:直线应该始终在正x方向上移动。p1.x < p2.x < ...

2:两条线永远不能交叉。

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

4:它应该使用尽可能少的多段线(或由我定义的数字)。

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

手动找到解决方案是微不足道的，但我不知道如何用逻辑术语来描述我的过程。我不需要一个最优的解决方案(不管那意味着什么)。它不需要很快。

Point set (Disregard colors)

Connected Points

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

我的下一个想法是，当碰撞发生时，使用暴力方法进行回溯。但这似乎也有点过了。

对于任何好奇的人来说，这些要点实际上是乐谱上的音符。X轴是时间，y轴是节距。多段线表示弹钢琴的机器手指的运动。

Answer 1

我们将找到一个使用最少数量的机器人手指(最少数量的折线)的解决方案。诀窍是将您的输入视为Partially ordered set (或偏序集)。输入中的每个点都是偏序集的一个元素，并且关系( p1.x，p1.y) < (p2.x，p2.y)当且仅当p1.x< p2.x。这基本上意味着具有相同x坐标的两个点彼此是不可比较的。

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

你要找的，是这个偏序集到链中的划分。这是使用Dilworth's Theorem完成的。应该清楚的是，如果有5个点具有相同的x坐标，那么我们至少需要5条不同的折线。迪尔沃思所说的是，如果没有超过5个点的x坐标，那么我们可以得到覆盖所有点的5条折线(链)。它还为我们提供了一个查找这些折线的way，我在这里总结一下：

您只需创建一个二部图G= (U，V，E)，其中U=V=所有输入点的集合，其中(u，v)是G中的一条边，如果u.x < v.x。然后在这个图中找到一条边，M，并考虑当M中有一条边(u，v)时，通过将u和v包括在同一条折线中而形成的一组多段线( maximum matching )。

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

首先，让我们假设只有两条多段线L1和L2。找到它们交叉的第一个实例(最小x坐标)。假设相交的两条线段是AB和CD：

​

​

我们删除AB和CD，代之以添加AD和CB：

​

​

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

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

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

以L1为例，找出它第一次与任何其他多段线相交的时间。在该交叉口，应用如上的交换操作。不断重复此操作，直到L1不与任何其他多段线相交。现在，L1处于“底部”，并且不会与任何其他行交叉。我们现在输出L1作为最终的折线之一，并从我们的算法中删除它。然后，我们对L2重复相同的过程，并在输出后删除它，然后对L3重复此过程，以此类推。