Привет!

Возник вопрос как определить (быстро) лежит ли определенная точка (пространства) в
произвольной треугольной пирамиде.

Есть идея, что это можно сделать определив уравнение плоскости граней пирамиды.
Но это -,скажем так, небыстрое и неточное решение;
особенно если рассматривать вырожденный случай-точка на грани пирамиды.

Мне кажется, что должно существовать решение, подобное тому,
как определяется принадлежность точки треугольнику на плоскости (через смешанное векторное произведение).

Если кто-либо знает точный и быстрый алгоритм, поделитесь пожалуйста.

Спасибо!

Здравствуйте, Dima_Ru, Вы писали:

D_R>Если кто-либо знает точный и быстрый алгоритм, поделитесь пожалуйста.
1. Считаешь уравнения для каждой плоскости пирамиды, причем нормаль каждой плоскости должна быть ориентирована внутри пирамиды (или все нормали должны быть ориентированы во вне пирамиды). Это делается без проблем — векторы нормали легко получаются с помощью векторного произведения.
2. Подставить точку в каждое получившееся уравнение плоскости.
3. Если знаки всех уравнений совпадут (ноль тоже считать совпадающим), то точка лежит внутри пирамиды.

Этот метод, кстати, подходит для любого выпуклого многогранника.

Здравствуйте, Cyberax, Вы писали:

C>Здравствуйте, Dima_Ru, Вы писали:

D_R>>Если кто-либо знает точный и быстрый алгоритм, поделитесь пожалуйста.
C>1. Считаешь уравнения для каждой плоскости пирамиды, причем нормаль каждой плоскости должна быть ориентирована внутри пирамиды (или все нормали должны быть ориентированы во вне пирамиды). Это делается без проблем — векторы нормали легко получаются с помощью векторного произведения.

Произвидение то леко найти, только еще надо учитывать, что можно получить
вектор "наружу" пирамиды.

C>2. Подставить точку в каждое получившееся уравнение плоскости.
C>3. Если знаки всех уравнений совпадут (ноль тоже считать совпадающим), то точка лежит внутри пирамиды.

C>Этот метод, кстати, подходит для любого выпуклого многогранника.

Привет! Спасибо за ответ.
Я просто думаю, что есть более быстрые решения %)

Здравствуйте, Dima_Ru, Вы писали:

D_R>Привет!

D_R>Возник вопрос как определить (быстро) лежит ли определенная точка (пространства) в
D_R>произвольной треугольной пирамиде.

D_R>Есть идея, что это можно сделать определив уравнение плоскости граней пирамиды.
D_R>Но это -,скажем так, небыстрое и неточное решение;
D_R>особенно если рассматривать вырожденный случай-точка на грани пирамиды.

D_R>Мне кажется, что должно существовать решение, подобное тому,
D_R>как определяется принадлежность точки треугольнику на плоскости (через смешанное векторное произведение).


Можно для каждой плоскости вычислить по два смешанных векторных произведения: одно для искомой точки, а другое — для оставшейся вершины. Если знаки совпадут, то точка лежит с нужной стороны плоскости.

Здравствуйте, Dima_Ru, Вы писали:

D_R>Привет!

D_R>Возник вопрос как определить (быстро) лежит ли определенная точка (пространства) в
D_R>произвольной треугольной пирамиде.

Одна из вершин — начало, векторы к остальным трем вершинам — базисные векторы непрямоугольной системы координат.
Разложим вектор начало-точка по трем базисным. Точка внутри, если каждая из координат больше нуля и их сумма в пределах 0..1.

Здравствуйте, Dima_Ru, Вы писали:

D_R>Привет!

D_R>Возник вопрос как определить (быстро) лежит ли определенная точка (пространства) в
D_R>произвольной треугольной пирамиде.

Идеологически "правильный" подход заключается в том, что мы условие внутри-снаружи выражаем в терминах некоторых базовых предикатов.
В данном случае всё можно выразить через предикат orient3d.

orient3d(a,b,c,d) > 0, если вектора ab,ac,ad ориентированы правильно.
orient3d(a,b,c,d) < 0, если вектора ab,ac,ad ориентированы неправильно.
orient3d(a,b,c,d) = 0, если a,b,c,d лежат в одной плоскости

Тогда тест "внутри" может быть выражен так:

orient3d(v0,v1,v2,v3) и orient3d(v0,v1,v2,x) имеют разные знаки => снаружи
orient3d(v1,v2,v3,v0) и orient3d(v1,v2,v3,x) имеют разные знаки => снаружи
orient3d(v2,v3,v0,v1) и orient3d(v2,v3,v0,x) имеют разные знаки => снаружи
orient3d(v3,v0,v1,v2) и orient3d(v3,v0,v1,x) имеют разные знаки => снаружи
Иначе внутри
В зависимости от того, как классифицировать точки на границе, стоит внести коррективы в этот алгоритм.

Заметим, что знак orient3d(v0,v1,v2,v3)=знак orient3d(v1,v2,v3,v0)=знак orient3d(v2,v3,v0,v1)=знак orient3d(v3,v0,v1,v2)

Проблемы:
выраженный наивным образом, предикат orient3d(v0,v1,v2,v3)=смешанное произведение(v1-v0,v2-v0,v3-v0).
В 99% это работает более или менее нормально, и подходит для решаемой задачи.
Однако нужно быть готовым к тому, что временами этот тест будет давать неправильный результат (точка реально над плоскостью, а тест даёт под...)
Это связано с ошибками вычислений с плавающей точкой. Если необходимо, чтобы тест работал правильно, придётся копать в сторону адаптивных предикатов, точных вычислений,...
См. например отсюда The CGAL Philosophy.

Всем большое спасибо за ответы!
Подход/идея ясна.

-Дима