0

我在屏幕上使用 OpenGL ES 渲染了许多 2D（可能相交）多边形。所有的多边形都完全包含在屏幕中。找到这些多边形的并集面积占屏幕总面积百分比的最及时方法是什么？需要及时性，因为我需要在多边形移动时立即更新覆盖区域。

目前，我将每个多边形表示为一个二维布尔数组。使用多边形中的点函数（来自几何包），我对屏幕上的每个点（x，y）进行采样以检查它是否属于多边形，如果是，则设置多边形[x][y] = true，否则为假。

在对屏幕中的所有多边形执行此操作后，我再次遍历所有屏幕像素，并检查每个多边形数组，如果任何多边形的多边形 [x] [y] 值设置为 true，则将该像素计数为“已覆盖” .

这可行，但随着多边形数量的增加，性能并不理想。有没有更好的方法来做到这一点，如果可能的话，使用开源库？我想到了：

(1) 合并多边形以获得一个或多个不重叠的多边形。然后使用标准的多边形面积公式计算每个多边形的面积。然后总结它们。不知道如何让它工作？

(2) 以某种方式使用 OpenGL。想象一下，我正在用一种颜色渲染所有这些多边形。是否可以用某种颜色计算屏幕缓冲区上的像素数？这听起来确实是一个不错的解决方案。

有什么有效的方法来做到这一点？

4

3 回答 3

1

如果您知道背景颜色并且所有多边形都有其他颜色，则可以从帧缓冲区读取所有像素glReadPixels()并简单地计算所有颜色与背景不同的像素。

如果不满足第一个条件，您可以考虑创建自定义帧缓冲区并使用相同颜色渲染所有多边形（例如，背景为 (0.0, 0.0, 0.0)，多边形为 (1.0, 0.0, 0.0)）。接下来，读取生成的帧缓冲区并计算整个屏幕上红色的平均值。

于 2013-01-06T12:47:47.023 回答
1

如果要获得不重叠的多边形，可以运行线相交算法。一个简单的变体是Bentley-Ottmann 算法，但甚至更快的算法O(n log n + k)（具有 n 个顶点和 k 个交叉点）也是可能的。

给定一个线交点，您可以通过在交点上构造一个连接两个多边形的顶点来统一两个多边形。然后沿着另一个多边形内部的一个多边形的顶点（您可以使用多边形中的点函数确定必须进入的方向），并删除所有顶点和边，直到到达多边形的外部. 在那里，您通过在两个多边形的第二个交点上创建一个新顶点来修复多边形。

除非我弄错了，否则这可以及时运行，O(n log n + k * p)其中 p 是多边形的最大重叠。

统一多边形后，您可以使用普通的面积函数来计算多边形的确切面积。

于 2013-01-06T12:52:27.500 回答
0

我认为用像素数计算多边形面积的尝试太复杂了，有时甚至不准确。您可以在有关计算多边形覆盖面积的stackoverflow答案中看到类似的内容，如果您构造正多边形，请查看正多边形的面积，

于 2013-01-06T12:39:36.800 回答