Как определить, находится ли точка в 2D треугольнике?
Существует ли простой способ определить, ли точка в треугольнике? Это 2D, не 3D.
3 ответа
В целом простейший (и весьма оптимальный) алгоритм проверяется на какой стороне полуплоскости, создаваемой краями.
Вот некоторое высокое качество информации в этом Тема на Геймедеве , включая проблемы с производительностью.
И вот какой-то код для начала:
float sign (fPoint p1, fPoint p2, fPoint p3)
{
return (p1.x - p3.x) * (p2.y - p3.y) - (p2.x - p3.x) * (p1.y - p3.y);
}
bool PointInTriangle (fPoint pt, fPoint v1, fPoint v2, fPoint v3)
{
float d1, d2, d3;
bool has_neg, has_pos;
d1 = sign(pt, v1, v2);
d2 = sign(pt, v2, v3);
d3 = sign(pt, v3, v1);
has_neg = (d1 < 0) || (d2 < 0) || (d3 < 0);
has_pos = (d1 > 0) || (d2 > 0) || (d3 > 0);
return !(has_neg && has_pos);
}
Решите следующую систему уравнения:
p = p0 + (p1 - p0) * s + (p2 - p0) * t
Точка P находится внутри треугольника, если 0 <= S <= 1 и 0 <= T <= 1 и S + T <= 1 .
s , T и 1 - S - T называются барицентрическими координатами точки p .
Простой способ:
Найти векторы, соединяющие указать на каждый из трех треугольников вершины и сумма углов между эти векторы. Если сумма Углы 2 * PI, то точка внутри треугольника.
Две хорошие сайты, которые объясняют альтернативы: