判断顶点是否为凸点。帮助理解。

Question

我正在学习以下代码。

boolean convex(double x1, double y1, double x2, double y2, 
       double x3, double y3)
{
if (area(x1, y1, x2, y2, x3, y3) < 0)
    return true;
else
    return false;
}


/* area:  determines area of triangle formed by three points
 */
double area(double x1, double y1, double x2, double y2,
    double x3, double y3)
{
double areaSum = 0;

areaSum += x1 * (y3 - y2);
areaSum += x2 * (y1 - y3);
areaSum += x3 * (y2 - y1);

/* for actual area, we need to multiple areaSum * 0.5, but we are
     * only interested in the sign of the area (+/-)
     */

return areaSum;
}

我不理解负面积的概念。难道面积不应该始终为正吗？也许我在这里缺乏一些术语的理解。我试图联系原作家，但这段代码已经有8年了，我没有办法联系到原作家。这种确定给定顶点x2y2是否凸的方法似乎很流行。我真的很想理解它。任何可以指导或帮助我理解这段代码的参考资料都将非常感激。

源代码: http://cgm.cs.mcgill.ca/~godfried/teaching/cg-projects/97/Ian/applets/BruteForceEarCut.java

- BlueBug

Answer 1

该算法使用一种非常简单的公式，可以计算三角形面积的两倍。

这个公式有两个优点：

- 它不需要任何除法。 - 如果点按逆时针顺序，则返回负面积。

在代码示例中，实际面积值并不重要，只需要结果的符号。

该公式也可用于检查三个点是否共线。

您可以在此网站上找到有关此公式的更多信息：http://www.mathopenref.com/coordtrianglearea.html

- obourgain

Answer 2

这个算法基本上使用了两个向量的点积并对结果进行解释。这是用于查找凸包的礼品包装算法的核心。

由于a·b也等于|a|*|b|*cos(theta)，因此如果结果为正，theta的cos必须为正，因此为凸形。根据维基百科关于叉积的文章...

因为叉积的大小通过其参数之间夹角的正弦来测量，所以可以将叉积视为“垂直性”的度量方式，就像点积是“平行”的衡量方式一样。给定两个单位向量，它们的叉积在两者垂直时具有大小为1，在两者平行时具有大小为零。反之，两个单位向量的点积则相反。

在我看来，原始编码人员使用“面积”略微误导了。

- Andrew White

---

非常感谢您的指导。我做了一些研究，但仍然难以理解您所说的“两个向量的叉积并解释结果”的含义。我知道在三维空间中，如果向量a和b按逆时针顺序排列，则得到的向量会弹出；如果相反，则会射向另一侧。因此，我假设通过对两个向量进行叉积运算，我也可以在二维空间中确定方向？在这种情况下，我可以将其用于在“gift wrapping algorithm”中找到“最左边”或“最右边”的下一个点。 - BlueBug

但我从未见过2D叉积，也没有处理过它在2D中的结果？你能在2D中进行叉积运算吗？如果可以，我应该如何解释它们？（这是一个有点冗长的问题，可能需要更多细节，但如果你能在这里帮助我一下，我会非常感激并送上我的灵魂和亲吻） - BlueBug

@BlueBug：数学出错了，我把点乘和叉乘搞混了。 - Andrew White

Answer 3

你知道积分是如何工作的吧？一种思考积分的方法是考虑被积曲线下的面积。对于严格为正的函数，这个定义很好用，但当函数在某些点变成负数时，就会出现问题，因为这时你需要取绝对值，对吗？

实际上，并不总是这样，有时保留曲线的负数部分会非常有用。回想一下之前所说的：曲线下方的面积。那么，所有负无穷到我们函数之间的空间都被包括了进来。显然，这是荒谬的，对吧？更好的思考方式是将其视为曲线下面积和x轴下面积的差异。这样，当函数为正时，曲线获得的面积更多，而当函数为负时，曲线获得的面积少于x轴。

同样的事情也适用于不是严格函数的平面图形。为了真正确定这一点，我们必须定义我们的边沿在绕着图形旋转时的“方向”。我们可以定义所有右侧区域内的面积都属于该区域，而所有左侧区域的面积则属于外部（或者我们也可以反过来定义，但我将使用第一种方式）。

因此，我们的图形包括从该点到直接在其右侧的平面的无限远处边缘的所有区域。顺时针封闭的区域实际上将其传统内部包含了两次。逆时针封闭的区域根本不包含其传统内部。那么，面积就是我们的区域和整个平面之间的差异。

如果你理解什么是凹凸的话，这个概念模型对于凹凸的应用就相当简单了。如果给出的三角形从平面中切掉了一块区域，那么它就是凹的；如果你给它添加了额外的区域，那么它就是凸的。这正是我们确定面积的方法，因此正面积对应凸形状，负面积对应凹形状。

你也可以用这个概念模型做其他奇怪的事情。例如，通过改变边缘方向来将区域“翻转”。

如果这有点难以理解，请原谅，但这是我理解负面积的实际方式。

- AJMansfield

---

是的，难以理解，但我会再读一遍！太好了。谢谢。 - BlueBug

很好的解释，让我信服 ^^ - Moberg