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

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

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

Алгоритм

1) Проверим отрезки на то что они лежат в одной плоскости, если лежат перейдем к плоскости и разберем случаи, иначе перейдем к шагу 2.

2) Построим из концов отрезков тетраэдр.

3) Проверим центр сферы на принадлежность тетраэдру. Если принадлежит то отрезки не пересекаются, иначе перейдем к шагу 4.

4) Подставим координаты точек в соотношение написанное выше и сравним результат с [math]0[/math]. Если хотя бы для одной точки результат [math]\gt 0[/math] то отрезки пересекаются, иначе нет.

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

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

Плоскость, образованная центром сферы и точками A и B. Необходимо определить взаимное расположение плоскости и точки С

[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]CD[/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]

Тетраэдр полученный из концов отрезков. В данном случае грань ADC отсекает его от центра сферы.

Проверим лежат ли точки в одной плоскости, если лежат проведем эту плоскость, пересечение сферы и этой плоскости это окружность, на которой лежат 4 точки(начала и концы отрезков). Далее необходимо выбрать из 2ух отрезков любой, посчитать поворот его концов относительно центра окружности, а дальше сравнить поворот оставшихся точек, если хотя бы одна точка из второго отрезка попадает в диапазон значений между концами выбранного нами отрезка, то прямые пересекаются, иначе необходимо взять другой отрезок и проверить это же утверждение для него(так как 1ый взятый нами отрезок мог содержаться во втором), в случае если оба случая не дали положительного результата - отрезки не пересекаются.

Иначе рассмотрим следующий алгоритм.

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

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

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

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

Для того, чтобы проверить грань необходимо посчитать определитель матрицы поворота для четырех точек.

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

Где [math]A[/math], [math]B[/math], [math]C[/math] - точки задающие плоскость, [math]P[/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].