В данном случае задача разбивается на две
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-угольника.