java - 确定顶点是否是凸的。帮助理解

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

Answer 1

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

这个公式有两个优点:

• 不需要任何除法
• 如果该点按逆时针顺序返回一个负区域。

在代码示例中，区域的实际值无关紧要，只需要结果的符号。

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

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