@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, то точка лежит внутри треугольника
, тут в этом алгоритме для нахождение площади использовалось формула Герона, ну такой алгоритм оказался неэффективным , так вот: какой алгоритм лучше всего использовать для определения нахождения точки за границей треугольника пространства?
  • Вопрос задан
  • 141 просмотр
Решения вопроса 1
wataru
@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)|
Ответ написан
Пригласить эксперта
Ответы на вопрос 1
gbg
@gbg
Любые ответы на любые вопросы
Алгоритм был нормальный (потому что найти трилинейные, либо барицентрические (как в вашем случае)) координаты точки и сравнить с единицей (или с площадью) - это и есть математически корректный алгоритм проверки.

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

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы