3

我正在研究以下代码。

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

4

3 回答 3

4

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

这个公式有两个优点：

  • 它不需要任何划分
  • 如果该点按逆时针顺序返回，则返回负区域。

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

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

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

于 2013-06-18T16:14:19.173 回答
3

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

如果结果是正的，因为a dot b也等于|a|*|b|*cos(theta)then，所以 theta 的 cos 必须是正的，因此是凸的。根据关于交叉产品的维基文章...

因为叉积的大小是其参数之间角度的正弦，所以叉积可以被认为是“垂直度”的量度，就像点积是“平行度”的量度一样。给定两个单位向量，如果两者垂直，它们的叉积的大小为 1，如果两者平行，则它们的叉积大小为零。两个单位向量的点积正好相反。

在我看来，“区域”的使用对部分原始编码器有点误导。

于 2013-06-18T16:05:28.903 回答
2

你知道积分是如何工作的，对吧？考虑积分的一种方法是根据积分曲线下的面积。对于严格为正的函数，这个定义很有效，但是当函数在某个时候变为负时，就会出现问题，因为你必须取绝对值，对吧？

实际上，情况并非总是如此，在某些情况下，使曲线为负值可能非常有用。回想一下前面所说的：曲线下的面积。负无穷和我们的函数之间的所有空间。显然，这很荒谬，对吧？更好的理解方式是曲线下面积与 x 轴下面积之差。这样，当函数为正时，我们的曲线获得更多面积，而当它为负时，它获得的面积小于 x 轴。

同样的事情也适用于不是严格函数的平面图形。为了真正确定这一点，我们必须定义我们的边缘在围绕图形行进时的方向。我们可以定义它，使曲线右侧的所有区域都在区域内，而左侧的所有区域都在区域外（或者我们可以反过来定义它，但我将使用第一种方式）。

所以我们的数字包括从那里到我们右边的平面无限远边缘的所有区域。顺时针包围的区域实际上包括了它们的传统内部两次。逆时针包围的区域根本不包括它们的传统内部。那么，面积就是我们所在区域与整个平面之间的差异。

如果您了解凹面或凸面的实际含义，则将其应用于凹面是相当简单的。如果从平面上切出一个区域，则给定的三角形是凹的，如果要向其添加额外的区域，则它是凸的。这与我们在确定我们的区域时所做的完全相同，因此正区域对应于凸形，负区域对应于凹形。

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

如果这有点难以理解，我很抱歉，但这是我理解负面区域的实际方式。

于 2013-06-18T16:47:31.460 回答