I have two arcs on a sphere that are defined as pair of points: $(\theta_0, \varphi_0)$, $(\theta_1, \varphi_1)$. I need to find a point where they intersect, or some indication if they don't. What is important is that they are arcs, not circles, so it is important to find intersection that is on the arcs specifically (not on projected circles). Arcs are meant to be shortest possible arcs. I am failing to find any specific equations on the internet. Thanks!
Asked
Active
Viewed 9,581 times
10
-
- Find the two intersection points of the corresponding great circles. 2. Keep the ones which lie inside both arcs.
– May 26 '13 at 12:10 -
@RahulNarain yes, right, but how? I am honestly not very good at spherical geometry, since I am solving purely practical task. – Andrey May 26 '13 at 17:29
4 Answers
3
You can find a javascript implementation here:
http://www.movable-type.co.uk/scripts/latlong.html
and a good explanation here:
user2290821
- 46
2
As far as I can tell to verify that two arcs intersect on the same sphere they must have an angular range that has at least shares one particular value of phi and theta, for instance if one arc covers (30,30 ) to (60, 60) and the other covers (0, 0) to (0, 60) they wouldn't intersect even if theta agrees. Basically the condition is that the intervals for both sets of phi and theta have nonzero set theoretic intersection at the same time, that is the ranges for phi must have at least one value in common at the same time as both ranges for theta have at least one value in common.
Triatticus
- 1,232
-
Well... while this is useful observation, I am trying to solve very specific task of finding the point itself. – Andrey May 26 '13 at 17:26
-
Maybe I can be of more help if I had just a bit more info on the problem, are you trying to make computer code that can find the intersection of two arcs or a quick manual way to find the intersection – Triatticus May 26 '13 at 19:23
-
Eventually I need to write code, I hope to find some formula that produces intersection point out of 4 points (2 arcs). – Andrey May 26 '13 at 21:56
-
I see, sorry I have nothing to offer on that, perhaps add computer/ programming to the tags and see if someone can help find an efficient algorithm – Triatticus May 30 '13 at 06:10
-
@Dam, you are missing the point. It is pure mathematical question, once it is solved I can proceed with code. – Andrey May 30 '13 at 08:46
-
Well as I said, in a purely mathematical way, if you have the starting and ending angles of the arcs then you will already know if they intersect based on the ranges given, I have written down the conditions it doesn't really get simpler than that. Two points in spherical geometry intersect if they have the same angular coordinate, similar to how cartesian coordinates would have equal x/y values. – Triatticus May 30 '13 at 14:36
-
Perhaps the only other thing I can mention is that you need to remember how spherical geometry is defined? – Triatticus May 30 '13 at 14:39
-
I am struggling to understand the cartesian analogy. I have say (0, 0) (5, 5) and (-1, 1) (3, -1). Nothing is equal but they do intersect. – Andrey May 30 '13 at 17:01
-
I must ask one thing first before I elaborate further, are these arcs necessarily part of great circles on the sphere in question? If so the relationship between $\theta$ and $\phi$ is given by $$ \cot \theta = a \cos( \phi - \phi_0) $$ where a and $\phi_0$ are constants to be determined by the end points. This was retreived on a pdf about circular geodesics http://www.damtp.cam.ac.uk/user/reh10/lectures/nst-mmii-handout2.pdf – Triatticus May 30 '13 at 21:32
1
Assuming points on a unit sphere...
Convert your four points to XYZ space. Let's call the points A, B, C, and D, with AB being one arc and CD the other. Let's call the origin O. A plane through ABO can be defined by the normal vector cross product AxB, let's call it E. Similarly, a plane through CDO can be defined by the normal vector cross product CxD, let's call it F.
Now, any vector normal to E will be on ABO, and any vector normal to F will be on CDO. The vector cross product ExF will be on both planes. Let's normalize that and call it G. This is one possible solution. The other possible solution is on the opposite side of the sphere, which is -G.
Use the dot product to find the angle between AB, the angle between GA, and the angle between GB. If the angles GA and GB are both less than the angle AB, then G must be between them.
Do the same for CD. If G is between both AB and CD, then that is an intersection
Now do that again for -G to see if that is an intersection.
In the off chance that ABCD all lie on the same great circle line, the cross product G will have a magnitude of 0. In this case, you can use the same dot product and angle comparison trick to see if A or B lie along the arc CD and vice versa.
user3258730
- 19
0
Here's an outline of how you could do it (though I suspect there are more efficient methods).
- For each arc, obtain the great circle it is on. If you don't already have this, you can define it with its (Cartesian) normal vector, i.e. cross product of the two points on the arc you have.
- With these two great circles, find the point of intersection. One fairly inelegant way of doing this is:
- take the cross product (again) of the two great circle normals $\mathbf{n_3}=\mathbf{n_1}\times \mathbf{n_2}$ - and use these 3 vectors to define 3 planes (all through the origin).
- Some caution is needed here in case the two arcs you were provided with originally were on the same great circle.
- Define $\mathbf{p_0}$ as the intersection of these three planes (calculate e.g. with matrix inversion or LU factorisation), now define $\mathbf{p_x}$ as this intersection of the line $\mathbf{p_0} + \lambda \mathbf{n}_3$ with the unit sphere (this involves solving a quadratic)
- Finally, you need to check whether this point $\mathbf{p_x}$ (which lies on both great circles) is inside the arcs you specify. A way (again there may be better ways) to do this is:
- (For each arc) parameterize the great circle in terms of a single parameter $\alpha$, defined as the angle from the $\mathbf{u_0}= (\theta_0,\phi_0)$ end.
- $\alpha_0 = 0$,
- $\alpha_1=acos(\mathbf{v_1}.\mathbf{u_0})$
- $\alpha_{p_x}=acos(\mathbf{p_x}.\mathbf{u_0})$
- Check if $\alpha_{p_x} < \alpha_{1}$, if so, repeat for other arc
You've probably lost interest by now, but I'm posting this as a placeholder so someone can point out a better way.
caspar
- 1