[Неочевидные алгоритмы очевидных вещей] Алгоритм 2. Принадлежность точки треугольнику в пространстве

[Imp5]

Автор, вот тест который показывает странное поведение этого алгоритма: codepad.org/a6bQS54E
Легко заметить, что все точки треугольника лежат в районе точки (-1, -1, 0), а тестируемая точка в (1, 1, 0)
Объясни пожалуйста, почему функция проверки иногда возвращает 1?

Да сколько уже можно публиковать безграмотный код?

[skobeltsyn]

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

[Ocelot]

Код должен быть понятный, а не универсальный

Это гениальная фраза. Буду её использовать, когда спросят, почему мой код иногда ведет себя некорректно.

[hardex]

Вот это поворот

[alexeykuzmin0]

А не проще ли использовать стандартный метод с лучом, исходящим из точки? кода будет втрое меньше

[skobeltsyn]

Чуть ниже коммент=)

[skobeltsyn]

Вы имеете в виду вычисление количества пересечений луча из точки P с треугольником?

[alexeykuzmin0]

Да

[skobeltsyn]

Там есть понятия вектора и т.п., мне кажется, алгоритм с площадями более нагляден. И обычно метод с лучом используется для 3D объектов из нескольких полигонов, а тут именно 2D треугольник. Но в принципе потом можно для N-угольника пост написать, если не заминусуют карму до -30, конечно =)

[alexeykuzmin0]

Метод с лучом очень прост. Причем для определения факта пересечения не нужно искать сами координаты, достаточно сделать проверку, как в комменте ниже

[PavloG]

Все намного проще

// returns true if projected point on triangle plane is inside triangle
inline bool isInsideTriangle(const Math::Vec3f& pt,const Math::Vec3f& v0,const Math::Vec3f& v1,const Math::Vec3f& v2,const Math::Vec3f& normal)
{
	if( CrossProduct(v1-v0,pt-v0).dot(normal)<TRIANGLE_EPSILON )
		return false;
	if( CrossProduct(pt-v0,v2-v0).dot(normal)<TRIANGLE_EPSILON )
		return false;
	if( CrossProduct(v1-pt,v2-pt).dot(normal)<TRIANGLE_EPSILON )
		return false;
	return true;
}

[PavloG]

Хотелось бы еще добавить, что для больших треугольников при использовании формулы Герона будут проявятся очень большие числа которые будут ломать точность float, что будет приводить в ошибкам.

[akalenuk]

Не надо трогать Герона. Можно взять сумму векторов векторных произведений от точки к вершинам (главное не потерять порядок) и сравнить квадрат ее нормы с квадратом нормы векторного произведения двух любых сторон. Это те же площади, но без корней и конских формул, а если компилятор позволяет, еще и с мультискалярными операциями на всех векторных вычислениях.

[KvanTTT]

Странно, что автор, который занимается «разработкой высокопроизводительных вычислительных систем моделирования распространения радиоволн (CUDA, C, MPI)» выкладывает такой неэффективный алгоритм с корнями.

Лучше берите пример из stackoverflow.

[Imp5]

codepad.org/1b5rNJDG — А ведь это самый заплюсованный ответ. Кажется, пора писать ещё одну статью про математику с плавающей точкой

[PapaBubaDiop]

Вспоминаем 8-ой класс. Точка (x,y) лежит слева от прямой (A,B,C), если Ax+By+C<0 и наоборот. Треугольник образуется тремя прямыми. Если для всех прямых точка лежит справа, то она внутри треугольника. И никаких площадей, боже сохрани.