问确定是否可以使用单个三角形扇子绘制二维多边形

EN

如果从锚点到每个顶点的角度在同一方向上移动，则可以将多边形绘制为三角形扇形。测试这一点的最简单方法是检查连续顶点的叉积的点积。

它看起来像这样：

vector lastCross = cross_product( vector(vertex[0] - center), vector(vertex[numVerts - 1] - center) );

canBeFan = true;
for (n = 1; canBeFan && n < numVerts; ++n) {
    vector testCross = cross_product( vector(vertex[n] - center), vector(vertex[n - 1] - center) );
    if (0.0 >= dot_product(testCross, lastCross) ) {
        canBeFan = false;
    }
}

您要查找的属性是"star-shaped“。星形多边形是通过具有一个点来定义的，从该点可以看到整个多边形。

要测试多边形是否为星形，可以构造整个多边形可见的区域。该区域将是一个凸集，因此您可以在O(log(n))中将其与半平面相交。

这意味着您可以与边形成的半平面相交，并检查生成的可见性区域在O(n log n)中是否是非空的。

看起来所有潜在的中心点都需要位于多边形每条边的内侧。因此，把所有的边都当作半空格，并确定它们的交集是否为空。

正如@jpalecek所说，这个术语是星形的。如果您的多边形是星形的，那么将有一个凸多边形(原始多边形的内部)，其点可以查看原始多边形的所有边--相反，如果不存在这样的子多边形，则原始多边形不是星形的，并且您不能用三角形扇子绘制它。

确定此子多边形基本上是convex hull问题的dual应用程序；它可以在O(n log n)中计算。