确定是否可以使用单个三角形扇形绘制2d多边形

Question

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

看起来关键是要确保从中心点到任何顶点绘制的线条没有"妨碍",这意味着顶点的其他边缘线.但是,重要的是尽可能使计算成本低廉,并且我不确定这样做是否有一个很好的数学捷径.

最终,我将要让多边形的顶点移动,并且我需要确定允许顶点移动的"边界",因为其余的是固定的(并且可能稍后甚至允许直接同时反应移动)还有2个邻居),以保持多边形能够在单个三角形扇形中绘制.但这就是未来,希望对整个多边形的测试可以分解为一个计算子集,以假设已经凸出的多边形来测试单个顶点运动的边界.

Answer 1

您正在寻找的属性是" 星形 ".通过具有整个多边形可见的点来定义星形多边形.

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

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

Answer 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;
    }
}