Пересечение отрезков на сфере

Постановка задачи

Дано два отрезка на сфере. Необходимо узнать пересекаются ли они, и если пересекаются, то где.

Проверка на пересечение

Сопоставим каждой точке на сфере луч, исходящий из центра сфера и проходящий через эту точку. Тогда лучи сопоставляемые двум точкам будут образовывать плоскость. Необходимо научиться проверять лежит данная точка в плоскости образованной двумя другими точками. Итак у нас есть точки [math]a[/math] и [math]b[/math] образующие плоскость, также есть точка [math]c[/math]. Необходимо узнать расположение этой точки относительно плоскости. Вспомним о повороте. Необходимо посчитать определитель матрицы поворота и сравнить его знак с нулем.

[math] A = [/math] [math] \left (\begin{array}{ccc} a_x & a_y & a_z \\ b_x & b_y & b_z \\ c_x & c_y & c_z \end{array}\right) [/math]

Рассмотрим три случая:

• [math]sign(|A|) \gt 0[/math] тогда точка [math]c[/math] лежит над плоскостью, образованной точками [math]a[/math] и [math]b[/math].
• [math]sign(|A|) \lt 0[/math] тогда точка [math]c[/math] лежит под плоскостью, образованной точками [math]a[/math] и [math]b[/math].
• [math]sign(|A|) = 0[/math] тогда точка [math]c[/math] лежит на плоскости, образованной точками [math]a[/math] и [math]b[/math].

Лемма (1):

Если два отрезка на сфере пересекаются, то все их четыре точки находятся в одной полусфере.

Доказательство:

[math]\triangleright[/math]

Пусть отрезки: [math]AB[/math] и [math]BC[/math]. Точка пересечения [math]X[/math]. Центр сферы - начало координат [math]O[/math]. Найдем нужную полусферу. Это будет полусфера от окружности точек [math]A[/math] и [math]C[/math], ориентированная так, чтобы содержать [math]X[/math].Проведем плоскость [math]OAX[/math], пересечем ее со сферой. На полученной окружности возьмем точку [math]A'[/math] - диаметрально противоположную точке [math]A[/math]. Точка [math]B[/math] находится в нашей полусфере, потому что она находится "ближе" точки [math]A'[/math]. Если бы она была дальше точки [math]A'[/math], то мы бы провели отрезок [math]AB[/math] через другую половину сферы, и соответственно, точка [math]X[/math] была бы не в выбранной полусфери. Далее повторим рассуждения для точек [math]C[/math] и [math]D[/math].

[math]\triangleleft[/math]

Соединив концы отрезков, получим тетрэдр.

Утверждение:

Если центр шара принадлежит тетраэдру, образованному концами отрезков, то отрезки лежат в разных полушариях.

Для того чтобы определить принадлежит ли центр шара тетраэдру, необходимо найти грань тетраэдра, которая будет отсекать тетрэдр от центра шара, если такой грани не существует, то центра шара принадлежит тетраэдру, следовательно отрезки находятся в разных полушариях, следовательно они не пересекаются. Для того, чтобы найти такую грань, необходимо для каждой пары точек проверить поворот противоположной точки и центра окружности, и если знаки определителей матриц поворота оказались разные, то такая грань найдена.

Рассмотрим отрезки [math]AB[/math] и [math]CD[/math]. Проверим их на пересечение. Для этого возьмем отрезок [math]AB[/math] и посчитаем для него следующее соотношение

[math]V=\vec A \times \vec B \times (\vec B - \vec A)\vec{AP} = (\vec A \times \vec B \times \vec B - \vec B \times \vec A \times \vec A)\vec{AP}[/math]

где вместо [math]P[/math] необходимо поочередно подставить [math]C[/math] и [math]D[/math]. И если хотя бы для одной точки [math]V \gt 0[/math], то отрезки пересекаются и точка пересечения лежит на [math]AB[/math].