11

起初，我认为这个问题相当于确定一个多边形是否是凸多边形，但似乎一个三角形扇形仍然可以绘制一个非凸多边形。 考虑这个形状，一个非凸多边形。可以很容易地想象一些中心点区域允许用三角形扇形绘制这个多边形（尽管会有其他中心点不会）。给定一个固定的中心点，我希望能够确定定义多边形的 2d 点集是否允许用单个三角形扇形绘制它。

似乎关键是确保从中心点到任何顶点的线没有“妨碍”，这意味着顶点的其他边缘线。但是，重要的是要使其在计算上尽可能便宜，而且我不确定是否有一个很好的数学捷径可以做到这一点。

最终，我将让多边形的顶点移动，并且我需要确定允许顶点移动的“边界”，因为其余部分是固定的（也许稍后甚至允许直接的同时反应移动2 个邻居），以保持多边形能够在单个三角形扇形中绘制。但这就是未来，希望对整个多边形的测试可以分解为计算的子集，以在假设已经是凸多边形的情况下测试单个顶点的移动边界。

4

3 回答 3

13

您要找的物业是“星形”。星形多边形是由一个点定义的，从该点可以看到整个多边形。

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

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

于 2012-04-25T17:25:30.067 回答
2

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

它看起来像这样：

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;
    }
}
于 2012-04-25T17:35:15.067 回答
1

看起来所有潜在的中心点都需要位于多边形每个边缘的内侧。因此，将所有边视为半空间，并确定它们的交点是否为空。

正如@jpalecek 所说，这个术语是星形的。如果您的多边形是星形的，则将有一个凸多边形（在原始多边形的内部），其点可以查看原始多边形的所有边缘-相反，如果不存在这样的子多边形，则原始多边形不是星形的，你不能用三角扇画它。

确定这个子多边形基本上是凸包问题的双重应用；它可以在 中计算。O(n log n)

于 2012-04-25T17:37:47.490 回答