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
Search the Dr. Math Library:
Ask Dr. MathTM
© 1994- The Math Forum at NCTM. All rights reserved.