判断多边形是否是星形

Question

我需要一些关于这个的提示：

如果多边形 P 的内部存在一个点 p，并且边界上的任何其他点（顶点）对 p 可见，则该多边形 P 是星形的。

给定一个多边形P，如何判断P是否是星形多边形？

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

我已经坐了一段时间了，任何帮助都会得到帮助。

Answer 1

根据圆圈和馅饼也是星星，对星星的定义非常奇怪......

我能想到的第一个简单和O(n)可能性是渲染可见性图：

1. 计算形状的 BBOX

   

2. 创建 BBOX 的 2D 地图并用零清除它

   因此将 2D 数组（纹理）映射到某个分辨率的 BBOXxs*ys

3. 对于每个凸顶点增量可见性图

   只需将“无限”三角形/四边形渲染到地图上

   

   您可以使用缠绕规则来选择顶点是凸还是凹，只需根据形状的缠绕规则检查相邻边叉积的 z 坐标的符号即可。

4. 扫描 2D 地图以查找包含凸顶点数量的单元格

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

这是（凸）顶点的数量，O(n*xs*ys)是可见性图的分辨率。请注意，如果您的分辨率由于不准确而太低，您可能会产生假阴性/阳性...如果地图的（最大）分辨率恒定，那么复杂性将变为。nxs*ysO(n)

渲染可以简单地完成，例如使用 OpenGL 和 STENCIL 缓冲区，它直接具有增加 STENCIL 像素的操作，但是，由于nSTENCIL 目前只有 8 位（在 OpenGL 更改后），因此将限制为 255...但是您可以解决方法这是通过将 BBOX 设置为1并清除三角形/四边形的外部而不是增加其内部来实现的。那么保存的像素1就是你的，Z这可以与任何渲染引擎一起使用，不需要 STENCIL