c++ - 具有不同长度的两个 vector 数组的线性插值

Question

我有两条曲线。一种是手绘的，另一种是手绘的平滑版本。
每条曲线的数据存储在2个独立的向量数组中。
时间增量也存储在手绘曲线向量中，因此我可以重播绘制过程，使其看起来自然。

现在，我需要将时间增量从曲线1（原始输入）传输到曲线2（已平滑的曲线）。

有时，第一个向量的大小大于，有时小于第二个向量。
（取决于输入绘制速度）

所以我的问题是：如何用正确的值填充向量PenSmoot.time？

情况1：输入向量较大

PenInput.time[0] = 0         PenSmoot.time[0] = 0
PenInput.time[1] = 5         PenSmoot.time[1] = ?
PenInput.time[2] = 12        PenSmoot.time[2] = ?
PenInput.time[3] = 2         PenSmoot.time[3] = ?
PenInput.time[4] = 50        PenSmoot.time[4] = ?
PenInput.time[5] = 100
PenInput.time[6] = 20
PenInput.time[7] = 3
PenInput.time[8] = 9
PenInput.time[9] = 33

情况2：输入向量较小

PenInput.time[0] = 0         PenSmoot.time[0] = 0
PenInput.time[1] = 5         PenSmoot.time[1] = ?
PenInput.time[2] = 12        PenSmoot.time[2] = ?
PenInput.time[3] = 2         PenSmoot.time[3] = ?
PenInput.time[4] = 50        PenSmoot.time[4] = ?
                             PenSmoot.time[5] = ?
                             PenSmoot.time[6] = ?
                             PenSmoot.time[7] = ?
                             PenSmoot.time[8] = ?
                             PenSmoot.time[9] = ?

简单表示：

PenInput holds the whole data of a drawn curve (Raw Input)

PenInput.x         // X coordinate)
PenInput.y         // Y coordinate)
PenInput.pressure  // The pressure of the pen)
PenInput.timetotl  // Total elapsed time)
PenInput.timepart  // Time fragments)

PenSmoot holds the data of the massaged (smoothed,evenly distributed) curve of PenInput

PenSmoot.x         // X coordinate)
PenSmoot.y         // Y coordinate)
PenSmoot.pressure  // Unknown - The pressure of the pen)
PenSmoot.timetotl  // Unknown - Total elapsed time)
PenSmoot.timepart  // Unknown - Time fragments)

这是我的结构。

struct Pencil 
{
    sf::VertexArray vertices;
    std::vector<int> pressure;
    std::vector<sf::Int32> timetotl;
    std::vector<sf::Int32> timepart;
};

Answer 1

[此答案已根据对该问题的编辑进行了广泛修订。]

好的，在我看来，您几乎只需要与这些点平行地插入时间戳即可。

我猜想传入的数据是按点数组（例如X，Y坐标）和时间增量数组的顺序排列的，每个数均相同，所以时间增量N告诉您时间从N-1点到达N点。

当您对点进行插值时，您可能会想要智能地进行。例如，在问题所示的形状中，我们看起来像两条接近的直线，一条直线为正斜率，另一条直线为负斜率。根据图片，这由263点组成。我们可以通过选择两个端点加上两条线相交处的一个点，将其减少到三个点，并且仍然可以相当合理地表示原始形状。

不过，我们可能不需要走那么远。特别是考虑到时间，我们可能希望至少使用7个点作为输出-每个彩色段的每个端点一个。那将给我们6个直线段。假设它们位于点0、30、140、180、200、250和263。

然后，我们将在时间增量上使用完全相同的细分。将增量从0累加到30，以获得第一段的平均速度。将31到140的增量相加，以得出第二段的平均速度（依此类推直至末尾）。

增加点数的方法大致相同。我们需要确切地查看用于创建一对输出点的输入点。举一个简单的例子，假设我们产生的输出恰好是输入点数的两倍。然后，我们将恰好在每对输入点之间的中间插入时间增量。

在问题所示的情况下，我们从不均匀分布的输入开始，但产生均匀分布的输出。因此，第二个输出点可能是前四个输入点的平均值。下一个输出点可能是三个输入点的平均值（依此类推）。在许多情况下，输出中某个段的端点都可能与输入中的任何点都不精确对应。

也可以我们在输入的两个点之间进行插值，以找出输出段起点的时间偏差。终点同样如此。然后，我们可以根据两点之间的时间差来计算在它们之间旅行所需的总时间。

如果想花哨的话，可以使用更高阶的插值代替线性插值。每个插值确实需要更多的输入点，但是看起来您可能有很多事情要做，例如二次或三次插值（在大多数情况下）。这可能会在过渡时产生最大的差异，即“笔”快速加速或减速的位置。在这种情况下，线性插值可能会产生误导性的结果（尽管鉴于您正在使用的点数，它可能不会引起足够的差异以至于引起注意）。

作为说明，让我们考虑一条直线。我们将从5个输入点开始，并产生7个输出点。

因此，输入点为[0、2、7、10、15]，关联的时间增量为[0、1、4、8、3]。

因此，总行进距离为16，我们希望输出点均匀分布。因此，输出点之间的距离将是16/7 =（大约）2.29。

因此，显然第一个输出点和时间都为0。第二个输出点为2.29。要计算输出时间，我们将整个时间带到第一个输入点（0-> 2），再加上0.29 /（7-2）*（4-1）。该插值部分为1.37，因此我们的第一个输出时间增量为2.37。

下一个输出点的距离应为4.58。由于第二输入段从2变为7，因此我们的整个第二输出段将位于第二输入段内。因此，我们取2.29 /（7-2），告诉使用该输出段占输入段的.458。然后，将其乘以第二个输入段的时间，得出第二个输出段的时间增量：.458 *（4-1）= 1.374。

[...并且它以相同的方式持续到我们到达终点为止。]