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

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

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

Алгоритм

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

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

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

4) Проверим с помощью поворота отрезки на пересечение.

Проверка на пересечение двух отрезков на сфере

Сопоставим каждой точке на сфере луч, исходящий из центра сферы(точка [math]O[/math]) и проходящий через эту точку. Тогда лучи сопоставляемые двум точкам будут образовывать плоскость. Необходимо проверять лежит ли точка [math]C[/math] в плоскости образованной лучами точек [math]A[/math] и [math]B[/math]. Вспомним о повороте. Необходимо посчитать определитель матрицы поворота и сравнить его знак с нулем.

Плоскость, образованная центром сферы и точками [math]A[/math] и [math]B[/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]O[/math], [math]A[/math] и [math]B[/math].
• [math]sign(|A|) \lt 0[/math] тогда точка [math]c[/math] лежит под плоскостью, образованной точками [math]O[/math], [math]A[/math] и [math]B[/math].
• [math]sign(|A|) = 0[/math] тогда точка [math]c[/math] лежит на плоскости, образованной точками [math]O[/math], [math]A[/math] и [math]B[/math].

Лемма (1):

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

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

[math]\triangleright[/math]

Плоскость ОАХ Пусть есть отрезки: [math]AB[/math] и [math]CD[/math]. Точка пересечения [math]X[/math]. Центр сферы - начало координат [math]O[/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]PABC[/math] от центра сферы, необходимо посчитать определитель матрицы поворота для четырех точек.

[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].