[Extreme Math] Calculating a point equidistant from 3 others

[Jimlad]

Yeah like HP said, if you just need the middle of a group of objects just average the points. You should have said that at the start! Being "in the middle of" is not the same as "equidistant from", in fact the two are very different except in special cases. You should avoid using specific terminology when you aren't being specific about the meaning.

[Magos Mechanicus]

Aww, it's not needed after all.

Anyways, I thought that trilateration stuff sounded like an interesting problem, so I made an E2 to do the necessary coordinate transformations. Then I discover the circumcenter, which let me find the equidistant point much easier, and having the coordinate transformations done already it was quite easy to find. Here's the result. It'll find the circumcenter equidistant to any 3 points that have one (i.e. are not on a line).

@name Circumcenter
@inputs A:vector B:vector C:vector
@outputs Circumcenter:vector
#Coordinate transformations
 #First things first:
 #Finding an orthonormal basis.
    I = (B-A):normalized()
    J = (C-A):normalized()
    J = (J-J:dot(I)*I):normalized()
 if(!J){exit()} #If A,B,C are on a line, then exit before we get divide by 0 and such
    K = J:cross(I)
    RefFrame=transpose(matrix(I,J,K))
 #Finding the position vectors of the 3 points
 #in our new reference frame.
    A2 = vec()
    B2 = RefFrame*(B-A)
    C2 = RefFrame*(C-A)
 
#Finding the circumcenter in local coords
BisectX = B2:x()/2
BisectC = C2/2
DirC = vec(0,0,1):cross(C2):normalized()
DistC = (BisectX-BisectC:x())/DirC:x()
Circumcenter2 = BisectC + DistC*DirC
 
#Transforming results to world coords
Circumcenter = A + RefFrame^-1*Circumcenter2

[-HP-]

Aww, it's not needed after all.

Anyways, I thought that trilateration stuff sounded like an interesting problem, so I made an E2 to do the necessary coordinate transformations. Then I discover the circumcenter, which let me find the equidistant point much easier, and having the coordinate transformations done already it was quite easy to find. Anyways, here's the result. It'll find the circumcenter equidistant to any 3 points that have one (i.e. are not on a line).

@name Circumcenter
@inputs A:vector B:vector C:vector
@outputs Circumcenter:vector
#Coordinate transformations
 #First things first:
 #Finding an orthonormal basis.
    I = (B-A):normalized()
    J = (C-A):normalized()
    J = (J-J:dot(I)*I):normalized()
    K = J:cross(I)
    RefFrame=transpose(matrix(I,J,K))
 #Finding the position vectors of the 3 points
 #in our new reference frame.
    A2 = vec()
    B2 = RefFrame*(B-A)
    C2 = RefFrame*(C-A)
 
#Finding the circumcenter in local coords
BisectX = B2:x()/2
BisectC = C2/2
DirC = vec(0,0,1):cross(C2):normalized()
DistC = (BisectX-BisectC:x())/DirC:x()
Circumcenter2 = BisectC + DistC*DirC
 
#Transforming results to world coords
Circumcenter = A + RefFrame^-1*Circumcenter2

Wow. I've no idea what the hell you do in that expression, it's faaaaar beyong me. Awesome, will keep that in mind and see if I need it sometime

[Jimlad]

haha, good stuff. Yeah I guess the circumcentre is probably the most direct way of finding one of the equidistant points. I haven't thought about it much, but I guess there are two others, opposite to each other normal to the plane of the triangle? Cool use of the matrix functions! I like how, rather than messing about with general formulae, you simplified it and just aligned the axes with the points.

[Magos Mechanicus]

Thanks. I think that's right, though they may take some more pondering to find. They wouldn't be at the same distance as the circumcenter, would they? Also, using matrix*vector to transform coordinates was a lifesaver in the below stuff particularly because you can scale matrices by a scalar, so thanks for adding them.

So today I finally got E2 holograms working and my first project to try and learn that was to illustrate the method in the above expression. The holo portion came out as about half of the gate afterwards, but it looks so cool I guess that's ok.

I find it works best to take 3 GPSes and hook their vector outputs up to A,B and C, then jiggle them about relative to one another and watch the reaction. Use Hologramscale to scale the holograms - at 1 you should be able to line the GPSes up with the respective points (though it's tricky), at 0.5 the figure is at half size, at 2 it's at double size and so on. If Hologramscale is 0 the holograms are not used. By default it shows the triangle formed by the three input points - the red side goes from A (directly above the expression) to B, and the last point is C. The little cube marks the circumcenter. You can turn on Guidelines to see the two lines I use to find the circumcenter; it's found where they intersect. Each starts on the halfway mark of the respective triangle side and is normal to it. The last option is to turn on the circumcircle, just to show that it is indeed equidistant to the 3 points.

@name Circumcenter
@inputs A:vector B:vector C:vector
@inputs Hologramscale Guidelines Circumcircle
@outputs Circumcenter:vector C2:vector
#Coordinate transformations
 #First things first:
 #Finding an orthonormal basis.
    I = (B-A):normalized()
    J = (C-A):normalized()
    J = (J-J:dot(I)*I):normalized()
 if(!J){exit()} #If A,B,C are on a line, then exit before we get divide by 0 and such
    K = I:cross(J)
    RefFrame=transpose(matrix(I,J,K))
 #Finding the position vectors of the 3 points
 #in our new reference frame.
    A2 = vec()
    B2 = RefFrame*(B-A)
    C2 = RefFrame*(C-A)
 
 
#Finding the circumcenter in local coords
BisectX = B2:x()/2
BisectC = C2/2
DirC = vec(0,0,1):cross(C2):normalized()
DistC = (BisectX-BisectC:x())/DirC:x()
Circumcenter2 = BisectC + DistC*DirC
 
#Transforming results to world coords
Circumcenter = A + transpose(RefFrame)*Circumcenter2
 
 
#Let's be fancy. Illustrative Holograms!
if(first()|duped()){createHolo(0) createHolo(1) createHolo(2)
   createHolo(3) createHolo(4) createHolo(5) createHolo(6)}
if(Hologramscale){
 interval(250)
    Model = "box" Skin = 1
    Pos = entity():pos() + 20*entity():up()
    Holoframe=matrix(entity())*Hologramscale
    Scalingfactor = Hologramscale/11.867 
 #A holoScale of 1 is 1 PHX unit, not 1 Gmod unit
 
 #The triangle itself
    Temp = B2/2
    Temp = Pos + Holoframe*Temp
    holoPos(0,Temp)
    holoColor(0,vec(255,0,0),255)
    holoModel(0,Model,Skin)
    holoScale(0,(B2+vec(0,1,1))*Scalingfactor)
    holoAng(0,(Holoframe*B2):toAngle())
    Temp = BisectC
    Temp = Pos + Holoframe*Temp
    holoPos(1,Temp)
    holoModel(1,Model,Skin)
    holoColor(1,vec(0,255,0),255)
    holoScale(1,vec(C2:length(),1,1)*Scalingfactor)
    holoAng(1,(Holoframe*C2):toAngle())
    Temp = B2 + (C2-B2)/2
    Temp = Pos + Holoframe*Temp
    holoPos(2,Temp)
    holoModel(2,Model,Skin)
    holoColor(2,vec(0,0,255),255)
    holoScale(2,vec((C2-B2):length(),1,1)*Scalingfactor)
    holoAng(2,(Holoframe*(C2-B2)):toAngle())
 
 #The circumcenter
    Temp = Circumcenter2
    Temp = Pos + Holoframe*Temp
    Dir = vec(0,1,0)
    holoPos(3,Temp)
    holoModel(3,Model,Skin)
    holoColor(3,vec(0,160,60),255)
    holoScale(3,vec(Dir:length(),1,1)*Scalingfactor)
    holoAng(3,(Holoframe*Dir):toAngle())
 
 #The guidelines used to find the circumcenter
 if(Guidelines){
        Temp = (B2/2 + Circumcenter2)/2
        Temp = Pos + Holoframe*Temp
        Dir = vec(0,1,0)
        holoPos(4,Temp)
        holoModel(4,Model,Skin)
        holoColor(4,vec(0,160,60),255)
        holoScale(4,vec((Circumcenter2-B2/2):length(),1,1)*Scalingfactor)
        holoAng(4,(Holoframe*Dir):toAngle())
        Temp = (Circumcenter2 + BisectC)/2
        Temp = Pos + Holoframe*Temp
        Dir = DirC
        holoPos(5,Temp)
        holoModel(5,Model,Skin)
        holoColor(5,vec(0,160,60),255)
        holoScale(5,vec(DistC,1,1)*Scalingfactor)
        holoAng(5,(Holoframe*DirC):toAngle())
 }else{holoColor(4,vec(),0) holoColor(5,vec(),0)}
 
 #The circumcircle
 if(Circumcircle){
        Radius = Circumcenter2:length()
        Temp = Circumcenter2
        Temp = Pos + Holoframe*Temp
        holoPos(6,Temp)
        holoModel(6,"cylinder",Skin)
        holoColor(6,vec(0,160,60),40)
        holoScale(6,vec(2*Radius,2*Radius,1)*Scalingfactor)
        holoAng(6,(Holoframe*vec(1,0,0)):toAngle())
 }else{holoColor(6,vec(),0)}
}

[Jimlad]

ooh that looks pretty neat, I'm going to have to check it out when I'm around later on. Yeah I didn't think the whole "other points" thing through, now that you mention it I'm pretty sure there aren't just two points, you'll have a line through the circumcentre, perpendicular to the plane that represents all the solutions. I think you'd need at least 4 points to start uniquely defining spheres.

I'm going to have to check out those holograph functions, it makes me wonder whether you can't just use matrices to define them rather than setting a bunch of vectors/angles.

[Manaan]

I think you just destroyed my brain.
This is way beyond me.

[IamMcLovin]

Thanks. I think that's right, though they may take some more pondering to find. They wouldn't be at the same distance as the circumcenter, would they? Also, using matrix*vector to transform coordinates was a lifesaver in the below stuff particularly because you can scale matrices by a scalar, so thanks for adding them.

So today I finally got E2 holograms working and my first project to try and learn that was to illustrate the method in the above expression. The holo portion came out as about half of the gate afterwards, but it looks so cool I guess that's ok.

I find it works best to take 3 GPSes and hook their vector outputs up to A,B and C, then jiggle them about relative to one another and watch the reaction. Use Hologramscale to scale the holograms - at 1 you should be able to line the GPSes up with the respective points (though it's tricky), at 0.5 the figure is at half size, at 2 it's at double size and so on. If Hologramscale is 0 the holograms are not used. By default it shows the triangle formed by the three input points - the red side goes from A (directly above the expression) to B, and the last point is C. The little cube marks the circumcenter. You can turn on Guidelines to see the two lines I use to find the circumcenter; it's found where they intersect. Each starts on the halfway mark of the respective triangle side and is normal to it. The last option is to turn on the circumcircle, just to show that it is indeed equidistant to the 3 points.

@name Circumcenter
@inputs A:vector B:vector C:vector
@inputs Hologramscale Guidelines Circumcircle
@outputs Circumcenter:vector C2:vector
#Coordinate transformations
 #First things first:
 #Finding an orthonormal basis.
    I = (B-A):normalized()
    J = (C-A):normalized()
    J = (J-J:dot(I)*I):normalized()
 if(!J){exit()} #If A,B,C are on a line, then exit before we get divide by 0 and such
    K = I:cross(J)
    RefFrame=transpose(matrix(I,J,K))
 #Finding the position vectors of the 3 points
 #in our new reference frame.
    A2 = vec()
    B2 = RefFrame*(B-A)
    C2 = RefFrame*(C-A)
 
 
#Finding the circumcenter in local coords
BisectX = B2:x()/2
BisectC = C2/2
DirC = vec(0,0,1):cross(C2):normalized()
DistC = (BisectX-BisectC:x())/DirC:x()
Circumcenter2 = BisectC + DistC*DirC
 
#Transforming results to world coords
Circumcenter = A + transpose(RefFrame)*Circumcenter2
 
 
#Let's be fancy. Illustrative Holograms!
if(first()|duped()){createHolo(0) createHolo(1) createHolo(2)
   createHolo(3) createHolo(4) createHolo(5) createHolo(6)}
if(Hologramscale){
 interval(250)
    Model = "box" Skin = 1
    Pos = entity():pos() + 20*entity():up()
    Holoframe=matrix(entity())*Hologramscale
    Scalingfactor = Hologramscale/11.867 
 #A holoScale of 1 is 1 PHX unit, not 1 Gmod unit
 
 #The triangle itself
    Temp = B2/2
    Temp = Pos + Holoframe*Temp
    holoPos(0,Temp)
    holoColor(0,vec(255,0,0),255)
    holoModel(0,Model,Skin)
    holoScale(0,(B2+vec(0,1,1))*Scalingfactor)
    holoAng(0,(Holoframe*B2):toAngle())
    Temp = BisectC
    Temp = Pos + Holoframe*Temp
    holoPos(1,Temp)
    holoModel(1,Model,Skin)
    holoColor(1,vec(0,255,0),255)
    holoScale(1,vec(C2:length(),1,1)*Scalingfactor)
    holoAng(1,(Holoframe*C2):toAngle())
    Temp = B2 + (C2-B2)/2
    Temp = Pos + Holoframe*Temp
    holoPos(2,Temp)
    holoModel(2,Model,Skin)
    holoColor(2,vec(0,0,255),255)
    holoScale(2,vec((C2-B2):length(),1,1)*Scalingfactor)
    holoAng(2,(Holoframe*(C2-B2)):toAngle())
 
 #The circumcenter
    Temp = Circumcenter2
    Temp = Pos + Holoframe*Temp
    Dir = vec(0,1,0)
    holoPos(3,Temp)
    holoModel(3,Model,Skin)
    holoColor(3,vec(0,160,60),255)
    holoScale(3,vec(Dir:length(),1,1)*Scalingfactor)
    holoAng(3,(Holoframe*Dir):toAngle())
 
 #The guidelines used to find the circumcenter
 if(Guidelines){
        Temp = (B2/2 + Circumcenter2)/2
        Temp = Pos + Holoframe*Temp
        Dir = vec(0,1,0)
        holoPos(4,Temp)
        holoModel(4,Model,Skin)
        holoColor(4,vec(0,160,60),255)
        holoScale(4,vec((Circumcenter2-B2/2):length(),1,1)*Scalingfactor)
        holoAng(4,(Holoframe*Dir):toAngle())
        Temp = (Circumcenter2 + BisectC)/2
        Temp = Pos + Holoframe*Temp
        Dir = DirC
        holoPos(5,Temp)
        holoModel(5,Model,Skin)
        holoColor(5,vec(0,160,60),255)
        holoScale(5,vec(DistC,1,1)*Scalingfactor)
        holoAng(5,(Holoframe*DirC):toAngle())
 }else{holoColor(4,vec(),0) holoColor(5,vec(),0)}
 
 #The circumcircle
 if(Circumcircle){
        Radius = Circumcenter2:length()
        Temp = Circumcenter2
        Temp = Pos + Holoframe*Temp
        holoPos(6,Temp)
        holoModel(6,"cylinder",Skin)
        holoColor(6,vec(0,160,60),40)
        holoScale(6,vec(2*Radius,2*Radius,1)*Scalingfactor)
        holoAng(6,(Holoframe*vec(1,0,0)):toAngle())
 }else{holoColor(6,vec(),0)}
}

Some one is making something useful other then a holo jizz contraption!

[Magos Mechanicus]

Got to thinking more about this problem, and I realized that assuming the equidistant point of 4 given points is on the line through the circumcenter of the first 3, you could instead of doing any geometry use the condition of equidistance to solve for z algebraically. I threw it into Maple and the z^2 term cancels so there's no bothering with the whole 0-2 solutions business. Encouraged by this, I tested it in game. The expression reports that it is indeed equidistant when I use V:length(), but the sphere hologram is apparently a bit too coarse-grained to show it very well.

Indeed, there's a lot of stuff you can do with the holograms other than create randomly floating stuff. They're really fun to use, and I think I'm going to go for a wall clock soon.

[ZeikJT]

If you want a smoother sphere use a bigger number.
sphere is the clunkiest.
sphere2 is more smooth.
sphere3 is the most smooth.

I left the default as the clunkiest so people don't spam the most intensive one without reason.