逆双线性插值？ [英] 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.

推荐答案

我认为这是最容易想到的问题作为一个交叉点的问题：什么是参数的位置（S，T），其中P点相交的任意2D双线性表面由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) )

我们现在可以设置这两个方程彼此相等，以消除吨。移动一切向左侧和简化，我们得到以下形式的公式：

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横产品（例如，P0 x p1的= X0 * Y1 - Y0 * 1次）。我格式化这个等式作为二次伯恩斯坦多项式的，因为这使事情变得更优雅，更数值稳定。该解决方案为s此方程的根。我们可以使用二次公式关于Bernstein找到根源：

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，可以替换的背到两个方程上面，我们解决了在t之一在条款。

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，否则的没有的的价值观包含第

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屋！