确定一个多边形是否为星形的。

Question

我需要一些提示：

如果存在多边形P内部的点p，使得P边界上的任何其他点（顶点）都可见于p，则多边形P是星形的。

给定一个多边形P，如何确定P是否为星形多边形？

平均时间复杂度应该为O(n)。

我已经思考了一段时间，任何帮助将不胜感激。

- firev2

---

@Dialecticus 如果边界上的任何一点对于该点p可见。 - firev2

一个多边形是“星形”的，如果存在任何点在包含每条边的无限直线的内部。请参见https://cp-algorithms.com/geometry/halfplane-intersection.html。 - Matt Timmermans

对于多边形的每一条边，计算其线性方程和所有位于“内侧”的点的半平面。然后获取所有这些半平面的交集。 - Matt Timmermans

@Matt Timmermans 很好。简单的解决方案，但并不是那么琐碎。 - firev2

已知一种O(n)算法，但是...祝你好运！https://www.researchgate.net/publication/234830402_An_Optimal_Algorithm_for_Finding_the_Kernel_of_a_Polygon - user1196549

Answer 1

非常奇怪的星形定义，根据那个圆形和饼图也是星形...

我能想到的第一个简单且O（n）的可能性是渲染可见性地图：

1. 计算形状的边界框

   

2. 创建边界框的2D映射并将其清零

   因此，将2D数组（纹理）映射到一些分辨率为xs*ys的边界框上

3. 对于每个凸顶点，增加可见性映射

   通过在地图上渲染“无限”三角形/四边形来简单地增加可见性映射

   

   您可以使用绕序规则通过仅检查相邻边缘叉乘的z坐标符号来选择凸或凹顶点，以符合形状的绕序规则。

4. 扫描包含凸顶点数的2D映射单元格

   所有包含凸顶点数的单元格/像素都是可能的Z，因此如果找到任何一个，则表明您的形状是一个“星形”。

这是O(n*xs*ys)，其中n是（凸）顶点的数量，xs*ys是可见性图的分辨率。请注意，如果由于不准确性而分辨率过低，则可能产生错误的负面/正面效果...如果地图的（最大）分辨率恒定，则复杂度将变为O(n)。

例如，可以使用OpenGL和STENCIL缓冲区简单地进行渲染，该缓冲区直接具有增加STENCIL像素的操作，但由于OpenGL中的更改，这会将n限制为255，因为STENCIL现在仅有8位... 但是，您可以通过将BBOX设置为1并清除三角形/四边形的外部而不是增加其内部来解决此问题。然后，持有1的像素就是您的Z，可以与任何渲染引擎一起使用，无需STENCIL。

- Spektre