Какой алгоритм использовать для определения нахождения точки за границей треугольника пространства?

Question

[vaselekk]

Допустим есть 3 точки: p1(x1,z1,y1), p2(x2,z2,y2), p3(x3,z3,y3), которые образовуют треугольника в пространстве (полигон). И есть точка p(x,y,z), как определить находиться ли эта точка за границами треугольника?
Был алгоритм :

Найти 4 площади: 1площадь отвечает за треугольник непосредственно построенного на вершинах p1, p2, p3, а остальные 3 площади треугольника построенные на вершинах вида: p1, p, p2; p2,p,p3 и т.д, и если сумма таких 3 площадей равняется площади треугольника p1p2p3, то точка лежит внутри треугольника

, тут в этом алгоритме для нахождение площади использовалось формула Герона, ну такой алгоритм оказался неэффективным , так вот: какой алгоритм лучше всего использовать для определения нахождения точки за границей треугольника пространства?

Comments

[Lynn «Кофеман»]

А что такое «за границами треугольника» в трёхмерном пространстве?

Answer 1

[Wataru]

Если точка не на плоскости треугольника, то вам надо переформулировать задачу. Там вообще непонтяно, что значит внутри/снаружи.

Если же оно на плоскости, то введите там систему координат (например, орто-нормируйте вектора p2-p1 и p3-p1). Получите координаты всех точек (p1 можно назначить началом координат).

Потом придется применять формулу для плоскости. Можно воспользоваться векторными произведениями. Произведение пар векторов {p-p1, p2-p1}, {p-p2, p3-p2}, {p-p3, p1-p3} должны все давать одинаковый знак (или все <=0 или все >=0. Равенство 0 чего-то будет означать, что точка на границе).

Или можно посчитать площади, опять же через векторное произведение. |(p2-p1)(p3-p1)| = |(p1-p)(p2-p)+(p2-p)(p3-p)+(p3-p)(p1-p)|

Comments

[vaselekk]

Что значит знак векторного произведения? векторное произведение 2 векторов это всегда координаты:

[Wataru]

vaselekk, Вы пропустили шаг приведения к плоскости.

Когда вы получили 2 ортонормированных вектора на плоскости e1 и e2, то считая скалярные произведения (P-p1) с e1 и e2 вы можете получить координаты точки P на плоскости. Вот уже там векторное произведение - это число.

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

Answer 2

[Армянское Радио]

Алгоритм был нормальный (потому что найти трилинейные, либо барицентрические (как в вашем случае)) координаты точки и сравнить с единицей (или с площадью) - это и есть математически корректный алгоритм проверки.

Только вместо колхоза школьных формул (которые надо оставить в школе) надо пользоваться матрицами и определителями. Весь поиск координат сводится к обращению матрицы 4x4, что делается легко и быстро.