| Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате |
| Форум программистов > Алгоритмы > Полигон и отрезок |
| Автор: Sail 28.6.2004, 20:54 |
| Есть: Полигон в 3D, известны координаты всех вершин в 3D, заведомо плоский и выпуклый многоугольник; и отрезок, координаты концов тоже известны. Надо: Быстро определить, пересекает ли отрезок этот полигон (именно отрезок, а не прямая, и именно полигон, а не плоскость). Идеи: По трем вершинам полигона сочиняем уравнение плоскости и находим точку пересечения плоскости и прямой, содержащей отрезок (выразив координаты точки пересечений функциями от нужных геометрических параметров). Отлавливаем divbyzero если они параллельны. Подставляем концы отрезка в уравнение плоскости: если значения имеют разные знаки, то отрезок пересекает плоскость. Осталось определить, он пересекает ее в полигоне или нет. Вот я и завис... Уж без того куча делений будет, а тут еще тригонометрией попахивает. Наверняка все в корне можно сделать не так. Может как-нибудь побыстрее можно? Хотя бы для частного случая, когда полигон - треугольник... |
| Автор: maxim1000 29.6.2004, 11:07 |
| ну для начала желательно найти точку пересечения отрезка с плоскостью потом надо определить, внутри ли многоугольника находится точка: 1. записываем вершины многоугольника по порядку (т.е. соседние вершины в списке идут друг за другом) 2. идем по ребрам многоугольника и смотрим справа исследуемая точка или слева 3. если точка всегда была с одной стороны, значит, она внутри, иначе - снаружи --- как определить справа точка или слева: ребро - AB, точка - O считаем векторное произведение ABxAO его знак указывает на то, справа или слева точка от ребра если при проходе по всем ребрам знак не изменился, значит, точка O внутри |
| Автор: yurgen20 2.7.2004, 13:40 |
| А можно еще свести задачу к двумерной. Т.е. выполнить преобразования координат так, чтобы плоскость многоугольника совпала с одной из координатных плоскостей. Исключая из расчетов одну из координат можно существенно ускорить алгоритм. |
| Автор: Sail 2.7.2004, 19:09 |
| 2 yurgen20 Хорошая идея  Так побыстрее будет. Но при преобразовании координат все равно потребуется вычислять нормаль и умножать матрицы 3x3 на (3x(n+2)), где n-количество вершин у полигона... Зато легко определится, пересекает ли отрезок эту плоскость, а точка пересечения найдется из подобия треугольников  2 maxim1000 Нормальный вариант, особенно когда одна координата нулевая, векторное произведение считается просто Наверно ничего оптимальнее не придумать... или придумать?..[s][/s] |
| Автор: maxim1000 2.7.2004, 23:30 | ||
ужас какой написал, а никто не заметил  конечно, нужно смотреть не знак векторного произведения , а его скалярного произведения на нормаль... |
| Автор: Sail 3.7.2004, 15:43 | ||
Зачем скалярное произведение? Векторные произведения будут параллельны нормали и достаточно следить знак любой проекции векторного произведения на x, y или z , которая у нормали не нулевая. |
| Автор: maxim1000 3.7.2004, 18:58 | ||
да, не заметил... просто скалярное произведение - первое, что пришло в голову |