algorithm - 如何在两者之间获得更小的分段线性曲线？

Question

我有两条分段线性曲线 c1 和 c2，我想要一条新的分段线性曲线 c3 作为 c1 和 c2 的较小部分。

是否有一个简洁的算法来获取 c3？

他们的观点是:

C1          C2          C3  
0   1       0   1.5     0   1
1   1       2   1.5     1   1
2   2       3.5 3       1.5 1.5
3   2       4   3       2   1.5
3   3       4   3.5     2.5 2
4   3       5   3.5     3   2
4   4                   3   2.5
5   4                   3.5 3
                        4   3
                        4   3.5
                        5   3.5

Answer 1

我建议使用以下方法来确定曲线。这条曲线将形成一个区域的边界，否则该区域将受到 x=[0, 5] 的限制并向负 Y 值开放。我假设输入中没有循环或向后曲线。

以下步骤:

1. 规范化两条曲线的大小:它们都应该有相同数量的线段，这些线段使用相同的上下 X 位置，您可以通过插值和插入额外的点来实现。使用相同数量的点和相同的 X 位置不起作用，因为有时在相同的 X 位置有多个点。这可能意味着一条归一化曲线的一段由两个相等的点定义，但这对于例如位置 x=3，它使整体思考和调试更容易。
2. 确定交叉点:每当 Y 位置(无论是 C1 还是 C2 在下方)的顺序在一个段内发生变化时，两条线之间必须有一个交叉点。确定这一点并将每条曲线中的线段替换为两条线段。第二次运行此步骤不应插入额外的点并在 C1 和 C2 中产生相同数量的点。
3. 通过从每个点索引中选择具有最低 Y 位置的点来形成第三条曲线。在这里你回到单点思考，而不是分段思考，这就是上面的准备工作所必需的。