Tricky Geometry...
Blitz3D Forums/Blitz3D Programming/Tricky Geometry...
| ||
| This is much harder than it first seemed. I have a triangle in 3D space made by 3 objects placed at various coords. The triangle isn't aligned to any axes, so if you can imagine it stands at an angle. I am trying to find the coordinates of a position in the centre of this triangle. However, I have only the corners' coords to work from ( and they're not nice numbers!) The point I am looking for is equidistant from each corner. Any maths genises out there that cold help me out? I have a formla for bisecting the edges, and drawing Normal tangents to the midpoints. Where these Normals intersect is the middle of the triangle, but I need to elevate this to the angle of the triangle itself. coords are: -3.1x,-19.2y,14.9z 21.2x,-8.9y,15.6z -1.1x,-12.4y,39.4z |
| ||
| How about averging your three coordinates?: x = (x1 + x2 + x3) / 3 y = (y1 + y2 + y3) / 3 z = (z1 + z2 + z3) / 3 -> x = ( -3.1 - 19.2 + 14.9 ) / 3 y = ( 21.2 - 8.9 + 15.6 ) / 3 z = ( -1.1 - 12.4 + 39.4 ) / 3 Not sure it will work, though.. |
| ||
| That's the center of mass, which I would consider the 'center' of the triangle. Note that it will usually not be equidistant from the three vertices. |
| ||
| I cannot see why it doesn't, although plotting the points on an orthographic graph shows that they are not correct. Interesting, and thanks ;) |
| ||
| take the distance between any two points in the triangle and find the midpoint(call that x). then find the midpoint between the x and the other point in the triangle. that should give you the midpoint of the triangle. :) (and i agree with floyd. the centre is only equidistant if it is an equilateral or isosceles triangle) _________________ ``==--..,..--==`` imagine that being a triangle. the centre is not equidistant example for finding centre of triangle
ax=0
ay=0
az=0
bx=10
by=0
bz=0
cx=5
cy=10
cz=0
temp_mid_point_x=ax-((ax-bx)/2)
temp_mid_point_y=ay-((ay-by)/2)
temp_mid_point_z=az-((az-bz)/2)
actual_mid_point_x=temp_mid_point_x-((temp_mid_point_x-cx)/2)
actual_mid_point_y=temp_mid_point_y-((temp_mid_point_y-cy)/2)
actual_mid_point_z=temp_mid_point_z-((temp_mid_point_z-cz)/2)
Print "midpoint of triangle ("+actual_mid_p troint_x+","+actual_mid_point_y+","+actual_mid_point_z+")"
|
| ||
| It is simple enough to find the midpoint per axis between point A and B, but point C must be considered too. Although it is a 2D triangle, it is in 3D space, and therefore all 3 dimnensions need to be considered. This is what makes it difficult. |
| ||
Graphics3D 1024,768,16,2
SetBuffer BackBuffer()
AmbientLight 255,200,200
light=CreateLight(2)
cam=CreateCamera()
CameraViewport cam,0,0,1024,768
A=CreateCube()
EntityColor A,255,200,0
B=CreateCube()
EntityColor B,50,50,200
C=CreateCube()
EntityColor C,0,255,0
PositionEntity A,-3.1,-19.2,14.9
PositionEntity B,21.2,-8.9,15.6
PositionEntity C,-1.1,-12.4,39.4
sphere=CreateSphere(50)
EntityParent light,sphere
PositionEntity cam,-60,50,50
PointEntity cam,sphere
temp_mid_point_x=EntityX#(A)-((EntityX#(A)-(EntityX#(B))/2) )
temp_mid_point_y=EntityY#(A)-((EntityY#(A)-(EntityY#(B))/2) )
temp_mid_point_z=EntityZ#(A)-((EntityZ#(A)-(EntityZ#(B))/2) )
actual_mid_point_x=temp_mid_point_x-((temp_mid_point_x-EntityX#(C))/2)
actual_mid_point_y=temp_mid_point_y-((temp_mid_point_y-EntityY#(C))/2)
actual_mid_point_z=temp_mid_point_z-((temp_mid_point_z-EntityZ#(C))/2)
x#=actual_mid_point_x
y#=actual_mid_point_y
z#=actual_mid_point_z
;"midpoint of triangle ("+actual_mid_p troint_x+","+actual_mid_point_y+","+actual_mid_point_z+")"
PositionEntity sphere,x#,y#,z#
UpdateWorld
RenderWorld
A_dist#=EntityDistance#(sphere,A)
B_dist#=EntityDistance#(sphere,B)
C_dist#=EntityDistance#(sphere,C)
Text 500,0,x#+","+y#+","+z#+","
Text 500,20,A_dist#
Text 500,50,B_dist#
Text 500,80,C_dist#
Flip
I am actually looking for the equidistant point bewteen all 3 corners... Hehe told ya it was tricky :) |
| ||
| As you pointed out at the beginning this easy enough in principle. But the details of the calculation are fairly gruesome. If you want another approach, consider the circle determined by the three points. The center of this circle is equidistant from them. Here's a description of the solution: circle from three points. Oops, just realized that is for 2d, i.e. no z. That's what I get for trying to help without making any real effort. Still, it's handy to know about Paul Bourke's site. Lots of neat stuff there. |
| ||
| that would lie outside the triangle, in most triangles.my code finds the centre of a 3d triangle. least it should, i'll be back :) |
| ||
| Maybe a sphere that touches all three points? but that may just overcomplicate matters... |
| ||
| Even though the points are in 3d space they still determine a circle. The center of that circle is the desired point. In general this point may not be anywhere near the triangle. Imagine a very large circle. Any three points on the circle are equidistant from the center, as are all points on the circle. If the three points are widely scattered around the circle then the center of the circle will be near the 'middle' of the triangle. But if the three points are clustered together then you have a small triangle. The center of the circle is far away from the triangle. |
| ||
| i know how to do it. triangle ABC. find the midpoint on line AB. find the midpoint on either line BC or AC. then find the point where them line meet. that is the mathimatical centre. |
| ||
| If you wnat a point that is equidistant from all three points in a triangle, then all you have to do is solve a series of equations: D = SQR((X1-X4)^2 + (Y1-Y4)^2 + (Z1-Z4)^2) D = SQR((X2-X4)^2 + (Y2-Y4)^2 + (Z2-Z4)^2) D = SQR((X3-X4)^2 + (Y3-Y4)^2 + (Z3-Z4)^2) 1, 2, and 3 are the points of the triangle. 4 is the centerpoint. Those equations calculate the distance between each corner point and the center point. We don't know the center point, but we do know that the distance is the same for all. D is the distance, and it is found in all three equations. As we don't actually need to find the distance, we can simplify the equations somewhat right off the bat: D = (X1-X4)^2 + (Y1-Y4)^2 + (Z1-Z4)^2 D = (X2-X4)^2 + (Y2-Y4)^2 + (Z2-Z4)^2 D = (X3-X4)^2 + (Y3-Y4)^2 + (Z3-Z4)^2 So now we're looking for D^2 for each set of points. Unfortunately, I don't know how to proceed from here. Unlike myself and many folks here, the folks on #math on IRC are rude, elitist, and unhelpful and refused to answer my "too-easy for them" questions about how to simplify equations when you have stuff that is squared in it. So I don't know how to extract X4 Y4 and Z4 from the parentheses so I can get them on the other side of the equation. What I did get out of them though is that sqr((x-z)^2) is not (x-z), it is |x-z|. So that cuts off one avenue I was considering for solving it. |
| ||
| Btw, here is a reference on Mathworld about this sort of thing: http://mathworld.wolfram.com/Circumcenter.html |
| ||
| sswift, am i right in assuming that to find the centre of the triangle you need to find two midpoints thenfind where in 3d space they intersect? |
| ||
| "sswift, am i right in assuming that to find the centre of the triangle you need to find two midpoints thenfind where in 3d space they intersect?" I don't know, and you are not being very specifc. If you check out that mathword site there's LOTS of different "centers" for triangles which you can find. Which you actually need depends on what you want to use it for. You can find one center by drawing lines from the center of each side perpendicular to the side and dtermining where they intersect. You can find another "center" by finding the circumcenter. Then there's the center of mass which you can get just by averaging the locations of the points. So you need to be more specific waht you want to do with it. |
| ||
| Well I projected the coords onto a graph orthographically, so I had 3 triangles one each as seen from PLAN, SIDE and FACE projection. I found the midpoint of each, which gave me 2 coords each. either XY,YZ or XZ Basically, I obtained a value for X Y and Z anyhow and fed them into my program above, but althogh I am confident abot it being the centre of mass, it is again, not equidistant :( Thanks for that link, Sswift - very good stuff, only I don't have the angles to work with... |
| ||
| the centre using the perdendicular sides is more what i'm needing, sorry to hijack the thread malice :) the program above doesn't really give you the exact centre of the triangle, it's a wee bit off but it's still pretty close. i looked into it and it's pretty deep the stuff for finding where two 3d lines intersect :S |
| ||
| Well, I'm officially bad a maths but I recently needed to add a vertex to the centre of all tris in a mesh in order to do per-tri rotations. This is the code I came up with, where: x0,y0,z0 = vert 0 coords. x1,y1,z1 = vert 1 coords. x2,y2,z2 = vert 2 coords. ; Calculate and add a lone 'centre of tri' ; vertex (needed for per-tri rotations). tx# = x1 + ((x2-x1)/2) ty# = y1 + ((y2-y1)/2) tz# = z1 + ((z2-z1)/2) cvx# = tx - ((tx-x0)/3) cvy# = ty - ((ty-y0)/3) cvz# = tz - ((tz-z0)/3) AddVertex(d_surf,cvx,cvy,cvz) It seemed to do the job. Appologies if this is no good (i.e. crap) or is a method you've already discussed - like I say, I'm not a maths person. ;) |
| ||
| Hello, my first reply was not what you were after, but now I think I have got it: Try this piece of code :-) ;Circumcenter by Jeppe Nielsen 2003 ; Find a triangleīs circumcenter; ; a center that is equally away from all of itīs vertices Global circumcenterx#,circumcentery#,circumcenterz# Graphics3D 800,600,16,2 HidePointer SeedRnd MilliSecs() pivot=CreatePivot() cam=CreateCamera(pivot) PositionEntity cam,0,0,-10 Dim entity(4) findcircumcenter(Rnd(-4,4),Rnd(-4,4),Rnd(-4,4),Rnd(-4,4),Rnd(-4,4),Rnd(-4,4),Rnd(-4,4),Rnd(-4,4),Rnd(-4,4)) Repeat If KeyHit(57) findcircumcenter(Rnd(-4,4),Rnd(-4,4),Rnd(-4,4),Rnd(-4,4),Rnd(-4,4),Rnd(-4,4),Rnd(-4,4),Rnd(-4,4),Rnd(-4,4)) EndIf TurnEntity pivot,MouseYSpeed()/2,-MouseXSpeed()/2,0 MoveMouse 400,300 If KeyDown(200) Then MoveEntity cam,0,0,.1 If KeyDown(208) Then MoveEntity cam,0,0,-.1 RenderWorld() Color 255,255,0 Rect 10,50,20,20 Color 0,0,255 Rect 10,80,20,20 Color 255,255,255 Text 10,10,"Mouse to rotate view" Text 10,30,"Space to create a new triangle" Text 40,50,"Circumcenter" Text 40,80,"Circumsphere" Flip Until KeyDown(1) End Function findcircumcenter(x1#,y1#,z1#,x2#,y2#,z2#,x3#,y3#,z3#) For n=0 To 4 If entity(n)<>0 FreeEntity entity(n) EndIf Next dx1#=(x2#-x1#) dy1#=(y2#-y1#) dz1#=(z2#-z1#) dx2#=(x3#-x1#) dy2#=(y3#-y1#) dz2#=(z3#-z1#) dx3#=(x3#-x2#) dy3#=(y3#-y2#) dz3#=(z3#-z2#) entity(0)=CreateCylinder(3,0) PositionMesh entity(0),0,1,0 PositionEntity entity(0),x1#,y1#,z1# l#=Sqr(dx1*dx1+dy1*dy1+dz1*dz1)/2.0 ScaleEntity entity(0),0.01,l#,0.01 AlignToVector entity(0),dx1,dy1,dz1,2 entity(1)=CreateCylinder(3,0) PositionMesh entity(1),0,1,0 PositionEntity entity(1),x1#,y1#,z1# l#=Sqr(dx2*dx2+dy2*dy2+dz2*dz2)/2.0 ScaleEntity entity(1),0.01,l#,0.01 AlignToVector entity(1),dx2,dy2,dz2,2 entity(2)=CreateCylinder(3,0) PositionMesh entity(2),0,1,0 PositionEntity entity(2),x2#,y2#,z2# l#=Sqr(dx3*dx3+dy3*dy3+dz3*dz3)/2.0 ScaleEntity entity(2),0.01,l#,0.01 AlignToVector entity(2),dx3,dy3,dz3,2 For n=0 To 2 EntityFX entity(n),1 Next ; Start math part :-) dx1#=(x2#-x1#) dy1#=(y2#-y1#) dz1#=(z2#-z1#) dx2#=(x3#-x1#) dy2#=(y3#-y1#) dz2#=(z3#-z1#) tnx# = dy1 * dz2 - dy2 * dz1 tny# = dz1 * dx2 - dz2 * dx1 tnz# = dx1 * dy2 - dx2 * dy1 sx1#=(x1#+x3#)/2.0 sy1#=(y1#+y3#)/2.0 sz1#=(z1#+z3#)/2.0 dx1#=(sx1#-x1#) dy1#=(sy1#-y1#) dz1#=(sz1#-z1#) dx2#=tnx# dy2#=tny# dz2#=tnz# nx# = dy1 * dz2 - dy2 * dz1 ny# = dz1 * dx2 - dz2 * dx1 nz# = dx1 * dy2 - dx2 * dy1 sx2#=sx1#+nx# sy2#=sy1#+ny# sz2#=sz1#+nz# sx3#=(x1#+x2#)/2.0 sy3#=(y1#+y2#)/2.0 sz3#=(z1#+z2#)/2.0 dx1#=(sx3#-x1#) dy1#=(sy3#-y1#) dz1#=(sz3#-z1#) dx2#=tnx# dy2#=tny# dz2#=tnz# nx# = dy1 * dz2 - dy2 * dz1 ny# = dz1 * dx2 - dz2 * dx1 nz# = dx1 * dy2 - dx2 * dy1 sx4#=sx3#+nx# sy4#=sy3#+ny# sz4#=sz3#+nz# ax#=sx2#-sx1# ay#=sy2#-sy1# az#=sz2#-sz1# bx#=sx4#-sx3# by#=sy4#-sy3# bz#=sz4#-sz3# cx#=sx3#-sx1# cy#=sy3#-sy1# cz#=sz3#-sz1# qx1# = cy * bz - by * cz qy1# = cz * bx - bz * cx qz1# = cx * by - bx * cy qx2# = ay * bz - by * az qy2# = az * bx - bz * ax qz2# = ax * by - bx * ay dot#=qx1*qx2+qy1*qy2+qz1*qz2 le#=Sqr(qx2*qx2+qy2*qy2+qz2*qz2) si#=dot#/(le#*le#) circumcenterx#=sx1#+ax#*si# circumcentery#=sy1#+ay#*si# circumcenterz#=sz1#+az#*si# ; End math part :-) entity(3)=CreateSphere(16) PositionEntity entity(3),circumcenterx#,circumcentery#,circumcenterz# ScaleEntity entity(3),0.05,0.05,0.05 EntityColor entity(3),255,255,0 EntityFX entity(3),1 dx#=circumcenterx#-x1# dy#=circumcentery#-y1# dz#=circumcenterz#-z1# rad#=Sqr(dx*dx+dy*dy+dz*dz) entity(4)=CreateSphere(24) PositionEntity entity(4),circumcenterx#,circumcentery#,circumcenterz# ScaleEntity entity(4),rad,rad,rad EntityAlpha entity(4),0.75 EntityColor entity(4),0,0,255 EntityOrder entity(4),1 End Function Hope you can use it :) |
| ||
| Did you solve your problem ? |
| ||
| the thing i can see tho that the Circumcenter is not always inside the triangle unless it has two or three similar angles. it's a toughy tho, u think it would be easy to find the centre of a tri :S |
| ||
| Well, I was trying this to help a friend out ( I didnt think it would be this hard!) and I found the coords that gave a close enough equidistant point, although I cannot prove this point mathematically, my friend is currently on holiday and I think the coords I obtained were acceptable, So thanks for all your help ;) |
| ||
| With your coords from your first post, I have found the equidistant point for the three vertices, using my program above. They are as follows: x: 7.92265 y: -12.0732 z: 25.2974 Run this piece of code to see that the three distances are equal: ;triangle coords ;-3.1x,-19.2y,14.9z ;21.2x,-8.9y,15.6z ;-1.1x,-12.4y,39.4z ;circumcenter coords x#=7.92265 y#=-12.0732 z#=25.2974 dx#=(-3.1-x) dy#=(-19.2-y) dz#=(14.9-z) dist1#=Sqr(dx*dx+dy*dy+dz*dz) dx#=(21.2-x) dy#=(-8.9-y) dz#=(15.6-z) dist2#=Sqr(dx*dx+dy*dy+dz*dz) dx#=(-1.1-x) dy#=(-12.4-y) dz#=(39.4-z) dist3#=Sqr(dx*dx+dy*dy+dz*dz) Print dist1 Print dist2 Print dist3 ;all distances are equal MouseWait |
| ||
| Thanks lots, Jeppe! My original coords that I felt happy with, (here substituted into your code) ;triangle coords ;-3.1x,-19.2y,14.9z ;21.2x,-8.9y,15.6z ;-1.1x,-12.4y,39.4z ;circumcenter coords x#=5.0 y#=-5.1 z#=23.6 dx#=(-3.1-x) dy#=(-19.2-y) dz#=(14.9-z) dist1#=Sqr(dx*dx+dy*dy+dz*dz) dx#=(21.2-x) dy#=(-8.9-y) dz#=(15.6-z) dist2#=Sqr(dx*dx+dy*dy+dz*dz) dx#=(-1.1-x) dy#=(-12.4-y) dz#=(39.4-z) dist3#=Sqr(dx*dx+dy*dy+dz*dz) Print dist1 Print dist2 Print dist3 give a reasonable 18.45 - ish! But thanks, your coords are much more accurate, and it is strange that the coordinates are so different, yet they work the same in both my code and yours, so must be right :) Thanks once again! |
   |