Hello

I have 3 points in space, and I'd like to get the coordinates of a 4th point.

The known data are
P1 : <P1.x, P1.y, P1.z>
P2 : <P2.x, P1.2, P2.z>
P3 : <P3.x, P1.3, P3.z>

Distance from point 1 to point 4 : D1
Distance from point 2 to point 4 : D2
Distance from point 3 to point 4 : D3


I tried with some formula (google : "trilateration" and "triangle resolution")

I could easily do this with 2 known points and 2 distances (on a fixed z plan)
but no way to get something working in 3D ^^

Any advice ?

Regards,
 Luc.

Post a reply to this message

Le 29/03/2012 14:31, Luc H. a écrit :
> Hello
> 
> I have 3 points in space, and I'd like to get the coordinates of a 4th point.
> 
> The known data are
> P1 : <P1.x, P1.y, P1.z>
> P2 : <P2.x, P1.2, P2.z>
> P3 : <P3.x, P1.3, P3.z>
> 
> Distance from point 1 to point 4 : D1
> Distance from point 2 to point 4 : D2
> Distance from point 3 to point 4 : D3
> 
> 
> I tried with some formula (google : "trilateration" and "triangle resolution")
> 
> I could easily do this with 2 known points and 2 distances (on a fixed z plan)
> but no way to get something working in 3D ^^
> 
> Any advice ?
> 

Too many data, nearly!

3 points define a triangle in space.
Each distance to point 4 define a sphere around a corner of that triangle.

From the first two distance, you get the intersection of 2 spheres.
* At worst: no intersection, no point 4.
* At best:, point 4 is on the segment and the intersection is that
single point. (well, check at least with the third distance)
* Usually: intersection of 2 spheres is a circle.

Now use the last sphere (the third distance from the third corner), and
intersect with the previous circle.
* at worst: no common,
* at best: point 4 is on the plane ot the triangle
* usually: you still have 2 candidates, in mirror position from the
plane of the triangle.

If you want it solved as a system of equations directly, you need to
specify the intersection of three spheres not at the origin. That will
gives you 3 spheres equations, all == 0, and you will push them in a
solver...


Notice: x²+y²+z²-1² = 0 is the equation for a sphere at <0,0,0> of radius 1.
The sphere at <i,j,k> of radius r has (x,y,z) matching:
(x-i)²+(y-j)²+(z-k)² - r² = 0

Post a reply to this message

Le_Forgeron <lef### [at] freefr> wrote:
>
> If you want it solved as a system of equations directly, you need to
> specify the intersection of three spheres not at the origin. That will
> gives you 3 spheres equations, all == 0, and you will push them in a
> solver...
>
>
> Notice: x²+y²+z²-1² = 0 is the equation for a sphere at <0,0,0> of radius 1.
> The sphere at <i,j,k> of radius r has (x,y,z) matching:
> (x-i)²+(y-j)²+(z-k)² - r² = 0

I totally agree !
And yes, I know there is 2 solutions (logical !)
BUT my problem is to compute this in POV, not on a paper :s

Example I have 3 points :
P1 <1,0,1>
P2 <4,1,3>
P3 <-1,-2,-1>

Distances :
||P1-P4|| = 3
||P2-P4|| = 5
||P3-P4|| = 2.5

I used the well known formula :

Then I rotate my point at distance 3 with the alpha angle.
The same for Y and Z rotation.
I thought it would work, but...  :'(

The other problem : this should be done in a POV macro.

Note for Le Forgeron : I'd like to restart an old work done by J.C Marteau
http://sibylone.free.fr/index.php?sub=repartition&lang=en
His repartition macro is excellent but can be optimised.

I thought about finding 3 points in an object then use a recursive macro to find
a 4th point, reuse this 4th point to get a 5th and so on...

JC used a random intensive approach which is costly but gives very good results.
http://sibylone.free.fr/povimg/planet_jewel_main.jpg
http://sibylone.free.fr/index.php?sub=repartition&lang=en&gal=g_extra_rep&img=puit_jewel2

I used another method to do the same, but it was 8 times longer.
Good results, anyway :
http://dilatt.free.fr/pov/povrep_01.png
http://dilatt.free.fr/pov/povrep_03.png

And as I need intensive repartitions in an animation, I need a faster macro :)

Post a reply to this message

"Luc H." <nomail@nomail> wrote:
> Hello
>
> I have 3 points in space, and I'd like to get the coordinates of a 4th point.
>
> The known data are
> P1 : <P1.x, P1.y, P1.z>
> P2 : <P2.x, P1.2, P2.z>
> P3 : <P3.x, P1.3, P3.z>
>
> Distance from point 1 to point 4 : D1
> Distance from point 2 to point 4 : D2
> Distance from point 3 to point 4 : D3
>
>
> I tried with some formula (google : "trilateration" and "triangle resolution")
>
> I could easily do this with 2 known points and 2 distances (on a fixed z plan)
> but no way to get something working in 3D ^^
>
> Any advice ?
>
> Regards,
>  Luc.

In 2D, clearly the condition to find (2) points is that D1+D2 >= D12

In 3D, the condition for (again 2, as remarked) points to exist will be more
complicated, involving the angles of the triangle and all three distances.

I'll think about the POV-Ray macro over the weekend. There should be a
non-iterative solution, when one exists.

Post a reply to this message

This is how I did it for 3 points.

#declare P1=<0,0,0>;
#declare R1=4;

#declare P2=<0,0,0>;
#declare R2=2;

#declare P3=<0,0,0>;
#declare R3=2;

#declare P4=<0,0,0>;
#declare R4=2;

#declare D12=R1+R2; // distance from P2 to P1
#declare D13=R1+R3; // distance from P3 to P2
#declare D23=R2+R3; // distance from P3 to P2

#declare D14=R1+R4; // distance from P4 to P1
#declare D24=R2+R4; // distance from P4 to P2
#declare D34=R3+R4; // distance ftom P4 to P3

// Coordinates of P2 are easy :
#declare P2=P1 + <D12,0,0>;

// Coordinates of P3 :
#declare alpha=acos((D13*D13 + D12*D12 - D23*D23)/(2*D13*D12));
#declare P3 = P1 + <D13*cos(alpha), D13*sin(alpha), 0>;

// Just playing with D12, D13 and D23 I have 3 spheres with radius R1, R2, R3
that touch each others, and on the XZ plan

// That's where it become tough : find the P4 coordinates knowing D14, D24 and
D34
#declare alx=acos((D14*D14+D12*D12-D14*D14)/(2*D14*D12));
#declare aly=acos((D14*D14+D13*D13-D34*D34)/(2*D14*D13));

// I thought P4 coordinates would be :
#declare P4x = D14*sin(alx);
#declare P4y = D14*cos(aly);
#declare P4z = D14*sin(aly);
// ... but seems to be buggy.
// I should have 4 spheres touching each other, but P4 is not at the good place.


sphere { P1, R1
         texture { pigment{ color rgbf <1,0,0,0.5> }
                   finish { phong 0.1 }
                 }
       }

sphere { P2, R2
         texture { pigment{ color rgbf <0,0,1,0.5> } // rgb< 1, 0.0, 0.0>}
                   finish { phong 0.1 }
                 }
       }

sphere { P3, R3
         texture { pigment{ color rgbf <0,1,0,0.5> } // rgb< 1, 0.0, 0.0>}
                   finish { phong 0.1 }
                 }
       }

sphere { P4, R4
         texture { pigment{ color rgbf <1,1,0,0.5> } // rgb< 1, 0.0, 0.0>}
                   finish { phong 0.1 }
                 }
       }

Post a reply to this message

"Luc H." <nomail@nomail> wrote:
> Hello
>
Luc,

This must be a solved problem, since it amounts to forming a tetrahedron given
the edge lengths, however...

What follows puts the initial triangle onto the x-y plane to make the geometry
easier. If it is something like what you want, I'll put it into vector form for
a general triangle orientation,

Jim

global_settings { ambient_light 4 }
//
#include "colors.inc"
//
#macro draw_axes (aT,aRad,xMin,xMax,yMin,yMax,zMin,zMax)
  object{
    union{
    cylinder{ <xMin,0,0>, <xMax,0,0>, aRad }
    cone    { <xMax,0,0>, 3*aRad, <xMax+8*aRad,0,0>, 0 }
    cylinder{ <0,yMin,0>, <0,yMax,0>, aRad }
    cone    { <0,yMax,0>, 3*aRad, <0,yMax+8*aRad,0>, 0 }
    cylinder{ <0,0,zMin>, <0,0,zMax>, aRad }
    cone    { <0,0,zMax>, 3*aRad, <0,0,zMax+8*aRad>, 0 }
    }
    texture{ aT }
  }
#end
//
//Draw the axes
//
#declare xMin = -5;
#declare xMax = 5;
#declare yMin = -5;
#declare yMax = 5;
#declare zMin = -5;
#declare zMax = 5;
#declare aT   = texture{ pigment { Black } }
#declare aRad = 0.05;
//
draw_axes (aT,aRad,xMin,xMax,yMin,yMax,zMin,zMax)
//
#macro tetrahedron(cRad,srad,p1,p2,p3,p4,d1,d2,d3)
//
union{
// Find the side lengths of the initial triangle
  #local d12 = vlength(p2-p1);
  #local d23 = vlength(p3-p2);
  #local d31 = vlength(p1-p3);
// Set the trial triangle on the x-y plane
  #local pp1 = <0,0,0>;
  #local pp2 = <d12,0,0>;
  #local x3  = (d12*d12+d31*d31-d23*d23)/(2*d12);
  #local y3  = sqrt(d31*d31-x3*x3);
  #local pp3 = <x3,y3,0>;
// Trial triangle vertices
  sphere{pp1 srad texture{pigment{Red}}}
  sphere{pp2 srad texture{pigment{Red}}}
  sphere{pp3 srad texture{pigment{Red}}}
// Joining trial triangle vertices
  cylinder{pp1 pp2 cRad texture{pigment{Blue}}}
  cylinder{pp2 pp3 cRad texture{pigment{Blue}}}
  cylinder{pp3 pp1 cRad texture{pigment{Blue}}}
// Trial triangle
  triangle{ pp1 pp2 pp3 texture{hT} }
// Calculating fourth vertex
// Start off working on the p1-p2-p4 triangle placed on the x-y plane
  #local       d     = (d12*d12+d1*d1-d2*d2)/(2*d12);
  #if(d>0)
     sphere{<0,0,-5> 0.5 pigment{Green}}
    #local     h     = d1*d1-d*d;
    #if(h>0)
      sphere{<0,0,-4> 0.5 pigment{Green}}
      #local   h     = sqrt(h);
      #local   costh = (d3*d3 - (x3-d)*(x3-d) - y3*y3 - h*h)/(2*y3*h);
      #local   sinth = 1 - costh*costh;
      #if(sinth > 0)
        sphere{<0,0,-3> 0.5 pigment{Green}}
        #local sinth = sqrt(sinth);
        #local pp4   = <d,-h*costh,h*sinth>;
      #else
        sphere{<0,0,-3> 0.5 pigment{Red}}
        #local pp4   = <0,0,0>;
      #end
    #else
      sphere{<0,0,-4> 0.5 pigment{Red}}
      #local   pp4   = <0,0,0>;
    #end
  #else
    sphere{<0,0,-5> 0.5 pigment{Red}}
    #local     pp4   = <0,0,0>;
  #end
//
  #if(abs(vlength(pp1-pp4)-d1)<(d1/10000000))
    sphere{  pp4     srad texture{pigment{Red}}}
    cylinder{pp1 pp4 cRad texture{pigment{Blue}}}
    cylinder{pp2 pp4 cRad texture{pigment{Blue}}}
    cylinder{pp3 pp4 cRad texture{pigment{Blue}}}
    triangle{pp1 pp2 pp4  texture{hT}}
    triangle{pp2 pp3 pp4  texture{hT}}
    triangle{pp3 pp1 pp4  texture{hT}}
  #end
// End of main union
     }
//
#end
//
// Joining line and vertex radii
//
#declare cRad = 0.05;
#declare sRad = 0.08;
//
// Joining line, convex hull and spline textures.
//
#declare cT   = texture{ pigment {  rgb<0,0,1> } }     //Blue
#declare hT   = texture{ pigment { rgbf<1,1,0,0.9> } } //Transparent yellow
#declare sT   = texture{ pigment {  rgb<0,1,0> } }     //Green
//
// Vertex definitions
//
#declare p1 = <0, 0  ,0>;
#declare p2 = <4, 0  ,0>;
#declare p3 = <2,3.46,0>;
#declare p4 = <0, 0  ,0>;
//
// Side lengths
//
#declare d1 = 4;
#declare d2 = 4;
#declare d3 = 4;
//
tetrahedron(cRad,sRad,p1,p2,p3,p4,d1,d2,d3)
//
background {color White}
light_source { <20,20,20> White shadowless}
camera{orthographic location <20,6,4> look_at <0,0,0> }

Post a reply to this message