4

I am given two geodesics on a sphere, each designated by longitude and latitude of the endpoints. How can I calculate whether they intersect each other? I.e. whether the great circles intersect within the segments?

Jim Newton
  • 509
  • If I knew the parametric equation p(t) which maps [0-1] onto each segment on the great circle, with p(0)= point1, p(1)=point2, then I could solve this. However the parametric equation is not p(t) = p1t + p2(1-t), that's not on the great circle, right? – Jim Newton Dec 02 '19 at 21:20
  • e.g. let $p_1$ and $p_2$ be two points on the same latitude. Then $p(t) = p_1\cdot t + p_2\cdot (1-t)$ traces a path on the latitude line, not on the great circle. – Jim Newton Dec 03 '19 at 07:17
  • isn't this the same as https://math.stackexchange.com/questions/402799/intersection-of-two-arcs-on-sphere – Jim Newton Dec 04 '19 at 09:09
  • re: https://math.stackexchange.com/questions/402799/intersection-of-two-arcs-on-sphere, I'm also interested in this version of the question, independently, in case someone can describe a way to test whether or not an intersection exists that's faster than computing the exact point at which the intersection occurs – Joe Amenta Dec 04 '19 at 19:27
  • Can I rotate a sphere so that two given points are mapped to the equator?

    If I could rotate a sphere so that two given points end up on the equator (anywhere I don't care) then I could detect wither the other two points now straddle the equator by looking at there latitudes-- one should be positive, and the other negative. Then I could rotate the sphere so that the other two points end up on the equator and make the same test with the first two points.

     – Jim Newton Dec 08 '19 at 14:26
  • Hmm, has this StackOverflow answer solved it for us? https://stackoverflow.com/a/26669130/1083771 – Joe Amenta Dec 10 '19 at 21:44
  • I don't believe the proposed solution posted in https://stackoverflow.com/questions/26668041/intersections-between-geodesics-shortest-distance-paths-on-the-surface-of-a-sp/26669130#26669130 The post is assuming Euclidian coordinates. That's a false assumption, in my opinion. I posted a counter-example. – Jim Newton Dec 11 '19 at 10:59
  • I may have a much easier and elegant way of solving this depending on the answer to question 3472337 If I come up with a good solution to that question, crossing geodesics solution here based on it. – Jim Newton Dec 11 '19 at 12:46

2 Answers2

1

Let $p_1,p_2$ are endpoints of one of the geodesics, and let's assume that $p_1,p_2$ are not antipodal points (because if they are then the geodesic is not unique). Let $q_1,q_2$ be endpoints of the other, also not antipodal. And I'm going to ignore latitude/longitide coordinates, and just use coordinates in 3-dimensions, so for example $$p_1 = (p_{1x},p_{1y},p_{1z}) \quad\text{such that} \quad p_{1x}^2 + p_{1y}^2 + p_{1z}^2 = 1 $$ The formula $p(t) = t \cdot p_1 + (1-t) \cdot p_2$, $0 \le t \le 1$, does not even lie on the sphere, it cuts across a chord on the inside of the sphere. However, that is the kernel of a useful idea.

The formula $$p(s,t) = s \cdot p_1 + t \cdot p_2, \quad s,t \in [0,\infty) $$ parameterises an "angle" in 3-space whose intersection with the sphere is equal to the geodesic connecting $p_1$ and $p_2$. Similarly for the formula $$q(s,t) = s \cdot q_1 + t \cdot q_2, \quad s,t \in [0,\infty) $$ In both cases, multiplication by $s,t$ means scalar multiplication in 3-d coordinates, and addition means vector addition.

The two spherical geodesics intersect in at least a point on sphere if and only if the two angles intersect in at least a ray in 3-space. So now your problem is reduced to some linear algebra calculations, as follows. Form the equation $p(s,t)=q(s',t')$, which gives three equations in the four unknowns $s',t'$. Solve for $s,t,s',t'$. Check whether there exists a solution with $s>0$ or $t > 0$, and with $s'$ or $t' > 0$ (which is equivalent to saying that the two angles intersect in at least a ray).

Lee Mosher
  • 120,280
  • Do I understand correctly? ...That $p(s,t) = s\cdot p_1 + t\cdot p_2$ defines a plain through the sphere center and the two points p_1, and p2, thus the plain contains the geodesic? Analogously for $q(s,t)$. If the planes are different and intersect then they intersect in a line. – Jim Newton Dec 04 '19 at 08:47
  • Sorry I don't understand what a spherical angle is. You state "The two spherical angles intersect in the sphere if and only if the two angles intersect." What does it mean for angles to intersect? Can you rephrase this sentence? Is a spherical angle two intersecting lines on the surface of the sphere? Or is it a cone whose vertex is the sphere center? – Jim Newton Dec 04 '19 at 08:50
  • I mistyped, that should have been "spherical geodesics", not spherical angle. I rewrote that paragraph a little. – Lee Mosher Dec 04 '19 at 13:15
  • For your first comment, the formula $p(s,t) = s \cdot p_1 + t \cdot p_2$ does indeed define a plane if $s,t$ vary independently over the entire the real number line $\mathbb R$. But what I've defined as an angle requires $s,t$ are restricted to vary independently over the positive half line $[0,\infty)$. – Lee Mosher Dec 04 '19 at 13:17
  • I'm content that https://stackoverflow.com/questions/26668041/ solves my problem. I've rewritten the code in Scala (the language I'm using for my project) and it seems to pass all my tests. – Jim Newton Dec 19 '19 at 13:14
0

another issue seems to solve this problem. It's pretty easy to translate the Python code shown in that issue into your programming language of choice.

Jim Newton
  • 509