逆双线性插值? [英] Inverse Bilinear Interpolation?

问题描述

我有四个二维点，p0 = (x0,y0), p1 = (x1,y1) 等等，它们形成了一个四边形.就我而言，四边形不是矩形，但至少应该是凸面.

I have four 2d points, p0 = (x0,y0), p1 = (x1,y1), etc. that form a quadrilateral. In my case, the quad is not rectangular, but it should at least be convex.

  p2 --- p3
  |      |
t |  p   |
  |      |
  p0 --- p1
     s

我正在使用双线性插值.S 和 T 在 [0..1] 内，插值点由下式给出:

I'm using bilinear interpolation. S and T are within [0..1] and the interpolated point is given by:

bilerp(s,t) = t*(s*p3+(1-s)*p2) + (1-t)*(s*p1+(1-s)*p0)

问题来了..我有一个二维点 p，我知道它在四边形内.我想找到在使用双线性插值时会给我那个点的 s,t .

Here's the problem.. I have a 2d point p that I know is inside the quad. I want to find the s,t that will give me that point when using bilinear interpolation.

是否有一个简单的公式来反转双线性插值?

Is there a simple formula to reverse the bilinear interpolation?

感谢您的解决方案.我将 Naaff 解决方案的实现作为 wiki 发布.

Thanks for the solutions. I posted my implementation of Naaff's solution as a wiki.

推荐答案

我觉得把你的问题看成一个相交问题是最容易的:点p与任意二维双线性相交的参数位置(s,t)是多少由 p0、p1、p2 和 p3 定义的表面.

I think it's easiest to think of your problem as an intersection problem: what is the parameter location (s,t) where the point p intersects the arbitrary 2D bilinear surface defined by p0, p1, p2 and p3.

我将采取的解决此问题的方法与 tspauld 的建议类似.

The approach I'll take to solving this problem is similar to tspauld's suggestion.

从两个关于 x 和 y 的方程开始:

Start with two equations in terms of x and y:

x = (1-s)*( (1-t)*x0 + t*x2 ) + s*( (1-t)*x1 + t*x3 )
y = (1-s)*( (1-t)*y0 + t*y2 ) + s*( (1-t)*y1 + t*y3 )

求解 t:

t = ( (1-s)*(x0-x) + s*(x1-x) ) / ( (1-s)*(x0-x2) + s*(x1-x3) )
t = ( (1-s)*(y0-y) + s*(y1-y) ) / ( (1-s)*(y0-y2) + s*(y1-y3) )

我们现在可以将这两个方程设置为彼此相等以消除 t.将所有内容移至左侧并进行简化，我们得到以下形式的方程:

We can now set these two equations equal to each other to eliminate t. Moving everything to the left-hand side and simplifying we get an equation of the form:

A*(1-s)^2 + B*2s(1-s) + C*s^2 = 0

地点:

A = (p0-p) X (p0-p2)
B = ( (p0-p) X (p1-p3) + (p1-p) X (p0-p2) ) / 2
C = (p1-p) X (p1-p3)

请注意，我使用运算符 X 表示 2D cross乘积(例如，p0 X p1 = x0*y1 - y0*x1).我将这个方程格式化为二次 Bernstein polynomial 因为这使得事情更优雅，在数值上更稳定.s 的解是这个方程的根.我们可以使用伯恩斯坦多项式的二次公式找到根:

Note that I've used the operator X to denote the 2D cross product (e.g., p0 X p1 = x0*y1 - y0*x1). I've formatted this equation as a quadratic Bernstein polynomial as this makes things more elegant and is more numerically stable. The solutions to s are the roots of this equation. We can find the roots using the quadratic formula for Bernstein polynomials:

s = ( (A-B) +- sqrt(B^2 - A*C) ) / ( A - 2*B + C )

由于+-，二次公式给出了两个答案.如果您只对 p 位于双线性曲面内的解感兴趣，那么您可以丢弃 s 不在 0 和 1 之间的任何答案.要找到 t，只需将 s 代回上面我们求解 t 的两个方程之一就 s 而言.

The quadratic formula gives two answers due to the +-. If you're only interested in solutions where p lies within the bilinear surface then you can discard any answer where s is not between 0 and 1. To find t, simply substitute s back into one of the two equations above where we solved for t in terms of s.

我应该指出一个重要的特殊情况.如果分母 A - 2*B + C = 0 那么二次多项式实际上是线性的.在这种情况下，您必须使用更简单的等式来找到 s:

I should point out one important special case. If the denominator A - 2*B + C = 0 then your quadratic polynomial is actually linear. In this case, you must use a much simpler equation to find s:

s = A / (A-C)

这会给你一个解决方案，除非 AC = 0.如果 A = C 那么你有两种情况:A=C=0 意味着 所有 s 的值都包含 p，否则 没有 s 的值包含 p.

This will give you exactly one solution, unless A-C = 0. If A = C then you have two cases: A=C=0 means all values for s contain p, otherwise no values for s contain p.

这篇关于逆双线性插值?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！