1. ## Bypassing a sphere

I really need some help. I'm trying to write a computer program that when given a line segment (two points, xyz) and a sphere (a point and a distance R) will, assuming that the segment's end point and start point are outside the sphere, output a series of points that if were connected would reach the original line segment's end point without intersecting any part of the sphere.

But I have no idea where to begin at all! I should have listened more in college! Someone, please help! :P

Edit: By the way, we're assuming the line intersects the sphere twice.

2. Originally Posted by spiramirabilis
I really need some help. I'm trying to write a computer program that when given a line segment (two points, xyz) and a sphere (a point and a distance R) will, assuming that the segment's end point and start point are outside the sphere, output a series of points that if were connected would reach the original line segment's end point without intersecting any part of the sphere.

But I have no idea where to begin at all! I should have listened more in college! Someone, please help! :P

Edit: By the way, we're assuming the line intersects the sphere twice.
You would need to be more specific: there are many paths that bypass the sphere...

- The "easiest" possibility would be a 5-segments path that avoids any sphere of radius $\displaystyle R$ (assuming like you that the sphere intersects the line twice). This path would form a rectangle with the initial segment: take two symmetric pieces of length $\displaystyle R$ to extend the initial segment in both directions, then two parallel segments of length $\displaystyle 2R$ , orthogonal to the first line (in any direction), and finally a long segment to close the rectangle.
- The most "economic" way would be a two-segments path: only one additional point. There is still plenty of choice: tangent to the sphere or not,...
- The "shortest" way would be a path crawling around the sphere using several segments (it must be specified how many).
- ...

What is it that you have in mind?

3. I was thinking the most economical way, which would add one more point. I thought about it last night and came up with this idea which is probably wrong:

I can easily calculate the 2 points of intersection with the sphere to form a line segment. I can find the mid point (X) of the this new segment and using the center point of the sphere as the beginning point and the midpoint X create a new line. Then I could extend this new line outside the sphere.

I'm not sure this would work in all situations though. How far past the sphere should I extend the line is something I was also wondering about.

4. Originally Posted by spiramirabilis
I was thinking the most economical way, which would add one more point. I thought about it last night and came up with this idea which is probably wrong:

I can easily calculate the 2 points of intersection with the sphere to form a line segment. I can find the mid point (X) of the this new segment and using the center point of the sphere as the beginning point and the midpoint X create a new line. Then I could extend this new line outside the sphere.

I'm not sure this would work in all situations though. How far past the sphere should I extend the line is something I was also wondering about.
Your idea would work, but it is not very simple to find how far the line should extend, because this line is not a very natural one for the problem.

I will explain how to find the path that bypasses the sphere using two line segments tangent to the sphere, in the shortest configuration. If you need the segments not to touch the sphere, you'll have to slightly move the point (more about it later...).

Let $\displaystyle A$ and $\displaystyle B$ be the endpoints of the segment, and $\displaystyle O$ be the center of the sphere, of radius $\displaystyle R$.

a) Tangent line from $\displaystyle A$.
- If $\displaystyle O\notin[A,B]$, define $\displaystyle \vec{i}=\frac{\overrightarrow{OA}}{OA}$, then $\displaystyle \vec{z}=\overrightarrow{AB}-\left(\overrightarrow{AB} \cdot \vec{i}\right)\vec{i}$ (there is a dot product here) and $\displaystyle \vec{j}=\frac{\vec{z}}{\|\vec{z}\|}$.
Then $\displaystyle (\vec{i},\vec{j})$ is an orthonormal basis of the plane $\displaystyle (OAB)$.

- If $\displaystyle O\in[A,B]$ (i.e. if $\displaystyle \vec{z}=\vec{0}$), define $\displaystyle \vec{i}$ in the same way, and let $\displaystyle \vec{j}$ be any unit vector orthogonal to $\displaystyle \vec{i}$. For instance, with $\displaystyle \vec{i}=(x,y,z)$, let $\displaystyle \vec{j}=\frac{1}{x^2+y^2}(y,-x,0)$ if the denominator is non-zero, and $\displaystyle \vec{j}=(1,0,0)$ else.

In the plane $\displaystyle (O,\vec{i},\vec{j})$, there are two lines going through $\displaystyle A$ and tangent to the sphere. They touch the sphere at points $\displaystyle U$ and $\displaystyle U'$. Define now $\displaystyle c=1-\left(\frac{R}{OA}\right)^2$, and $\displaystyle \vec{u}=c \overrightarrow{AO} + R\sqrt{c}\,\vec{j}$. Then (using Pythagoras theorem and other geometrical stuff) we have $\displaystyle U=A+\vec{u}$. (To get $\displaystyle U'$, it would suffice to put a minus instead of the plus in the definition of $\displaystyle \vec{u}$. But if there are two intersections, $\displaystyle U$ is the point that will provide the shortest path.)

b) Tangent line from B.
The same procedure can be held by replacing $\displaystyle A$ by $\displaystyle B$ in the above formulas (redefine $\displaystyle \vec{i},\vec{j},\vec{u},U$), and you get $\displaystyle \vec{v}$ and $\displaystyle V$.

c) Intersection of the tangent lines.
After solving a linear system, the intersection point is seen to be: $\displaystyle P=A+\lambda\vec{u}$, where $\displaystyle \lambda=\frac{x_v(y_B-y_A)-y_v(x_B-x_A)}{x_v y_u-x_u y_v}$.
If the denominator is zero, replace $\displaystyle \lambda$ by the same quantity with $\displaystyle z$ instead of $\displaystyle x$, or instead of $\displaystyle y$.

--
To sum up: using these formulas, compute $\displaystyle \vec{j}$ (using $\displaystyle \vec{i}$ and $\displaystyle \vec{z}$), then $\displaystyle \vec{u}$ (using $\displaystyle c$), do the same for $\displaystyle B$, and finally compute $\displaystyle \lambda$ and $\displaystyle P=A+\lambda\vec{u}$. Using $\displaystyle P$, the bypassing path $\displaystyle ([AP],[PB])$ touches the sphere in two points. If you prefer that the path avoids the sphere, just add some small amount to the $\displaystyle \vec{j}$-component of $\displaystyle \vec{u}$ and $\displaystyle \vec{v}$: $\displaystyle \vec{u}=c \overrightarrow{AO} + (R\sqrt{c}+\varepsilon)\,\vec{j}$ for any small $\displaystyle \varepsilon>0$.

I hope there is no mistake, and that this answers your problem.