PDA

View Full Version : Solved: Triangulation help needed.



mdmackillop
12-09-2009, 10:56 AM
I need to calculated the height at intermediate grid co-ordinates where I have 3 sets of enclosing co-ordinates and heights.

Formula or UDF solutions welcome!

mdmackillop
12-09-2009, 04:56 PM
I've also posted in a Maths forum (http://www.mathhelpforum.com/math-help/geometry/119616-triangulation-help-needed.html)

p45cal
12-09-2009, 05:56 PM
I know nothing about 3d geometry, but I used this (http://local.wasp.uwa.edu.au/%7Epbourke/geometry/planeeq/)site to create this function (not a very elegant one, I know):
Function HeightAt(x4, y4, x1, x2, x3, y1, y2, y3, z1, z2, z3)
A = y1 * (z2 - z3) + y2 * (z3 - z1) + y3 * (z1 - z2)
B = z1 * (x2 - x3) + z2 * (x3 - x1) + z3 * (x1 - x2)
C = x1 * (y2 - y3) + x2 * (y3 - y1) + x3 * (y1 - y2)
D = -(x1 * (y2 * z3 - y3 * z2) + x2 * (y3 * z1 - y1 * z3) + x3 * (y1 * z2 - y2 * z1))
HeightAt = -((A * x4 + B * y4 + D) / C)
End Function This gave results that are very credible. I was pleased to see that the estimates I made of those heights before I saw the results were very close indeed to the heights calculated.

See attached.

mikerickson
12-09-2009, 07:40 PM
I'm not sure what you are looking for.
Is this an accurate restatement of the problem?

Given three points that define a plane, and given an X coordinate and a Y coordinate.
What is the Z coordinate such that (X,Y,Z) in that plane?

mdmackillop
12-10-2009, 01:48 AM
Thanks P45, I'll give it a go.

Mike,
A much neater explanation!

mikerickson
12-11-2009, 10:09 AM
Here's my approach,
we are given 3 points (P1, P2, P3)
(These are vectors, each Pi has 3 coordinates)

We have a (partialy) unknown V =(given X, given Y, unknown Z)

Calculate
Q1 = P1-V
Q2 = P2-V
Q3 = P3-V

Then take the inner products
Q1 • Q2
Q1 • Q3
Q2 • Q3

And divide by the product of the lengths of Qi, Qj to give us the cosines of the angles between Qi and Qj

(Q1 • Q2) / Len(Q1) / Len(Q2)
(Q1 • Q3) / Len(Q1) / Len(Q3)
(Q2 • Q3) / Len(Q2) / Len(Q3)

Sum the arcsines of these values.

If V is interior to the triangle P1 P2 P3, i.e. lies in the plane defined by the 3 points, then the sum of those arcsines = 360°

So use Solver to find the Z value that will make that sum = 360
(Edit: Corrected this line and attached spreadsheet)

This method has significant round-off error. On one test, Excel returned .998 when 1 was the answer.

mikerickson
12-12-2009, 12:06 PM
I've found a more robust approach. It
a) does not require that X be interior to the triangle.
b) avoids dividing by lenghts (a.k.a round off error)

It utilizes the cross-product and uses Solver to find the Z, such that Q3 • (Q1 X Q2) = 0

If the Button doesn't work, Solver can be called manualy or the Solver Add-in should be active in the VBE Tools>References.

Paul_Hossler
12-12-2009, 04:58 PM
Doing this as a UDF is another way.

I set it to pass ranges, but you can easily change that or make it a sub,



'ref: http://www.jtaylor1142001.net/calcjat/Solutions/VPlanes/VP3Pts.htm
'P,Q,R as 3 Col by 1 Row, X as 2 Col, 1 Row
Function Triang(P As Range, R As Range, Q As Range, X As Range) As Variant
Dim i As Long
Dim Z As Double

Dim PQ(1 To 1, 1 To 3) As Double, PR(1 To 1, 1 To 3) As Double, PQxPR(1 To 1, 1 To 3) As Double
Dim Coeff(1 To 1, 1 To 3) As Double, D As Double

On Error GoTo NiceExit
'get vectors PQ and PR
For i = 1 To 3
PQ(1, i) = Q(1, i) - P(1, i)
PR(1, i) = R(1, i) - P(1, i)
Next i

'Normal vector to PQ and PR via cross product
PQxPR(1, 1) = PR(1, 2) * PQ(1, 3) - PR(1, 3) * PQ(1, 2)
PQxPR(1, 2) = PR(1, 3) * PQ(1, 1) - PR(1, 1) * PQ(1, 3)
PQxPR(1, 3) = PR(1, 1) * PQ(1, 2) - PR(1, 2) * PQ(1, 1)

'use first point
D = 0#
For i = 1 To 3
D = D + PQxPR(1, i) * P(1, i).Value
Next i

'solve aX + bY + cZ = D for Z, given X and Y (passed from X range), a,b, and c from cross product, and D solved above
With X
Z = D - (PQxPR(1, 1) * .Cells(1, 1)) - (PQxPR(1, 2) * .Cells(1, 2))
Z = Z / PQxPR(1, 3)
End With

Triang = Z

Exit Function
NiceExit:
Triang = CVErr(xlErrNA)
End Function



Paul

mdmackillop
12-13-2009, 10:18 AM
Thanks all,
I've gone with P45Cal's solution, as I need to finish this project. I'll check out the other's in detail. I'm attaching part of the final solution incorpporating the Function do demonstrate how it was used.