Есть: Полигон в 3D, известны координаты всех вершин в 3D, заведомо плоский и выпуклый многоугольник; и отрезок, координаты концов тоже известны.

Надо: Быстро определить, пересекает ли отрезок этот полигон (именно отрезок, а не прямая, и именно полигон, а не плоскость).

Идеи: По трем вершинам полигона сочиняем уравнение плоскости и находим точку пересечения плоскости и прямой, содержащей отрезок (выразив координаты точки пересечений функциями от нужных геометрических параметров). Отлавливаем divbyzero если они параллельны. Подставляем концы отрезка в уравнение плоскости: если значения имеют разные знаки, то отрезок пересекает плоскость. Осталось определить, он пересекает ее в полигоне или нет.
Вот я и завис... Уж без того куча делений будет, а тут еще тригонометрией попахивает.

Наверняка все в корне можно сделать не так. Может как-нибудь побыстрее можно? Хотя бы для частного случая, когда полигон - треугольник...

ну для начала желательно найти точку пересечения отрезка с плоскостью
потом надо определить, внутри ли многоугольника находится точка:
1. записываем вершины многоугольника по порядку (т.е. соседние вершины в списке идут друг за другом)
2. идем по ребрам многоугольника и смотрим справа исследуемая точка или слева
3. если точка всегда была с одной стороны, значит, она внутри, иначе - снаружи
---
как определить справа точка или слева:
ребро - AB, точка - O
считаем векторное произведение ABxAO
его знак указывает на то, справа или слева точка от ребра
если при проходе по всем ребрам знак не изменился, значит, точка O внутри

А можно еще свести задачу к двумерной. Т.е. выполнить преобразования координат так, чтобы плоскость многоугольника совпала с одной из координатных плоскостей. Исключая из расчетов одну из координат можно существенно ускорить алгоритм.

2 yurgen20
Хорошая идея Так побыстрее будет. Но при преобразовании координат все равно потребуется вычислять нормаль и умножать матрицы 3x3 на (3x(n+2)), где n-количество вершин у полигона...
Зато легко определится, пересекает ли отрезок эту плоскость, а точка пересечения найдется из подобия треугольников

2 maxim1000
Нормальный вариант, особенно когда одна координата нулевая, векторное произведение считается просто

Наверно ничего оптимальнее не придумать... или придумать?..[s][/s]

Цитата

считаем векторное произведение ABxAO его знак указывает на то, справа или слева точка от ребра если при проходе по всем ребрам знак не изменился, значит, точка O внутри

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

Цитата

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

Зачем скалярное произведение?
Векторные произведения будут параллельны нормали и достаточно следить знак любой проекции векторного произведения на x, y или z , которая у нормали не нулевая.

Цитата

Векторные произведения будут параллельны нормали и достаточно следить знак любой проекции векторного произведения на x, y или z , которая у нормали не нулевая.

да, не заметил...
просто скалярное произведение - первое, что пришло в голову