0

如果在 (x1, y1)、(x2, y2) 和 (x3, y3) 处有一组三个顶点，如何确定由这三个顶点定义的三角形是朝左还是朝右？

目前，我正在使用叉积来确定顶点是否是顺时针方向，并且有了这些知识，我可以在对它们的 y 坐标进行排序时确定三角形是朝左还是朝右。

这很好用，但叉积需要五次减法和两次乘法。

是否有一些更简单、更快的方法来确定我缺少的三角形是否朝左？

4

2 回答 2

2

这将取决于浮点运算的成本visavi 条件语句的成本（加上一半时间清除指令管道的额外成本）。

我的直觉是，您当前的解决方案可能是一个相当不错的解决方案。

于 2014-08-12T08:48:08.967 回答
0

我是这样看的：

  1. 找到具有最小和最大 Y 坐标的 2 个点

    • 如果任意两点具有相同的 Y 坐标
    • 那么你必须选择一个 X 坐标更接近另一个 Y 最小/最大点的

  2. 测试第 3 个点 x 坐标

    • 如果它小于任何其他点，则它朝左
    • 如果它大于任何其他点，则它朝左

三角面

[笔记]

  • 这个实现需要几个if状态
  • 然后通过交叉产品解决这个问题可能会更慢......
  • 即使它的操作较少

如果你的三角形有定义的绕组（总是顺时针或逆时针）

  • 三角形有 A,B,C 点

  • 像这样计算行的正负 dy 的计数：

    int p=0,n=0;
if (B.y-A.y>=0) p++; else n++;
if (C.y-B.y>=0) p++; else n++;
if (A.y-C.y>=0) p++; else n++;

  • 现在为CW

  • if (p<n) left_facing; else right_facing;
  • 对于CCW，它被取消了......
于 2014-08-12T07:55:47.040 回答