algorithm - 二维插值算法

Question

我有两种形状，它们是通道的横截面。我想计算两个定义点之间的中间点的横截面。在这种情况下使用最简单（相对简单？）的算法是什么？

PS：我遇到了几个算法，比如自然邻居和泊松，看起来很复杂。我正在寻找一个可以快速实施的简单解决方案。

编辑：我从标题中删除了“最简单”这个词，因为它可能会产生误导

Answer 1

这很简单：

1. 在每个横截面上，沿横截面的边界以均匀的间隔画出 N 个点。
2. 从横截面 1 上的第 n 个点到横截面 2 上的第 n 个点画直线。
3. 在旧横截面之间的所需距离处取下新横截面。

更简单：

1. 使用现有的横截面之一，无需修改。

我想这第二个建议可能太简单了，但我敢打赌没有人建议更简单的！

根据 OP 的评论进行编辑：（重新评论太多了）

好吧，你确实要求一个简单的方法！我不确定我是否看到与第一种方法相同的问题。如果横截面不是太奇怪（如果它们是凸多边形可能是最好的）并且您没有做任何奇怪的事情，例如将一个横截面的左侧映射到另一个横截面的右侧（从而迫使很多交叉线) 那么该方法应该产生某种合理的横截面。在您建议三角形和矩形的情况下，假设三角形位于其底部，顶部有一个顶点。将该点映射到矩形的左上角，然后沿着连接相应点的两个横截面的边界沿相同方向（顺时针或逆时针）前进。我没有看到任何交叉线，

Answer 2

请注意，您可能需要解决有关高性能标记的答案的一些含糊不清的问题，并将定义他的方法输出的质量。最重要的是，当你n在两个横截面上绘制点时，你确定它们之间的对应关系是什么，即如果你按照高性能标记建议的方式进行，那么标记点的顺序就变得很重要。

我建议同时通过两个横截面旋转（正交）平面，然后在一个横截面上与该平面相交的一组点只需要与在另一个横截面上与该平面相交的一组点相匹配。假设这些集合中的点数没有限制，但它肯定会降低原始情况下对应问题的复杂性。

Answer 3

这是该问题的另一种尝试，我认为这是一个更好的尝试。

给定两个横截面C_1，C_2

将每个都C_i放入具有坐标系的全局参考系中，(x,y)以便它们相对定位的方式有意义。将每个C_i分成上下曲线U_i和L_i。这个想法是你会想要不断地将曲线变形U_1为U_2和。（请注意，如果您愿意，可以扩展此方法以将每条曲线分割成曲线。）L_1L_2C_im

方法如下。对于每个T_i = U_i, or L_i样本n点，确定插值多项式P{T_i}(x)。正如下面适当指出的那样，插值多项式容易受到振荡的影响，尤其是在端点处。代替插值多项式，可以使用更稳健的最小二乘拟合多项式。然后将多项式P{U_1}(x) = a_0 + a_1 * x + ... + a_n * x^n的变形定义P{U_2}(x) = b_0 + b_1 * x + ... + b_n * x^n 为Q{P{U_1},P{U_2}}(x, t) = ( t * a_0 + (1 - t ) b_0 ) + ... + (t * a_n + (1-t) * b_n ) * x^n变形Q被定义在0<=t<=1哪里t定义变形在哪里（即在t=0我们在哪里，U_2在t=1我们在哪里U_1，每隔一段时间，t我们就处于两者的某种连续变形。）完全相同的如下 Q{P{L_1},P{L_2}}(x, t). 这两个变形为您构建了两个横截面之间的连续表示，您可以在任意位置进行采样t。

请注意，这实际上是对两个横截面的两个插值多项式的系数进行线性插值。另请注意，在拆分横截面时，您可能应该限制它们必须在匹配的端点处拆分，否则您的变形中可能会有“孔”。

我希望那很清楚。

编辑：解决了插值多项式中的振荡问题。