梯形上的双线性插值

Question

我正在尝试根据形成梯形的输入对数据进行插值。我找到了 Nico Schertler 的 this solution，它概述了如何对任意四个未对齐的输入点进行插值。但是，我无法将其推广到梯形。

插值是通过：

interpolated value = (1 - alpha) * ((1 - beta) * p1 + beta * p2) + alpha * ((1 - beta) * p3 + beta * p4)

在哪里

alpha = -(b e - a f + d g - c h + sqrt(-4 (c e - a g) (d f - b h) +
        (b e - a f + d g - c h)^2))/(2 c e - 2 a g)    
beta  = (b e - a f - d g + c h + sqrt(-4 (c e - a g) (d f - b h) + 
        (b e - a f + d g - c h)^2))/(2 c f - 2 b g)

或

alpha = (-b e + a f - d g + c h + sqrt(-4 (c e - a g) (d f - b h) + 
        (b e - a f + d g - c h)^2))/(2 c e - 2 a g)
beta  = -((-b e + a f + d g - c h + sqrt(-4 (c e - a g) (d f - b h) + 
        (b e - a f + d g - c h)^2))/( 2 c f - 2 b g))

系数由下式给出：

a = -p1.x + p3.x
b = -p1.x + p2.x
c = p1.x - p2.x - p3.x + p4.x
d = interpolated_point.x - p1.x
e = -p1.y + p3.y
f = -p1.y + p2.y
g = p1.y - p2.y - p3.y + p4.y
h = interpolated_point.y - p1.y

其中p1-p4是多边形输入顶点的坐标。当 p1.x=p3.x 和 p2.x=p4.x 但 p1.y!=p2.y!=p3.y!=p4.y 时会出现此问题 - 梯形就是这种情况。在这种情况下，a=c=0 并且 alpha 系数在除以 0 后变为无穷大。

所以我的问题是：有没有办法修改（简化？）Nico的方法使其适用于梯形。

Answer 1

梯形只有一个唯一解，这意味着参数坐标的方程是线性。因此，任意四边形的通解是未定义的，因为从中导出的方程是二次方程。

这当然可以严格证明，但也可以很容易地用两个图来说明：

在两种配置中（如果交换参数，它们是等效的），表示不同 alpha 值的蓝线从不在梯形内部相交，这意味着不可能有多个解决方案。

梯形的特例解可以从插值坐标的原始表达式导出R:

R = (1 - β)*[(1 - α)*P1 + α*P3] + β*[(1 - α)*P2 + α*P4]

  = (1 - β)*[P1 + α*(P3 - P1)] + β*[P2 + α*(P4 - P2)]

  = P1 + β*(P2 - P1) + α*(P3 - P1) + αβ*(P4 - P3 - P2 + P1)

  = P1 + β*E12 + α*E13 + αβ*(E24 - E13)

where the "edge vector" Exy = Py - Px

将P1移动到LHS，并取边1-2和1-3两边的cross-product：

(R - P1)xE12 = β*E12xE12 + α*E13xE12 + αβ*(E34xE12 - E12xE12)
------------     -------     -------       -------   -------
      A            = 0          C             E        = 0
   
(R - P1)xE13 = β*E12xE13 + α*E13xE13 + αβ*(E24xE13 - E13xE13)
------------     -------     -------       -------   -------
      B             D          = 0            F        = 0

回顾平行向量cross-product为0，得到一对联立二次方程：

A = α*C + αβ*E
B = β*D + αβ*F

note that D = -C

第一个图中，E13和E24平行，表示F = 0:

β = B/D
α = A / (C + E*B/D) = A*C / (C*C - E*B)

...第二个也是如此。

梯形上的双线性插值

Bi-linear interpolation on a trapezoid

algorithm

interpolation