另一种(Yet Another)三角形线性插值方法

灰太狼 2022-04-24 05:32 223阅读 0赞

> 本文简述了一种三角形线性插值的方法(本文仅讨论二维情况)

#### 相关问题 ####

给定一个三角形的顶点坐标(**P0, P1 和 P2**)以及对应的数值(**V0, V1 和 V2**),插值求解三角形内一点(坐标给定为**P**)的数值(**V**).

问题说的有些抽象,给张图会清晰明了一些,图中的 **V** 即是我们想要插值求解的数值.

![在这里插入图片描述][20190417232732771.png]

#### 插值方法 ####

如何求解呢?一般我们是采用比例面积的方法,见下图(图中 **a0, a1 和 a2** 分别代表三个分割三角形的面积):

![在这里插入图片描述][2019041723274673.png]

图中 **a0** 占三角形整体面积的比例代表 **V2**(**P2**对应的数值)占 **V** 的比例, **a1** 占三角形整体面积的比例代表 **V1**(**P1**对应的数值)占 **V** 的比例, 而 **a2** 占三角形整体面积的比例则代表 **V0**(**P0**对应的数值)占 **V** 的比例,假设三角形的整体面积为 **a**, 则我们有:

V = a 0 a ∗ V 2 + a 1 a ∗ V 1 + a 2 a ∗ V 0 = ( a 0 ∗ V 2 + a 1 ∗ V 1 + a 2 ∗ V 0 ) / a \\begin\{aligned\} V & = \\dfrac\{a\_0\}\{a\} \* V\_2 + \\dfrac\{a\_1\}\{a\} \* V\_1 + \\dfrac\{a\_2\}\{a\} \* V\_0 \\\\ & = (a\_0 \* V\_2 + a\_1 \* V\_1 + a\_2 \* V\_0) / a \\end\{aligned\} V=aa0∗V2\+aa1∗V1\+aa2∗V0=(a0∗V2\+a1∗V1\+a2∗V0)/a

接下来的问题就是如何根据三角形的顶点求解三角形的面积了,这里我们直接给出结论,有兴趣的朋友可以从[这里][Link 1]开始了解,方法就是使用**叉积**:

假设三角形的三个顶点分别为 **P0, P1 和 P2**, 则三角形面积 **a** 的计算公式为:

a = 1 2 ∗ ∣ ( P 1 − P 0 ) × ( P 2 − P 0 ) ∣ a = \\dfrac\{1\}\{2\} \* | (P\_1 - P\_0) \\times (P\_2 - P\_0) | a=21∗∣(P1−P0)×(P2−P0)∣

如果 **P0** 的坐标为 **<x0, y0>**, **P1** 的坐标为 **<x1, y1>**, **P2** 的坐标为 **<x2, y2>**,则上面的公式可表达为:

a = 1 2 ∗ ∣ ( P 1 − P 0 ) × ( P 2 − P 0 ) ∣ = 1 2 ∗ ∣ ( < x 1 , y 1 > − < x 0 , y 0 > ) × ( < x 2 , y 2 > − < x 0 , y 0 > ) ∣ = 1 2 ∗ ∣ ( < x 1 − x 0 , y 1 − y 0 > ) × ( < x 2 − x 0 , y 2 − y 0 > ) ∣ = 1 2 ∗ ∣ ( x 1 − x 0 ) ∗ ( y 2 − y 0 ) − ( x 2 − x 0 ) ∗ ( y 1 − y 0 ) ∣ \\begin\{aligned\} a & = \\dfrac\{1\}\{2\} \* | (P\_1 - P\_0) \\times (P\_2 - P\_0) | \\\\ & = \\dfrac\{1\}\{2\} \* |(<x\_1, y\_1> - <x\_0, y\_0>) \\times (<x\_2, y\_2> - <x\_0, y\_0>) | \\\\ & = \\dfrac\{1\}\{2\} \* |(<x\_1 - x\_0, y\_1 - y\_0>) \\times (<x\_2 - x\_0, y\_2 - y\_0>) | \\\\ & = \\dfrac\{1\}\{2\} \* |(x\_1 - x\_0) \* (y\_2 - y\_0) - (x\_2 - x\_0) \* (y\_1 - y\_0) | \\end\{aligned\} a=21∗∣(P1−P0)×(P2−P0)∣=21∗∣(<x1,y1>−<x0,y0>)×(<x2,y2>−<x0,y0>)∣=21∗∣(<x1−x0,y1−y0>)×(<x2−x0,y2−y0>)∣=21∗∣(x1−x0)∗(y2−y0)−(x2−x0)∗(y1−y0)∣

这里需要说明的一点是,二维向量实际上是没有叉积定义的,但是我们可以将二维坐标点看做是三维坐标点(第三维取 0 即可)来进行求解,更多细节还是请参看[这里][Link 1].

讲到这里,我们便可以进行实现了,参考代码如下:

public struct Value2<T>
    {
        public float x;
        public float y;
        public T v;
    
        public Vector2 Vector
        {
            get
            {
                return new Vector2(x, y);
            }
        }
    
        public Value2(float x, float y, T v)
        {
            this.x = x;
            this.y = y;
            this.v = v;
        }
    }

public static float Cross(Vector2 v0, Vector2 v1)
    {
        return v0.x * v1.y - v1.x * v0.y;
    }
    
    public static float TriangleArea(Vector2 v0, Vector2 v1)
    {
        return 0.5f * Math.Abs(Cross(v0, v1));
    }
    
    public static float TriangleLerp(Value2f val0, Value2f val1, Value2f val2, Vector2 p)
    {
        var v01 = val1.Vector - val0.Vector;
        var v02 = val2.Vector - val0.Vector;
        var v0p = p - val0.Vector;
    
        var a = TriangleArea(v01, v02);
        Debug.Assert(a > 0, "[MathUtil]Error to do triangle Lerp, seems vertexes collinear ...");
        
        var a0 = TriangleArea(v01, v0p);
        var a1 = TriangleArea(v0p, v02);
        var a2 = a - a0 - a1;
    
        return (val2.v * a0 + val1.v * a1 + val0.v * a2) / a;
    }

#### 另一种(Yet Another)插值方法 ####

实际上我还尝试了一种类似于[双线性插值][Link 2]的求解方法,发现也是可行的,参考下图:

![在这里插入图片描述][20190417232814775.png]

其中的虚线线段平行于向量 **P2 - P1**(虚线取用其他线段也是可行的,只是计算上不方便),只要我们求解出 **P1’** 的对应数值 **V1’**, **P2’** 的对应数值 **v2’**,以及子线段(**P1’ 至 P**)占总线段(**P1’ 至 P2’**)的比例 **t**,则 **P** 点对应的数值 **V** 便可以用简单的线性插值来求解了:

V = ( 1 − t ) ∗ V 1 ′ + t ∗ V 2 ′ V = (1 - t) \* V\_1&\#x27; + t \* V\_2&\#x27; V=(1−t)∗V1′\+t∗V2′

我们可以采用解析法来求解上面所需的 **V1’**, **V2’** 和 **t**, 参考下图:

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3Rrb2tvZjE_size_16_color_FFFFFF_t_70]

我们设红色向量部分(**P1’ - P**)等于 **t1 \* (P2 - P1)**,黄色向量部分(**P1’ - P0**)等于 **t2 \* (P1 - P0)**,由于相似三角形对应边成比例的关系,蓝色向量部分(**P2’ - P0**)的比例系数也为 **t2**,类似的,向量 **P2’ - P1’** 相对与向量 **P2 - P1** 的比例系数同样也为 **t2**.

我们知道:

P 1 ′ − P 0 = ( P − P 0 ) + ( P 1 ′ − P ) &ThickSpace; ⟹ &ThickSpace; t 2 ∗ ( P 1 − P 0 ) = ( P − P 0 ) + t 1 ∗ ( P 2 − P 1 ) \\begin\{aligned\} & P\_1&\#x27; - P\_0 = (P - P\_0) + (P\_1&\#x27; - P) \\implies \\\\ & t\_2 \* (P\_1 - P\_0) = (P - P\_0) + t\_1 \* (P\_2 - P\_1) \\end\{aligned\} P1′−P0=(P−P0)\+(P1′−P)⟹t2∗(P1−P0)=(P−P0)\+t1∗(P2−P1)

并且 **P0** 的坐标为 **<x0, y0>**, **P1** 的坐标为 **<x1, y1>**, **P2** 的坐标为 **<x2, y2>**, **P** 的坐标为 **<x, y>**

则有:

\{ t 2 ∗ ( x 1 − x 0 ) = x − x 0 + t 1 ∗ ( x 2 − x 1 ) t 2 ∗ ( y 1 − y 0 ) = y − y 0 + t 1 ∗ ( y 2 − y 1 ) \\left\\\{ \\begin\{aligned\} t\_2 \* (x\_1 - x\_0) & = x - x\_0 + t\_1 \* (x\_2 - x\_1) \\\\ t\_2 \* (y\_1 - y\_0) & = y - y\_0 + t\_1 \* (y\_2 - y\_1) \\end\{aligned\} \\right. \{ t2∗(x1−x0)t2∗(y1−y0)=x−x0\+t1∗(x2−x1)=y−y0\+t1∗(y2−y1)

求解可得:

\{ t 1 = ( x 1 − x 0 ) ∗ ( y − y 0 ) − ( x − x 0 ) ∗ ( y 1 − y 0 ) ( x 2 − x 1 ) ∗ ( y 1 − y 0 ) − ( x 1 − x 0 ) ∗ ( y 2 − y 1 ) = ( P 1 − P 0 ) × ( P − P 0 ) ( P 2 − P 1 ) × ( P 1 − P 0 ) t 2 = ( x − x 0 ) + t 1 ∗ ( x 2 − x 1 ) x 1 − x 0 o r ( y − y 0 ) + t 1 ∗ ( y 2 − y 1 ) y 1 − y 0 \\left\\\{ \\begin\{aligned\} t\_1 & = \\dfrac\{(x\_1 - x\_0) \* (y - y\_0) - (x - x\_0) \* (y\_1 - y\_0)\}\{(x\_2 - x\_1) \* (y\_1 - y\_0) - (x\_1 - x\_0) \* (y\_2 - y\_1)\} = \\dfrac\{(P\_1 - P\_0) \\times (P - P\_0)\}\{(P\_2 - P\_1) \\times (P\_1 - P\_0)\} \\\\ t\_2 & = \\dfrac\{(x - x\_0) + t\_1 \* (x\_2 - x\_1)\}\{x\_1 - x\_0\} or \\dfrac\{(y - y\_0) + t\_1 \* (y\_2 - y\_1)\}\{y\_1 - y\_0\} \\end\{aligned\} \\right. ⎩⎪⎪⎨⎪⎪⎧t1t2=(x2−x1)∗(y1−y0)−(x1−x0)∗(y2−y1)(x1−x0)∗(y−y0)−(x−x0)∗(y1−y0)=(P2−P1)×(P1−P0)(P1−P0)×(P−P0)=x1−x0(x−x0)\+t1∗(x2−x1)ory1−y0(y−y0)\+t1∗(y2−y1)

可以看到 **t1** 的计算公式是一个叉积比例的形式,其实这个形式除了使用先前的解析方法,也可以运用几何方法来进行求解,只是对思维的要求比较高,有兴趣的朋友可以自己尝试一下(提示:叉积->面积).

有了 **t1** 和 **t2**,我们就可以计算之前的 **V1’**, **V2’** 和 **t** 了:

V 1 ′ = ( 1 − t 2 ) ∗ V 0 + t 2 ∗ V 1 V 2 ′ = ( 1 − t 2 ) ∗ V 0 + t 2 ∗ V 2 t = ∣ t 1 ∗ ( P 2 − P 1 ) t 2 ∗ ( P 2 − P 1 ) ∣ = ∣ t 1 t 2 ∣ \\begin\{aligned\} V\_1&\#x27; & = (1 - t\_2) \* V\_0 + t\_2 \* V\_1 \\\\ V\_2&\#x27; & = (1 - t\_2) \* V\_0 + t\_2 \* V\_2 \\\\ t &= | \\dfrac\{t\_1 \* (P\_2 - P\_1)\}\{t\_2 \* (P\_2 - P\_1)\} | = |\\dfrac\{t\_1\}\{t\_2\}| \\end\{aligned\} V1′V2′t=(1−t2)∗V0\+t2∗V1=(1−t2)∗V0\+t2∗V2=∣t2∗(P2−P1)t1∗(P2−P1)∣=∣t2t1∣