Добро пожаловать, гость
:: алгоритмы  и методы :: :: олимпиадные задачи :: :: связь :: :: о сайте :: :: форум ::

Форум работает в режиме архива, только для чтения и поиска.
Архив 2004 Архив 2007 Архив 2013

 
 
Опции темы Поиск в этой теме Опции просмотра
  #1  
Старый 19.03.2010, 23:01
dominator

 
Сообщений: n/a

точка внутри пирамиды
Добрый день. Подскажите, пожалуйста, самый простой способ проверить находится ли точка строго внутри треугольной пирамиды. Координаты точки и вершин пирамиды целые числа.

Я знаю, что здесь можно пойти двумя путями:
1) найти уравнения каждой плоскости, подставить в них координаты заданной точки и проверить совпадают ли по знаку значения A*x + B*y + C*z + D. Однако здесь, видимо, есть нюанс, который я не знаю как обойти: значения A,B,C,D зависят от порядка точек, на которые опирается плоскость. Иными словами, нормаль может быть направлена как в одну сторону, так и в другую. Наверное, надо как-то установить порядок этих точек перед вычислением A,B,C,D или каким-то образом преобразовать полученные уравнения плоскостей.
2) провести луч из заданной точки и посчитать количество раз, которое он пересекает грани пирамиды. Этот способ мне кажется сложнее, потому что нужно еще учитывать случаи, когда луч попадает в вершину или в ребро пирамиды.
  #2  
Старый 20.03.2010, 00:51
гость

 
Сообщений: n/a

детерминанта матрицы 3x3 в которой строки - вектора A, B, C, по абсолютному значению равен объему пирамиды (а по научному говоря - симплекса) OABC. (O - начало координат.)

Как определить что X лежит внутри ABCD? Очень просто - проверить что V(XABC) + V(XABD) + V(XBCD) = V(ABCD), где V - объем. Причем если хоть одно слагаемое слева нулевое, то точка лежит на границе.
  #3  
Старый 20.03.2010, 00:59
гость

 
Сообщений: n/a

хочу заметить, что способ выше не оптимальный - вместо четырех детерминантов можно на самом деле обойтись вычислением и одного, - но зато он предельно прост для понимая и дурако-устойчив )в знаках точно не запутаешься.)
  #4  
Старый 20.03.2010, 12:30
MBo MBo вне форума
Местный

Отправить личное сообщение для MBo Посмотреть профиль Найти все сообщения от MBo
 
Регистрация: 21.09.2006
Адрес: Новосибирск
Сообщений: 1,374

Взять одну из вершин пирамиды (A) за базовую точку, и разложить вектор AP по базисным векторам AB, AC, AD. Каждый коэффициент должен быть в пределах 0..1, и их сумма тоже.
 


Опции темы Поиск в этой теме
Поиск в этой теме:

Расширенный поиск
Опции просмотра


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
нахождение координат точек внутри угла Геп Вычислительная геометрия 1 15.05.2009 07:37
Аппроксимация внутри призмы midi Математические алгоритмы 6 07.01.2009 17:08
Точка внутри тетраэдра Aram Вычислительная геометрия 2 03.03.2008 14:53
Разместить один полигон внутри другого Максим Вычислительная геометрия 3 28.11.2007 19:04
точка в окужности Олег Павлыш Вычислительная геометрия 5 28.11.2006 16:10