c++ - C ++查找点集位于其他两个点之间的位置

Question

我有三组二维点。我需要做的是找出一个相对于另外两个的位置。每组都有相同的点，顺序相同。一个是“中性”，一个是“最大”，第三个是未知的。我需要的是返回一个介于 0 和 1 之间的值，它说明未知集在其他两个之间的数量。

例如，在图像中：

我会以某种方式获得 A 组和 B 组之间的“距离”或“重量”，然后找出 C 组在它们之间的位置。在本例中，我预计值约为 75%，即 0.75。

我已经研究过使用点集配准算法返回一个比例量以匹配集 C 到集 B，但我不相信这是最好的方法。什么方法适合这个问题？我应该搜索什么算法？

标签： c++mathpointpoint-clouds

Answer 1

您可以尝试通过在两组之间进行简单的线性插值来解决此问题。如果集合之间的转换确实几乎是线性的，则此方法有效。如果你知道它是别的东西，你可以调整插值函数。

让我们专注于一点p。我们知道它在所有集合p_A、p_B和中的坐标p_C。然后，我们指定它p_C或多或少是参数之间p_A的线性插值（其中表示集合 A，表示集合 B）：p_Btt=0t=1

      p_C = (1 - t) * p_A + t * p_B
          = p_A - t * p_A + t * p_B
          = p_A + t * (p_B - p_A)
p_C - p_A = t * (p_B - p_A)

现在的问题是找到一个t大致适用于你所有观点的。

我们可以通过将问题描述为线性最小二乘问题来解决这个问题。即，我们希望最小化所有点的总残差（上式左侧和右侧之间的差异）：

arg min_t Σ_i (pi_C.x - pi_A.x - t * (pi_B.x - pi_A.x))^2
               + (pi_C.y - pi_A.y - t * (pi_B.y - pi_A.y))^2

那么最优t的是：

numX = Σ_i (pi_A.x^2 - pi_A.x * pi_B.x - pi_A.x * pi_C.x + pi_B.x * pi_C.x)
numY = Σ_i (pi_A.y^2 - pi_A.y * pi_B.y - pi_A.y * pi_C.y + pi_B.y * pi_C.y)
denX = Σ_i (pi_A.x^2 - 2 * pi_A.x * pi_B.x + pi_B.x^2)
denY = Σ_i (pi_A.y^2 - 2 * pi_A.y * pi_B.y + pi_B.y^2)
t = (numX + numY) / (denX + denY)

如果您的点具有更高的维度，只需添加具有相同模式的新维度。