Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате
Форум программистов > Алгоритмы > Как определить пересекает ли прямая полигон?


Автор: Elfet 28.5.2007, 11:02
Как определить пересекает ли прямая полигон? Если полигон это плоскость заданная тремя вершинами? И если это не плоскость, а мыльная плёнка заданная n-ым количеством вершин?
Заранее спасибо!  smile 

Автор: maxim1000 28.5.2007, 12:55
в случае плоскости - определяем точку пересечения прямой с плоскостью и смотрим, входит ли она в полигон (эта задача уже не раз обсуждалась)
в случае с произвольной поверхностью надо смотреть, что за поверхность, так непонятно...

Автор: Promitheus 28.5.2007, 13:53
А если "мыльная пленка" , то у неё должно быть уранение поверхности, генерирующая эти точки и далее надо смотреть есть ли общие решения у этой поверхности и прямой. Если же поверхность задаётся n полигонами, то задача сводится найти полигон (если таковой имеется), который пересекает прямая. 

Автор: Elfet 28.5.2007, 17:33
Цитата(maxim1000 @  28.5.2007,  13:55 Найти цитируемый пост)
(эта задача уже не раз обсуждалась)

 smile не нахожу smile

Promitheus, не-а уравнение нет, есть твининг smile

Автор: Elfet 28.5.2007, 18:03
Вот что нашёл:
Цитата( Пересечение: Прямая(или отрезок) и плоскость)

Плоскость задана тремя точками, прямая( или отрезок) начальной и конечными точками.

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

Будем обозначать A,B,C - точки плоскости, X,Y - точки прямой(концы отрезка), SP - скалярное произведение, VP - векторное произведение. O - искомое множество точек пересечения

N = VP ( B - A, C - A )
N = N / | N |  - нормаль к плоскости  // в принципе это можно и не делать
V = A - X
// расстояние до плоскости по нормали
d = SP ( N, V )  
W = Y - X
// приближение к плоскости по нормали при прохождении отрезка
e = SP ( N, W ) 

if( e!=0 )
  O = X + W * d/e;          // одна точка
else if( d==0)
  O =X + W * (anything)     // прямая принадлежит плоскости
else
  O = empty;                // прямая параллельна плоскости

Если хочешь быть уверен, что плоскость пересекает не только прямая, но и отрезок, можно проверить условие SP ( X - O, Y - O ) <=0

Но что-то мне не понятно вот тут: 
Цитата

V = A - X
// расстояние до плоскости по нормали
d = SP ( N, V ) 


Добавлено через 4 минуты и 19 секунд
http://algolist.manual.ru/maths/geom/intersect/linefacet3d.php

Автор: maxim1000 28.5.2007, 18:32
Цитата(Elfet @  28.5.2007,  17:33 Найти цитируемый пост)
не нахожу

http://forum.vingrad.ru/topic-40818.html

Powered by Invision Power Board (http://www.invisionboard.com)
© Invision Power Services (http://www.invisionpower.com)