1

将四边形（由四个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);
}

编辑：我问的是如何将单个四边形转换为应由四个点组成的单个三角形条带。

4

2 回答 2

3
  1. 用坐标定位四边形的极值点。顺其自然，循环容器上的迭代器在p哪里p
  2. 检查是否p + 2位于由{p - 1, p, p + 1}. 如果是，则寻找其他坐标的极值（或从min到max，反之亦然）并重复步骤 1。
  3. 通过切断极值点周围的“耳朵”将四边形分成两个三角形： t0 = { p - 1, p, p + 1}和 t1 = { p + 1, p + 2, p - 1 }

无需排序，只需找到极值即可。如果保证您的四边形是凸的（实四边形），则跳过极值搜索并选择任意p。

编辑：根据评论中的建议进行了修改。评论者建议的公式也更容易实现：

  1. 给定一个四边形A, B, C, D的对角线 AC和BD
  2. 如果点B和D位于ACthen的不同边AC可以用来分割四边形
  3. 对和BD点应用相同的推理AC
于 2012-09-03T09:18:21.020 回答
2

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.

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.

于 2012-09-03T08:41:07.093 回答