Пересечение отрезков на сфере — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Проверка на пересечение)
м (rollbackEdits.php mass rollback)
 
(не показано 15 промежуточных версий 4 участников)
Строка 11: Строка 11:
 
3) Проверим центр сферы на принадлежность тетраэдру. Если принадлежит то отрезки не пересекаются, иначе перейдем к шагу 4.
 
3) Проверим центр сферы на принадлежность тетраэдру. Если принадлежит то отрезки не пересекаются, иначе перейдем к шагу 4.
  
4) Подставим координаты точек в соотношение написанное выше и сравним результат с <tex>0</tex>. Если хотя бы для одной точки результат <tex>> 0</tex> то отрезки пересекаются, иначе нет.
+
4) Проверим с помощью поворота отрезки на пересечение.
  
== Проверка на пересечение ==
+
== Проверка на пересечение двух отрезков на сфере==
  
  
Сопоставим каждой точке на сфере луч, исходящий из центра сфера и проходящий через эту точку. Тогда лучи сопоставляемые двум точкам будут образовывать плоскость. Необходимо научиться проверять лежит данная точка в плоскости образованной двумя другими точками. Итак у нас есть точки <tex>a</tex> и <tex>b</tex> образующие плоскость, также есть точка <tex>c</tex>. Необходимо узнать расположение этой точки относительно плоскости. Вспомним о повороте. Необходимо посчитать определитель матрицы поворота и сравнить его знак с нулем.
+
Сопоставим каждой точке на сфере луч, исходящий из центра сферы(точка <tex>O</tex>) и проходящий через эту точку. Тогда лучи сопоставляемые двум точкам будут образовывать плоскость. Необходимо проверять лежит ли точка <tex>C</tex> в плоскости образованной лучами точек <tex>A</tex> и <tex>B</tex>. Вспомним о повороте. Необходимо посчитать определитель матрицы поворота и сравнить его знак с нулем.
  
[[Файл:Sphere1.png|right|1000|thumb|Плоскость, образованная центром сферы и точками A и B. Необходимо определить взаимное расположение плоскости и точки С]]
+
[[Файл:Sphere_1.png|right|1000|thumb|Плоскость, образованная центром сферы и точками <tex>A</tex> и <tex>B</tex>. Необходимо определить взаимное расположение плоскости и точки С]]
  
  
Строка 33: Строка 33:
 
Рассмотрим три случая:
 
Рассмотрим три случая:
  
* <tex>sign(|A|) > 0</tex> тогда точка <tex>c</tex> лежит над плоскостью, образованной точками <tex>a</tex> и <tex>b</tex>.
+
* <tex>sign(|A|) > 0</tex> тогда точка <tex>c</tex> лежит над плоскостью, образованной точками <tex>O</tex>, <tex>A</tex> и <tex>B</tex>.
* <tex>sign(|A|) < 0</tex> тогда точка <tex>c</tex> лежит под плоскостью, образованной точками <tex>a</tex> и <tex>b</tex>.
+
* <tex>sign(|A|) < 0</tex> тогда точка <tex>c</tex> лежит под плоскостью, образованной точками <tex>O</tex>, <tex>A</tex> и <tex>B</tex>.
* <tex>sign(|A|) = 0</tex> тогда точка <tex>c</tex> лежит на плоскости, образованной точками <tex>a</tex> и <tex>b</tex>.
+
* <tex>sign(|A|) = 0</tex> тогда точка <tex>c</tex> лежит на плоскости, образованной точками <tex>O</tex>, <tex>A</tex> и <tex>B</tex>.
  
  
Строка 42: Строка 42:
 
|statement=Если два отрезка на сфере пересекаются, то все их четыре точки находятся в одной полусфере.
 
|statement=Если два отрезка на сфере пересекаются, то все их четыре точки находятся в одной полусфере.
 
|proof=
 
|proof=
[[Файл:Sphere4.png|right|1000|thumb|Плоскость ОАХ]]
+
[[Файл:Sphere_4.png|right|1000|thumb|Плоскость ОАХ]]
Пусть отрезки: <tex>AB</tex> и <tex>CD</tex>. Точка пересечения <tex>X</tex>. Центр сферы - начало координат <tex>O</tex>.
+
Пусть есть отрезки: <tex>AB</tex> и <tex>CD</tex>. Точка пересечения <tex>X</tex>. Центр сферы - начало координат <tex>O</tex>.
Найдем нужную полусферу. Это будет полусфера от окружности точек <tex>A</tex> и <tex>C</tex>, ориентированная так, чтобы содержать <tex>X</tex>.Проведем плоскость <tex>OAX</tex>, пересечем ее со сферой. На полученной окружности возьмем точку <tex>A'</tex> - диаметрально противоположную точке <tex>A</tex>. Точка <tex>B</tex> находится в нашей полусфере, потому что она находится "ближе" точки <tex>A'</tex>. Если бы она была дальше точки <tex>A'</tex>, то мы бы провели отрезок <tex>AB</tex> через другую половину сферы, и соответственно, точка <tex>X</tex> была бы не в выбранной полусфери.
+
Найдем нужную полусферу. Это будет полусфера от плоскости, образованной точками <tex>O</tex>, <tex>A</tex> и <tex>C</tex>, ориентированная так, чтобы содержать <tex>X</tex>.Проведем плоскость <tex>OAX</tex>, пересечем ее со сферой. На полученной окружности возьмем точку <tex>A'</tex> - диаметрально противоположную точке <tex>A</tex>. Точка <tex>B</tex> находится в нашей полусфере, потому что она находится "ближе" точки <tex>A'</tex>. Если бы она была дальше точки <tex>A'</tex>, то мы бы провели отрезок <tex>AB</tex> через другую половину сферы, и соответственно, точка <tex>X</tex> была бы не в выбранной полусфере.
 
Далее повторим рассуждения для точек <tex>C</tex> и <tex>D</tex>.
 
Далее повторим рассуждения для точек <tex>C</tex> и <tex>D</tex>.
 
}}
 
}}
Строка 55: Строка 55:
 
Иначе, если точки не лежат в одной плоскости, рассмотрим следующий алгоритм.
 
Иначе, если точки не лежат в одной плоскости, рассмотрим следующий алгоритм.
  
Соединив концы отрезков, получим тетрэдр.
+
Соединим концы отрезков, результатом будет тетрэдр.
  
 
{{Утверждение
 
{{Утверждение
Строка 64: Строка 64:
 
Для того, чтобы найти такую грань, необходимо для каждой грани тетраэдра проверить поворот противоположной точки и центра окружности, и если знаки определителей матриц поворота оказались разные, то такая грань найдена.
 
Для того, чтобы найти такую грань, необходимо для каждой грани тетраэдра проверить поворот противоположной точки и центра окружности, и если знаки определителей матриц поворота оказались разные, то такая грань найдена.
  
Для того, чтобы проверить грань необходимо посчитать определитель матрицы поворота для четырех точек.
+
Для того, чтобы проверить существование грани, отсекающей тетраэдр <tex>PABC</tex> от центра сферы, необходимо посчитать определитель матрицы поворота для четырех точек.
  
  

Текущая версия на 19:31, 4 сентября 2022

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

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

Алгоритм

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