转换四到三角形带的最快方法？

问题描述

什么是转换一个四边形（由四个 X，Y 点），以一个三角形带的最快方法是什么？我很清楚的存在一般三角算法，但我需要一个短的很好的优化算法与四边形只涉及。

What is the fastest way of converting a quadrilateral (made up of four x,y points) to a triangle strip? I'm well aware of the general triangulation algorithms that exist, but I need a short, well optimized algorithm that deals with quadrilaterals only.

我目前的算法做到这一点，它适用于最四边形，但仍然得到混淆的一些要点：

My current algorithm does this, which works for most quads but still gets the points mixed up for some:

#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);
}

编辑：我问转换的单四到一个三角形带，应该包括四个点

I'm asking about converting a single quad to a single triangle strip that should consist of four points.

推荐答案

由于四 ABCD 我们可以将其分成 ABC，ACD 或 ABD，DBC 。

Given a quad A B C D we can split it into A B C, A C D or A B D, D B C.

比较 AC的长度和 BD 和使用较短的分裂边缘。换句话说使用 ABC，ACD 如果 C 更短， ABD，DBC 否则。

Compare the length of A-C and B-D and use the shorter for the splitting edge. In other words use A B C, A C D if A-C is shorter and A B D, D B C otherwise.

这篇关于转换四到三角形带的最快方法？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！