c++ - 确定是否可以用单个三角形扇形绘制二维多边形

Question

一开始我以为这道题等同于判断一个多边形是不是凸多边形，但是貌似非凸多边形用一个三角扇还是可以画出来的。 Consider this shape , 一个非凸多边形。人们可以很容易地想象出一些中心点区域可以让这个多边形用三角形扇形绘制(尽管会有其他中心点不允许)。给定一个固定的中心点，我希望能够确定定义多边形的 2d 点集是否允许使用单个三角形扇形绘制它。

似乎关键是确保没有任何东西“妨碍”从中心点到任何顶点绘制的线，这意味着顶点的其他边缘线。但是，重要的是要尽可能降低计算成本，而且我不确定是否有很好的数学捷径来做到这一点。

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

Answer 1

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

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

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