🔒 Locked

Solve triangle interpolation linear equations

Started by dcosborn Mar 8, 2006 at 9:46 PM 2 replies 9.3k views

Original Post

Mar 8, 2006 at 9:46 PM

This is probably going to seem like a no-brainer to some people. Basically, I'm trying to linear interpolate a 2D triangle where each point has a certain value (z). I found this set of linear equations that I need to solve: Ax₀ + By₀ + C = z₀ Ax₁ + By₁ + C = z₁ Ax₂ + By₂ + C = z₂ Now apparantly I can determine A, B, and C if I know all instances of x, y, and z. However, my math skills have steadily degraded since high school. I'm trying substitution, but I'm not even sure its going to get me anywhere. C = z₀ - Ax₀ - By₀ Ax₁ + By₁ + (z₀ - Ax₀ - By₀) = z₁ Ax₁ - Ax₀ + By₁ - By₀ = z₁ - z₀ By₁ - By₀ = Ax₀ - Ax₁ + z₁ - z₀ Now I was hoping to extract B somehow so I could plug it into that last equation, but I'm not sure how to do this. Should I even be approaching it from this angle?

Zakwayda

Mar 8, 2006 at 10:37 PM

I'm not completely clear on the problem you're trying to solve, but as for the math, solving even a 3x3 system by hand can get pretty messy.

If you have a matrix class with an invert() function available, you could solve the system that way. Also, here is a longhand solution:

[a11 a12 a13][x1]   [b1][a21 a22 a23][x2] = [b2][a31 a32 a33][x3]   [b3]       b1(a22a33-a23a32)-a12(b2a33-a23b3)+a13(b2a32-a22b3)x1 = --------------------------------------------------------     a11(a22a33-a23a32)-a12(a21a33-a23a31)+a13(a21a32-a22a31)       a11(b2a33-a23b3)-b1(a21a33-a23a31)+a13(a21b3-b2a31)x2 = --------------------------------------------------------     a11(a22a33-a23a32)-a12(a21a33-a23a31)+a13(a21a32-a22a31)       a11(a22b3-b2a32)-a12(a21b3-b2a31)+b1(a21a32-a22a31)x3 = --------------------------------------------------------     a11(a22a33-a23a32)-a12(a21a33-a23a31)+a13(a21a32-a22a31)

I think the above is correct, although I can't guarantee it. Also, there are no optimizations there (note for example that the denominator, the determinant, is the same in each case).

You might be able to just plug your values into the above equations and get the answers you're looking for. There are other ways to solve linear systems as well, but they might require additional coding.

biki_

Mar 9, 2006 at 1:28 AM

how about something like this

A*x0 + B*y0 + C = z0
A*x1 + B*y1 + C = z1
A*x2 + B*y2 + C = z2

i substract 2 and 3 row from 1

A*(x0-x1) + B*(y0-y1) = z0-z1
A*(x0-x2) + B*(y0-y2) = z0-z2

now

let P=x0-x1 Q=y0-y1
R=x0-x2 S=y0-y2
T=z0-z1 U=z0-z2

A*P+B*Q=T
A*R+B*S=U

det=P*S-R*Q
idet=1/det
A=(T*S-U*Q)*idet
B=(P*U-R*T)*idet
C=z0-A*x0-B*x0

14 muls 1 div.. shoud be quite fast

dcosborn

Mar 9, 2006 at 1:29 AM

jyk: Thanks for the help. I was searching for more information on solving via matrix inversions and I stumbled on this linear solver. It can take a linear system with parameters and output the equations to find each unknown. I just plugged in the equations and my interpolations are now working correctly.

biki_: Your method looks like it would probably be more efficient than what I have now. I'll have to try it out.

Topic Locked

This topic has been locked by a moderator. New replies are not allowed.