将一组点与水平对齐的折线连接而没有交叉

Question

几天来我一直在尝试解决这个问题，但是我找不到一个好的解决方案。

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

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

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

3：所有折线必须从x = 0开始并以x-max结尾。

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

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

手动找到解决方案很简单，但是我不知道如何用逻辑术语描述我的过程。我不需要最佳解决方案（无论那是什么意思）。不需要很快。

Point set (Disregard colors)

Connected Points

我当前的解决方案是沿x轴遍历该集合，然后尝试所有可行的组合，并选择垂直移动总数最低的组合。这在某些情况下有效，但并非全部。而且似乎使问题变得更加复杂。

我的下一个想法是在发生碰撞时采用回溯的蛮力方法。但这似乎也很多。

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

Answer 1

我们将找到一种使用最少数量的机械手手指（最少数量的折线）的解决方案。诀窍是将您的输入视为Partially ordered set（或位姿）。输入中的每个点都是位姿的元素，并且当且仅当p1.x

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

您正在寻找的是将这个摆球分割成多个链条。使用Dilworth's Theorem完成。应该清楚的是，如果有5个点具有相同的x坐标，那么我们至少需要5条不同的折线。迪尔沃思（Dilworth）说的是，如果不存在x坐标超过5个点的坐标，那么我们可以获得5条覆盖所有点的折线（链）。而且它还给我们提供了way来找到这些折线，我在这里总结一下：

您只创建了二部图G =（U，V，E），其中U = V =所有输入点的集合，并且如果u.x maximum matching，M，并考虑在M中存在边（u，v）的情况下，通过在同一折线中包含u和v形成的折线集合。

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

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

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

多义线仍彼此交叉，但其交叉点已延迟。因此，我们可以继续重复此过程，直到没有交叉为止。这最多需要n次迭代。因此，我们知道如何“解缠”两条折线。

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

现在，假设我们有k条不同的多义线，最大匹配已赋予我们：L1，L2，...，Lk。 WLOG，让我们假设在x = 0时，L1的y坐标低于L2的y坐标，后者低于L3的y坐标，依此类推。

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