0

i am trying to find a algorithm or a way to find the intersection between two circle on a sphere (in 3d). For example if i have two circles center at two pointsA(latitude1,longitude1) and B(latidude2,longitude2) assuming that they intersect, how can i find the intersection between those two circles? is there an algorithm to do that?

Thank you

user3841581
  • 2,637
  • 11
  • 47
  • 72
  • 1
    Convert to 3D Cartesian coordinates. Find the parameters of the two planes on which the circles lie. Find the parameters of the line comprising the intersection of the planes. Find the points of intersection of the line with the sphere. Convert back to latitude/longitude. Watch out for degenerate cases. – David Eisenstat Sep 16 '14 at 13:42
  • @David Eisenstat can you please give me a numerical example or a source or reference from which i can read to have a clear picture on how to do it? Thank you – user3841581 Sep 16 '14 at 13:59

1 Answers1

3

  1. Convert from latitude/longitude to 3D Cartesian coordinates.

  2. For each circle, find the equation nx x + ny y + nz z = d of the plane whose intersection with the sphere is the circle. Assuming that the sphere is centered at the origin, the normal vector (nx, ny, nz) is the circle center (cx, cy, cz) (projected or not) after normalization.

                     (cx, cy, cz)
(nx, ny, nz) = -----------------
               ||(cx, cy, cz)||
                               2

    The distance d is computed using Pythagoras. Let r be the radius of the circle and R be the radius of the sphere.

     2    2    2
R  = d  + r
      _______     _______________
     | 2    2    |
d = \|R  - r  = \|(R + r) (R - r)

    The second expression is preferred for numerical stability.

    If we know only the length r' on the surface of the sphere from the projected center of the circle to the circle, then compute

    d = R cos(r'/R)
r = R sin(r'/R).

    We actually don’t need r in this case.

  3. Find the intersection of the two planes, a line.

  4. Find the intersection of the line and the sphere, between zero and two points.

  5. Convert the points to latitude/longitude.

Community
  • 1
  • 1
David Eisenstat
  • 64,237
  • 7
  • 60
  • 120
  • the 4th step is suppose to give me 0,1,or 2 for t right but i do not get it. After following the steps, i get something like 3.222 which is obviously wrong. i tried to check carefully but i seem to have followed the steps; i am not sure if i made or not because i check carefully many times and my calculation seems fine. – user3841581 Sep 17 '14 at 14:17
  • @user3841581 Search for another sphere-ray intersection answer then. There's a lot of them. – David Eisenstat Sep 17 '14 at 14:20
  • Thank you David Eisenstat; i think in my problem i might have to consider the intersection of disck in 2d instead. Thank you again for your time – user3841581 Sep 17 '14 at 14:22
  • after checking, my problem can not be reduced to 2D. can you please help me with a method or function which find those intersection points? say i have A(0,0) and B(0,30). can you please help me with a method or function which can help me to find that? Thank you – user3841581 Sep 18 '14 at 14:00