Point Inside A triangle

[ceaser]

Iwonder if somebody can help me please

I have a triangle defined by three vertices(X, Y, Z). Inside this triangle I have another point (X, Y). Now, I need a formula to calculate the height (Z) of the point inside the triangle using the coordinates (X,Y,Z) of the vertices.

I have been using least squares adjustment, but have found that the bigger the triangle is, the less accurate the Z coordinate becomes.

Anybody?

Thanks
Michael

[Ariel_Z]

I'm afraid I could not understand your request. The third point is marked (X,Y) with regard to the vertices (X,Y) or is independent? And what do you mean exactly by "Height" of that point?

[ceaser]

Hi Ariel

I have a lot of points (topographical survey points) and these points are defined by X, Y and Z coordinates. These points then get triangulated with the help of Agraham's Delauney dll

Now, when I tap with my stylus inside any triangle, the program will return the X and Y position where I tapped on the screen. The program then uses these X and Y values to find out in which triangle I have tapped.

Now comes the difficult part. Using the X, Y and Z coordinates of the triangle in which I have tapped, the program needs to calculate a "Z" (height) value of the point where I have tapped, using the values of the 3 corners of the triangle.

Like I have said previously, it works with least squares adjustment, but only to a certain point.

Hope you can help

Thanks
Michael

[klaus]

Hi Michael,
Here you are.
Attached a test program.
The program doesn't check if the point is inside the triangle.

Best regards.

[ceaser]

Hi Klaus

Thank you very much I don't know what I would have done without the help in this forum.

Something that has struck me with your routine is that one could "extrapolate" heights outside your Tin Model. Where this would be helpful is say controlling the earthworks operation on a golfcourse. What I do is to take the coordinates from the Landscaper (Golfcourse Designer!) as he\she has designed it, convert it to a Tin Model and download it to my controller (Workabout_pro)

Then in the field I hold the Prism Pole (Robotic Total Station) or the Rover Pole (GPS) anywhere on the site and the program will tell me how much up or down the groundlevel must go, to tie in with that of the designer. The design height gets calculated from the respective vertexes from the triangle in which the Pole is held.

What I will do is to change the program that it will also give me a height outside the Tin Model, but warn me (or the user) once the Prism Pole is outside the Tin Model limits.

On another note. I am busy changing the storage format of the CAD program and will post it as soon as it is finished.

Thanks
Michael

[klaus]

Hi Michael,

The fact that the user can extrapolate outsides the triangle has 2 reasons.
- mathematically the 3 vertices of the triangle define a plane, this one is defied inside and outside the triangle.
- in the demo program there is only ONE triangle, the coordinates of the 3 vertices are known when strating the program that means that the plane is already defined. So you can click elsewhere you get an answer.
In your program you must first search in what triangle the point is located and then define the plane.

I didn't include a test if the point is inside the triangle because as you wrote in a previous post:
- that you click on a point
- the program searches the triangle where the point is in
- the program should calculate the altitude of that point.
In this case the point is by definition in a known triangle.
If the point is out of the tin model, the triangle search routine will return no triangle so you already have the warning information.

You could also change the Calc_Z routine as follows.
Instead of transmitting the vertex coordinates

Sub Calc_Z(x1,y1,z1,x2,y2,z2,x3,y3,z3,x,y)

you could transmit the triangle index and extract the vertex coordinates in the routine.

Sub Calc_Z(ti,x,y)
 Dim x1,x2,x3,y1,y2,y3,z1,z2,z3

 
 x1=Point(Triangle(ti).V1).X
 y1=Point(Triangle(ti).V1).Y
 z1=Point(Triangle(ti).V1).Z
 
 x2=Point(Triangle(ti).V2).X
 y2=Point(Triangle(ti).V2).Y
 z2=Point(Triangle(ti).V2).Z
' etc

Best regards.

[DeeCee]

As mentioned, the three points define a plane, so you can also find the equation of the plane in 3d and use that to find the Z of any X, Y point. A good way to find a plane equation is discussed at the following site:

Equation of a plane


I am working on a similar program and would be interested in knowing if you have an optimized routine to find the triangle holding the point. Do you just brute force search and test each triangle, or do you have a better way?

[ceaser]

Hi DeeCee

I use what you call the "brute force" method Firstly I calculate the area of the triangle using the 3 vertexes and then I calculate the area from the prism point (X & Y) to the respective triangle. If the 2 areas are the same, then the point is inside the triangle, but if the area from the prism point is larger than the triangle, then the point is outside the triangle, then the program tests the next triangle.

You are right, I test each triangle until the program finds the triangle where the point is inside the respective triangle.

I am sure there is a faster way. Maybe we should ask Klaus

Thanks
Michael

[wolfgang]

Hi,
have a look at this: Point in triangle test

[DeeCee]

Thanks Michael,

That is what I do also, just test each triangle. Of course, if you have 10,000 triangles and your point is in the last one tested, that takes a while. I would think a way to do it faster would be to sort the triangle array by X or Y, then do some type of binary search, but I'm not really sure how to do that.