Spherical Geometry

Date: 02/10/2003 at 08:49:17
From: Russ
Subject: Spherical geometry.

How do I calculate whether two lines that lie on the surface of a 
sphere intersect, and if they do intersect, the point of that 
intersection?

The lines are actually 'straight' as opposed to arcs due to the way 
the spherical polygons are defined as 3D line segments.  However my 
problem lies in determining if the lines cross and where.

Date: 02/10/2003 at 09:29:20
From: Doctor Rick
Subject: Re: Spherical geometry.

Hi, Russ.

Perhaps you can give us some more information. What do you know about 
the lines? Are they specified in terms of the end points in spherical 
coordinates (angles theta and phi), perhaps? Or in 3-d Cartesian 
coordinates x,y,z? Or are the lines specified by one point and a 
direction? There are many possibilities. If I know what information 
we have, it will be easier to decide what method to use to find the 
intersection.

Since the lines are straight and not along the surface of the sphere, 
the problem may be harder, depending on what you mean by crossing or 
intersecting. One line might pass "above" or "below" the other 
(farther or closer to the center of the sphere). If so, are they 
intersecting (in your meaning) or not?

- Doctor Rick, The Math Forum
  http://mathforum.org/dr.math/ 

Date: 02/10/2003 at 10:14:26
From: Russ
Subject: Spherical geometry.

Thanks for getting back to me.  I have been giving the matter more 
consideration and things are perhaps more complex than I first 
thought.

Firstly the line segments are defined using cartesian coordinates 
(x,y,z). The vertices (or start and end points) of the segments are 
on the surface of a sphere but obviously the segments do not follow 
the surface between them.

The point of intersection I am interested in is that seen from the 
centre of the sphere. As you suggest, the intersection may not 
actually occur in 3D space, yet I have to determine the correct point 
on the line segments. So, if we had a line that projected out from the 
centre of the sphere it would intersect the two line segments at the 
point of intersection as viewed when looking down our projected line.

Thanks again.

Date: 02/10/2003 at 15:38:50
From: Doctor Rick
Subject: Re: Spherical geometry.

Hi, Russ. Thanks for the additional information; it makes the 
situation clear. Now we can get to work.

One way we can think of it is this. Each line segment, together with 
the origin of the sphere, defines a plane. We can find the 
intersection of the planes defined by the two line segments; this will 
be a line through the origin, and we will then be able to find the 
intersection of this line with the sphere. This is the point of 
intersection as you are defining it (I believe).

The only other issue is whether the point we have found lies between 
the end points of each line segment. I'll think about that later.

Let's say line segment 1 has endpoints P1 (x1,y1,z1) and P2 
(x2,y2,z2). The plane that contains these points and the origin 
(0,0,0) has the vector equation

  P . (P1 x P2) = 0

In other words,

  x(y1*z2-z1*y2) + y(z1*x2-x1*z2) + z(x1*y2-y1*x2) = 0

Likewise for segment 2 with endpoints P3 (x3,y3,z3) and P4 (x4,y4,z4):

  x(y3*z4-z3*y4) + y(z3*x4-x3*z4) + z(x3*y4-y3*x4) = 0

I'll define the coefficients in the equations above so I don't have 
to type so much:

  A = y1*z2-z1*y2
  B = z1*x2-x1*z2
  C = x1*y2-y1*x2
  D = y3*z4-z3*y4
  E = z3*x4-x3*z4
  F = x3*y4-y3*x4

Then we have

  Ax + By + Cz = 0
  Dx + Ey + Fz = 0

When we solve these equations simultaneously, we can get a pair of 
equations, expressing x and y in terms of z. 

      BF-CE
  x = ----- z
      AE-BD

      AF-CD
  y = ----- z
      BD-AE

The intersection of this line with the sphere of radius R has z such 
that the distance from the origin is R:

  x^2 + y^2 + z^2 = R^2

  (BF-CE)^2       (AF-CD)^2
  --------- z^2 + --------- z^2 + z^2 = R^2
  (AE-BD)^2       (BD-AE)^2

                (BF-CE)^2   (AF-CD)^2
  z = R / sqrt( --------- + --------- + 1 )
                (AE-BD)^2   (BD-AE)^2

From this you can find x and y using the equations above.

I think I'll leave it at this for now. As I said, there is more to do 
in order to check whether the point we've found lies between the 
endpoints of each line segment. But first, is this the kind of thing 
you're looking for?

- Doctor Rick, The Math Forum
  http://mathforum.org/dr.math/ 

Date: 02/11/2003 at 03:36:53
From: Russ
Subject: Spherical geometry.

That is just what I was after. Many thanks. Just one last point. What 
would I expect when working it through, if the two line segments did 
not intersect?

Thanks again.

Date: 02/11/2003 at 08:24:36
From: Doctor Rick
Subject: Re: Spherical geometry.

Hi, Russ.

You're going to get a solution in any case, unless the two line 
segments are on the same great circle (that is, they are in the same 
plane passing through the center of the sphere). In that case the 
denominators in the equations for x and y will be zero.

The main issue is that my formulas find the point of intersection of 
the LINES containing the line segments, and I haven't provided a way 
to determine whether it lies within each segment. There are probably 
several ways this might be done; here is the first that comes to 
mind. We know that the vector P (x,y,z) is in the same plane with P1 
(x1,y1,z1) and P2 (x2,y2,z2). We could take cross products P1xP, PxP2, 
and P1xP2. (We already got P1xP2 in the course of finding the 
intersection.) These cross products will all be collinear, that is, 
each vector will be a scalar multiple of each of the others. If those 
scalar multiples are all positive, P lies on the segment P1P2. 
Likewise for segment P3P4.

- Doctor Rick, The Math Forum
  http://mathforum.org/dr.math/ 

Date: 02/11/2003 at 08:32:47
From: Russ
Subject: Thank you (Spherical geometry.)

Thanks for all your help. That has helped me out a lot and I should be 
on the right track now.

Cheers,
Russ