Point Inside A triangle

C

ceaser

Active Member
Licensed User
Iwonder if somebody can help me please:sign0085:

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.:sign0085:

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

Anybody?

Thanks
Michael
 
C

ceaser

Active Member
Licensed User
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:sign0188:

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:sign0085:

Thanks
Michael
 
klaus

klaus

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

Best regards.
 

Attachments

  • Triangle_Z.jpg
    Triangle_Z.jpg
    10.2 KB · Views: 259
  • Triangle.sbp
    2.8 KB · Views: 329
C

ceaser

Active Member
Licensed User
Hi Klaus

Thank you very much:sign0188: 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

klaus

Expert
Licensed User
Longtime User
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
B4X: 
[FONT=Courier New][SIZE=2][COLOR=#0000ff][FONT=Courier New][SIZE=2][COLOR=#0000ff][FONT=Courier New][SIZE=2][COLOR=#0000ff]Sub [/COLOR][/SIZE][/FONT][/COLOR][/SIZE][/FONT][/COLOR][/SIZE][/FONT][FONT=Courier New][SIZE=2][FONT=Courier New][SIZE=2]Calc_Z(x1,y1,z1,x2,y2,z2,x3,y3,z3,x,y)[/SIZE][/FONT][/SIZE][/FONT]
you could transmit the triangle index and extract the vertex coordinates in the routine.
B4X: 
[FONT=Courier New][SIZE=2][COLOR=#0000ff][FONT=Courier New][SIZE=2][COLOR=#0000ff][FONT=Courier New][SIZE=2][COLOR=#0000ff][FONT=Courier New][SIZE=2][COLOR=#0000ff][FONT=Courier New][SIZE=2][COLOR=#0000ff][FONT=Courier New][SIZE=2][COLOR=#0000ff][FONT=Courier New][SIZE=2][COLOR=#0000ff][FONT=Courier New][SIZE=2][COLOR=#0000ff][FONT=Courier New][SIZE=2][COLOR=#0000ff]Sub [/COLOR][/SIZE][/FONT][/COLOR][/SIZE][/FONT][/COLOR][/SIZE][/FONT][FONT=Courier New][SIZE=2][FONT=Courier New][SIZE=2][COLOR=#000000]Calc_Z(ti,x,y)[/COLOR][/SIZE][/FONT]
[/SIZE][/FONT][FONT=Courier New][SIZE=2][COLOR=#0000ff][FONT=Courier New][SIZE=2][COLOR=#0000ff][FONT=Courier New][SIZE=2][COLOR=#0000ff] Dim[/COLOR][/SIZE][/FONT][/COLOR][/SIZE][/FONT][/COLOR][/SIZE][/FONT][FONT=Courier New][SIZE=2][FONT=Courier New][SIZE=2] x1,x2,x3,y1,y2,y3,z1,z2,z3[/SIZE][/FONT][/SIZE][/FONT]
[FONT=Courier New][SIZE=2]
 
[SIZE=2][FONT=Courier New] x1=Point(Triangle(ti).V1).X[/FONT][/SIZE]
[SIZE=2][FONT=Courier New] y1=Point(Triangle(ti).V1).Y[/FONT][/SIZE]
[SIZE=2][FONT=Courier New] z1=Point(Triangle(ti).V1).Z[/FONT][/SIZE]
 
[SIZE=2][FONT=Courier New] x2=Point(Triangle(ti).V2).X[/FONT][/SIZE]
[SIZE=2][FONT=Courier New] y2=Point(Triangle(ti).V2).Y[/FONT][/SIZE]
[SIZE=2][FONT=Courier New] z2=Point(Triangle(ti).V2).Z[/FONT][/SIZE]
[/SIZE][/FONT][FONT=Courier New][SIZE=2][COLOR=#008000][FONT=Courier New][SIZE=2][COLOR=#008000][FONT=Courier New][SIZE=2][COLOR=#008000]' etc[/COLOR][/SIZE][/FONT][/COLOR][/SIZE][/FONT][/COLOR][/SIZE][/FONT][/COLOR][/SIZE][/FONT][/COLOR][/SIZE][/FONT][/COLOR][/SIZE][/FONT][/COLOR][/SIZE][/FONT][/COLOR][/SIZE][/FONT][/COLOR][/SIZE][/FONT]


Best regards.
 
D

DeeCee

Member
Licensed User
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?
 
C

ceaser

Active Member
Licensed User
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:sign0188:

Thanks
Michael
 
W

wolfgang

Member
Licensed User
Longtime User
D

DeeCee

Member
Licensed User
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.
 
C

ceaser

Active Member
Licensed User
Thanks Wolfgang...it helped. It seems to be faster than using the area method.

My only problem is that, like DeeCee says, if you have 10 000 triangles. It can take some time when the triangle that you are working with is the last one!

Thanks
Michael
 
klaus

klaus

Expert
Licensed User
Longtime User
Hi DeeCee and Ceasar,

I was on travel the last weeks, so I didn't answer your post before.

I have made some tests finding the triangle where the point is in.
Attached 3 test programs:
The programs checks 10000 triangles, the point is in the last one.

3 methods are used:
1)Check triangle:
- checks if the point lies in the triangle
2)Check rectangle:
- calculates the coordinates of the surrounding rectangle
- checks if the point lies in the surrounding rectangle
- if yes, checks if the point lies in the triangle
3)Check X Y Max Min:
- the xmin, xmax, ymin and ymax of the surrounding rectangle for each triangle are precalculated somewhere else in the program and memorized
- checks if the point lies in the surrounding rectangle
- if yes, checks if the point lies in the triangle

Checking if a point lies in a rectangle is faster then checking for a triangle.

TestFindTriangle1:
- standard variables
- 10000 triangles with the 3 coordinates

TestFindTriangle2:
- variables declared as Double
- 10000 triangles with the 3 coordinates

TestFindTriangle3: variables declared as Double
- variables declared as Double
- 4 points with their coordinates
- 10000 triangles with the vertex point indexes

Test results optimized compiled on my htc Touch HD in seconds:
B4X: 
[SIZE=2][FONT=Courier New][SIZE=2][FONT=Courier New]  Test1 Test2 Test3[/FONT][/SIZE][/FONT][/SIZE]
[SIZE=2][FONT=Courier New][COLOR=#800080][SIZE=2][FONT=Courier New][COLOR=#800080][SIZE=2][FONT=Courier New][COLOR=#800080]1[/COLOR][/FONT][/SIZE][/COLOR][/FONT][/SIZE][/COLOR][/FONT][/SIZE][FONT=Courier New][SIZE=2][FONT=Courier New][SIZE=2]) [/SIZE][/FONT][/SIZE][/FONT][FONT=Courier New][SIZE=2][COLOR=#800080][FONT=Courier New][SIZE=2][COLOR=#800080][FONT=Courier New][SIZE=2][COLOR=#800080]43    [/COLOR][/SIZE][/FONT][/COLOR][/SIZE][/FONT][/COLOR][/SIZE][/FONT][FONT=Courier New][SIZE=2][COLOR=#800080][FONT=Courier New][SIZE=2][COLOR=#800080][FONT=Courier New][SIZE=2][COLOR=#800080]30    33[/COLOR][/SIZE][/FONT][/COLOR][/SIZE][/FONT][/COLOR][/SIZE][/FONT]
[FONT=Courier New][SIZE=2][COLOR=#800080][FONT=Courier New][SIZE=2][COLOR=#800080][FONT=Courier New][SIZE=2][COLOR=#800080]2[/COLOR][/SIZE][/FONT][/COLOR][/SIZE][/FONT][/COLOR][/SIZE][/FONT][FONT=Courier New][SIZE=2][FONT=Courier New][SIZE=2]) [/SIZE][/FONT][/SIZE][/FONT][FONT=Courier New][SIZE=2][COLOR=#800080][FONT=Courier New][SIZE=2][COLOR=#800080][FONT=Courier New][SIZE=2][COLOR=#800080]40    13[/COLOR][/SIZE][/FONT][/COLOR][/SIZE][/FONT][/COLOR][/SIZE][/FONT][FONT=Courier New][SIZE=2][COLOR=#800080][FONT=Courier New][SIZE=2][COLOR=#800080][FONT=Courier New][SIZE=2][COLOR=#800080]    15[/COLOR][/SIZE][/FONT][/COLOR][/SIZE][/FONT][/COLOR][/SIZE][/FONT]
[FONT=Courier New][SIZE=2][COLOR=#800080][FONT=Courier New][SIZE=2][COLOR=#800080][FONT=Courier New][SIZE=2][COLOR=#800080]3[/COLOR][/SIZE][/FONT][/COLOR][/SIZE][/FONT][/COLOR][/SIZE][/FONT][FONT=Courier New][SIZE=2][FONT=Courier New][SIZE=2]) [/SIZE][/FONT][/SIZE][/FONT][FONT=Courier New][SIZE=2][COLOR=#800080][FONT=Courier New][SIZE=2][COLOR=#800080][FONT=Courier New][SIZE=2][COLOR=#800080]12     4[/COLOR][/SIZE][/FONT][/COLOR][/SIZE][/FONT][/COLOR][/SIZE][/FONT][FONT=Courier New][SIZE=2][COLOR=#800080][FONT=Courier New][SIZE=2][COLOR=#800080][FONT=Courier New][SIZE=2][COLOR=#800080]     5[/COLOR][/SIZE][/FONT][/COLOR][/SIZE][/FONT][/COLOR][/SIZE][/FONT]

Hope this could help you.

Best regards.
 
C

ceaser

Active Member
Licensed User
Hi Agraham

Thanks for that. I did have a look at it, but have not played with it yet.

I suppose I could also use it in my surveying program, as there are routines which are based on some heavy maths. For instance the calculations involved in a spiral, cross-section calcs, or even in the CAD....

Thanks
Michael
 
You must log in or register to reply here.
Top