2
$\begingroup$

This problem is bugging for quite some time now, and I actually need to program the solution in my game.

I have one point on a radius 1 sphere, and a rotation matrix. When I rotate the point with the matrix, I get another point in the sphere. I know the rotation won't give me a point to far away from the first, so now I have two close points to each other in a sphere, the original $P_1$ and the rotated $P_2$. Since they are close (i.e. they are not on opposite sides of the sphere), there is a unique smallest radius 1 arc segment from $P_1$ to $P_2$. I need a fast way to compute if this arc segment either intersects or is contained in a given circle, also on the sphere. The circle is given by a point on the sphere that I call "center", and a arc radius (in radians). Notice that this "center" is not the euclidean center, for it is also in the sphere.

Poor drawing

How to do it?

What about on higher dimension? If $P_1$ and $P_2$ are on the surface of a 3-sphere, and I need to know if the small arc between $P_1$ and $P_2$ either is contained or intersects with a likewise defined 2-sphere on the 3-sphere, how to do it?

$\endgroup$
5
  • $\begingroup$ Hi, I'm not sure that I understood your question.You have points on the sphere, not opposites, and you consider the smallest arc segment from $P_1$ and $P_2$ (a geodesic, is it?), denoted by $\alpha$. So, You would like to know if $\alpha$ intersects or is contained in a circle with center on sphere and radius equal to $l(\alpha)$ (length of $\alpha$). Is it? $\endgroup$
    – Irddo
    Sep 10, 2015 at 5:04
  • $\begingroup$ No, the circle has some other given radius. And this radius is an arc, through the surface of the sphere. So, for instance, if the center of the circle is the north pole, and its radius is 90°, so the circle is the whole northern hemisphere, and its perimeter is the equator. $\endgroup$
    – lvella
    Sep 10, 2015 at 5:07
  • $\begingroup$ So, my english is very bad, I don't understood yet. Can you make a picture? $\endgroup$
    – Irddo
    Sep 10, 2015 at 5:10
  • $\begingroup$ It turned out bigger than I wanted... HUEHUEBR? $\endgroup$
    – lvella
    Sep 10, 2015 at 5:24
  • $\begingroup$ SUAHSUASH, yes, BR! $\endgroup$
    – Irddo
    Sep 10, 2015 at 5:39

3 Answers 3

2
$\begingroup$

A guideline for the solution:

Let's take the problem to lower dimensions following these steps:

  1. Construct a spherical coordinate system where $P_1$ and $P_2$ are in a plane $P$ such that $\phi=\phi_\circ$ with $\phi_\circ$ a constant. (For simplicity, you may pick $P_1$ to be the x-axis, $\phi=0$ and then finding $\theta$ for $P_2$ should be trivial)
  2. Represent $c$ in the new coordinate system and using $r$, you should be able to find the intersection points of $C(c,r)$ with the plane $\phi=\phi_\circ$. (This can be done by first finding $\phi$ coordinate of $c$, then comparing it with $r$ .. you will need to do some solid geometry analysis to come-up with the intersection location in $\phi=\phi_\circ$ plane if there is any).
  3. If there exist intersection points, your problem is a 1D problem and you can directly compare the $\theta$ coordinate of $P_1$, $P_2$ and the intersection points.
$\endgroup$
1
$\begingroup$

The figure below is a schematic of the problem. All points and curves shown in this figure lie on the sphere, but I have "flattened" the diagram into a plane, drawing great circles as straight lines.

enter image description here

Points $C$, $P_1$, and $P_2$ are as in the question, $M$ is the closest point to $C$ on the great circle through $P_1$ and $P_2$, and $A$ is one of the points where that great circle intersects the small circle around $C$. The angle $\theta$ is the angle of rotation, which is also the angle measure of the great-circle arc from $P_1$ to $P_2$. The distance from $C$ to $A$ is $\rho$, which is a measure of the "radius" of the circle; if $r$ is the radius of the circle in its own plane then $r = \sin\rho$, so you can easily calculate $\rho$, and if you must do multiple calculations with the same small circle you can re-use the value of $\rho$ each time. The angular measures of arcs $CM$, $AM$, and $P_1M$ are $\alpha$, $\beta$, and $\gamma$, respectively.

I will abuse the notation a bit and use the names of the points as the names of vectors from the center of the sphere to each point. So $P_1 \times P_2$ is a vector perpendicular to the vectors $P_1$ and $P_2$, and therefore perpendicular to the plane of the great circle in which points $P_1$ and $P_2$ lie. Let

$$v = \frac{P_1 \times P_2}{\|P_1 \times P_2\|}.$$

Then $v$ is a unit vector perpendicular to the plane of the great circle in which points $P_1$ and $P_2$ lie, and $C \cdot v = \sin\alpha.$ If $\alpha > \rho$ then the arc from $P_1$ to $P_2$ is entirely outside the small circle; otherwise you can use formulas for spherical right triangles to determine $\beta$ from $\alpha$ and $\rho$ and to determine $\gamma$ from $\alpha$ and the angular measure of the arc from $C$ to $P_1$. If you know that the rotation takes $P_2$ "toward" the small circle then you can test whether $\beta + \theta \geq \gamma$.

Alternatively, let $$u = \frac{C \times v}{\|C \times v\|},$$ so $u$ is a vector perpendicular to the plane of the great circle through $C$ and $M$. Let

\begin{align} h_0 & = A \cdot u \\ h_1 & = P_1 \cdot u \\ h_2 & = P_2 \cdot u \end{align}

If you have already determined that $P_1$ and $P_2$ are both close enough to $C$ (anything less than $\frac\pi4$ arc distance from $C$ is "close enough"), then if $h_0$ and $h_1$ have opposite sign, the arc $P_1P_2$ passes through $M$ and therefore at least part of the arc is inside the small circle. If either $|h_1| \leq |h_0|$ or $|h_2| \leq |h_0|$ then either $P_1$ or $P_2$ is inside the circle. In any other case, $P_1$ and $P_2$ are both outside the circle on the "same side", and the arc $P_1P_2$ is entirely outside the small circle.

Note that if you apply the same rotation matrix repeatedly to each new point, and you use the same small circle each time, points $C$, $A$, and $M$ are the same in each calculation and you can compute $u$ and $h_0$ once and use them repeatedly. You can also re-use $h_2$ once as the value of $h_1$ for the next calculation; or you might get clever and use $\arcsin(h_1)$, $\theta$, and $\beta$ to determine how many times you can repeat the rotation before you intersect the small circle, and after that you just need to keep count of how many rotations remain before intersection occurs.


Another approach is to project the figures from the sphere to a plane or hyperplane. There are actually several approaches here depending on which projection you use. I have had some success solving problems very much like this with a stereographic projection onto a plane tangent to the sphere at $P_1$. The stereographic projection has the nice property that circles are mapped to circles, but finding the center of the projection of the circle was somewhat complicated. (It is not at the projected image of $C$.)

Let's try a gnomonic projection onto a plane tangent to the sphere at $C$. A gnomonic projection maps great circles to straight lines. The image of the small circle is a circle whose center is $C$ (in the same plane). If the radius of the original small circle in its own plane is $r$, that plane is at a distance $\sqrt{1-r^2}$ from the center, so the radius of the image of the circle is $r/\sqrt{1-r^2}$. The images of $P_1$ and $P_2$ are respectively

$$ P_1' = \frac{P_1}{P_1\cdot C} \quad\text{and}\quad P_2' = \frac{P_2}{P_2\cdot C}.$$

The vector $u = P_2' - P_1'$ gives you the direction of the line onto which $P_1$ and $P_2$ are projected, and you can eliminate the component of $P_1' - C$ in the direction of $u$ in order to obtain the vector $v = M' - C$. Then you can compute

\begin{align} h_0 & = \|A' - M'\| = \sqrt{\frac{r^2}{1-r^2} - \|v\|^2} \\ h_1 & = \frac{(P_1' - C) \cdot u}{\|u\|} \\ h_2 & = \frac{(P_2' - C) \cdot u}{\|u\|} \end{align}

Again, you can use the signs and magnitudes of $h_0$, $h_1$, and $h_2$ to determine whether the arc from $P_1$ to $P_2$ lies at least partly within the small circle. I believe that all these calculations work the same for a three-sphere under a gnomonic projection onto the hyperplane tangent to the three-sphere at $C$.

$\endgroup$
3
  • $\begingroup$ I know this answers the first question, and this is the best answer so far, but, for the second part, in $R^4$ there is no cross product... $\endgroup$
    – lvella
    Sep 10, 2015 at 16:03
  • $\begingroup$ A lot of things change when you add a dimension. There is an entire plane perpendicular to the great-circle arc from $P_1$ to $P_2$, for example. You could use other methods to find an orthonormal basis of that plane, but there are likely to be other difficulties after that. There are other approaches to the problem that may transfer better to the three-sphere; I'll try to add something to the answer later. $\endgroup$
    – David K
    Sep 10, 2015 at 19:34
  • $\begingroup$ I've added a new method that I think extends more easily to the extra dimension. $\endgroup$
    – David K
    Sep 11, 2015 at 0:41
0
$\begingroup$

Parcial answer:

Denote by $\alpha$ the arc segment from $P_1$ and $P_2$. We have that if $\alpha \subset C(c,r)$, circle of center $c$ and radius $r$, then $r=1$ because the smallest arc segments on the spheres are contain in big-circles (circle with radius equal to 1). So if $r\neq 1$, then $C(c,r)$ not contain $\alpha.$

$\endgroup$
1
  • $\begingroup$ By the arc being contained in a circle, I meant in any place of its internal area. What I called a "circle" is an area on the surface of the sphere, and it also has curvature following the sphere. I meant this circle to be on a non-euclidean spherical space. $\endgroup$
    – lvella
    Sep 10, 2015 at 6:00

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .