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

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-угольник

в плоскости xy так, чтобы точка (x*, y*)попала в начало координат.

В новой координатной системе абсциссы и ординаты вершин n-угольника будут соответственно

Теперь остается выяснить, будет (или не будет) точка (0,0), в которую преобразуется точка (x*, y*),внутренней точкой n-угольника с вершинами

Возможны два случая.

IАбсциссы всех вершин n-угольника – одного знака.

Это означает, что рассматриваемая точка лежит вне n-угольника.

IIЕсть два ребра n-угольника с вершинами

соответственно ( i < j), такие, что

Если

то интересующая нас точка лежит внутри n-угольника.

Это означает, что точка (x* , y* ,z*) лежит внутри исходного n-угольника.

Если же последнее произведение положительно, то точка (x* , y* ,z*)лежит вне исходного n-угольника.