Каков самый быстрый способ преобразования четырехугольника (состоящего из четырех точек x,y
) в полосу треугольника? Я хорошо знаком с существующими общими алгоритмами триангуляции, но мне нужен короткий, хорошо оптимизированный алгоритм, работающий только с четырехугольниками.
Мой текущий алгоритм делает это, и он работает для большинства квадроциклов, но для некоторых все еще путает точки:
#define fp(f) bounds.p##f
/* Sort four points in ascending order by their Y values */
point_sort4_y(&fp(1), &fp(2), &fp(3), &fp(4));
/* Bottom two */
if (fminf(-fp(1).x, -fp(2).x) == -fp(2).x)
{
out_quad.p1 = fp(2);
out_quad.p2 = fp(1);
}
else
{
out_quad.p1 = fp(1);
out_quad.p2 = fp(2);
}
/* Top two */
if (fminf(-fp(3).x, -fp(4).x) == -fp(3).x)
{
out_quad.p3 = fp(3);
out_quad.p4 = fp(4);
}
else
{
out_quad.p3 = fp(4);
out_quad.p4 = fp(3);
}
Редактировать: я спрашиваю о преобразовании одного четырехугольника в одну треугольную полосу, которая должна состоять из четырех точек.