В данном случае задача разбивается на две

16 17 18 19 20 21 22

1) нахождение пересечения луча с плоскостью, в которой лежит многоугольник.

2) Проверка принадлежности точки пересечения многоугольнику.

1)Пусть плоскость задана общим уравнением

Ax+By+Cz+D=0

Где N=(A, B,C) -нормальный вектор плоскости.

Заменяя в уравнении плоскости величины x,y и z их выражениями (*),

Получаем линейное уравнение относительно t:

Разрешая которое, находим, что

Если a=Al+Bm+Cn обращается в нуль, a=Al+Bm+Cn=0, то луч параллелен плоскости, и, следовательно, не пересекает ее.

В случае t*<0 луч не пересекает плоскости.

Если t*>0 то координаты точки пересечения вычисляются по формулам

2) Решение основано на нахождении пересечения с треугольником. Если у многоугольника n вершин (n>3), то он будет представляться как набор из n-2 треугольников. N — вектор нормали к плоскости, в которой лежит рассматриваемый многоугольник. Точка Р задается как

(4)

Точка Р будет внутри треугольника

если а>=0, b>=0, и a + b<= 1

В равенство (4) состоит из 3 равенств:

(5)

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

В качестве направления проектирования рекомендуется брать ту ось, которой соответствует наибольшая координата у нормали.

Пусть

Пусть (u,v) координаты вектора в плоскости, на которую был спроектирован многоугольник. Тогда векторы будут иметь следующие координаты:

Система (5) упроститься до системы:

Решением являются:

2*) Выпуклый n-угольник однозначно задается набором своих вершин

Будем считать, что вершины многоугольника занумерованы так, что соседние по номеру вершины примыкают к одной стороне. Обозначим через (x*,y*,z*) точку пересечения заданного луча с плоскостью Ax+By+Cz+D=0, в которой лежит рассматриваемый многоугольник.

Вследствие того, что нормальный вектор N=(A, B,C) плоскости, несущей заданный многоугольник, отличен от нуля, этот n-угольник можно взаимно однозначно спроектировать на n-угольник, лежащий в одной из координатных плоскостей. В качестве направления проектирования рекомендуется брать ту ось, которой соответствует наибольшая координата у нормали.

Предположим для определенности, что C =Max(A, B,C).

Тогда в качестве такой плоскости можно взять координатную плоскость xy, а в качестве направления проектирования – ось аппликат (ось Z).

Легко видеть, что координаты вершин n-угольника, получающегося в результате такого проектирования, будут иметь вид

Координаты точки, получающейся в результате проектирования на плоскость xy точки (x*,y*,z*) будут соответственно (x*, y*).

Ясно, что если точка (x*, y*) лежит вне (внутри) n-угольника, получившегося на плоскости xy,то исходная точка (x*,y*,z*) будет внешней (внутренней) по отношению к исходному n-угольнику.

Для определения положения точки (x*, y*) относительно выпуклого n-угольника, лежащего на плоскости xy, можно поступить, например, следующим образом.

Передвинем n-угольник