确定多边形是否为星形
Determine if a polygon is star-shaped
我需要一些关于这方面的提示：
多边形 P 是星形的，如果在 P 的内部存在一个点 p，使得边界上的任何其他点（顶点）对 p 可见。
给定一个多边形 P，如何确定 P 是否为星形多边形？
时间复杂度平均应为 o(n)。
我已经坐了一段时间了，任何帮助都会得到帮助。
星星的定义很奇怪 根据 圆 和 饼 也是星星。 ..
我能想到的第一个简单且 O(n) 的可能性是渲染可见性图：
计算形状的BBOX
创建BBOX的二维地图并用零清除
所以将二维数组（纹理）映射到某个分辨率的 BBOX xs*ys
for each convex vertex increment visibility map
只需在地图上渲染“无限”triangle/quad
您可以使用缠绕规则来选择顶点是凸的还是凹的，只需根据您的形状的缠绕规则检查相邻边叉积的 z 坐标的符号。
扫描包含多个凸顶点的单元格的二维地图
所有包含凸顶点数的 cells/pixels 都是你可能的 Z 所以如果发现你的形状是“星形”。
这是 O(n*xs*ys)，其中 n 是（凸）顶点数，xs*ys 是可见性贴图的分辨率。请注意，如果您的分辨率由于不准确而太低，您可能会产生错误的 negatives/positives ...如果地图的（最大）分辨率不变，则复杂性将变为 O(n).
渲染可以简单地完成，例如使用 OpenGL 和 STENCIL 缓冲区，它直接具有增加 STENCIL 像素的操作但是这将限制 n 到 255，因为现在 STENCIL 只有 8 位（更改后在 OpenGL 中）...但是，您可以通过将 BBOX 设置为 1 并清除 triangle/quad 的外部而不是增加其内部来解决此问题。那么持有 1 的像素就是你的 Z 这可能与任何渲染引擎一起使用而不需要 STENCIL
我需要一些关于这方面的提示：
多边形 P 是星形的，如果在 P 的内部存在一个点 p，使得边界上的任何其他点（顶点）对 p 可见。
给定一个多边形 P，如何确定 P 是否为星形多边形？
时间复杂度平均应为 o(n)。
我已经坐了一段时间了，任何帮助都会得到帮助。
星星的定义很奇怪 根据 圆 和 饼 也是星星。 ..
我能想到的第一个简单且 O(n) 的可能性是渲染可见性图：
计算形状的BBOX
创建BBOX的二维地图并用零清除
所以将二维数组（纹理）映射到某个分辨率的 BBOX
xs*ysfor each convex vertex increment visibility map
只需在地图上渲染“无限”triangle/quad
您可以使用缠绕规则来选择顶点是凸的还是凹的，只需根据您的形状的缠绕规则检查相邻边叉积的 z 坐标的符号。
扫描包含多个凸顶点的单元格的二维地图
所有包含凸顶点数的 cells/pixels 都是你可能的
Z所以如果发现你的形状是“星形”。
这是 O(n*xs*ys)，其中 n 是（凸）顶点数，xs*ys 是可见性贴图的分辨率。请注意，如果您的分辨率由于不准确而太低，您可能会产生错误的 negatives/positives ...如果地图的（最大）分辨率不变，则复杂性将变为 O(n).
渲染可以简单地完成，例如使用 OpenGL 和 STENCIL 缓冲区，它直接具有增加 STENCIL 像素的操作但是这将限制 n 到 255，因为现在 STENCIL 只有 8 位（更改后在 OpenGL 中）...但是，您可以通过将 BBOX 设置为 1 并清除 triangle/quad 的外部而不是增加其内部来解决此问题。那么持有 1 的像素就是你的 Z 这可能与任何渲染引擎一起使用而不需要 STENCIL