algorithm - 二维光栅图像视线算法

Question

我正在开发一个有趣的简单地图应用程序，我需要做的一件事是找到（并着色）从当前位置可见的所有点。在这种情况下，点是像素。我的地图是一个光栅图像，其中透明像素是开放空间，而任何其他像素都是不透明的。（没有半透明像素；alpha 为 0 或 100%。）从这个意义上说，它有点像常规的泛光填充，限制是每个填充的像素必须有清晰的视线到原点。下图显示了几个这样的区域（小十字线是原点，白色 = 透明）：

( http://tinyurl.com/nf3nqa4 )

此外，我最终感兴趣的是“边界”其他颜色的点，即我想要构成可见区域边缘的点列表。

我当前且非常低效的解决方案是我上面描述的修改后的洪水填充。这种方法返回正确的结果，但由于需要将行上的每个像素迭代到泛洪填充中每个像素的原点，因此速度非常慢。我的图像被缩小和量化，但我仍然需要大约 1MP 才能获得可接受的精度，典型的 LoS 区域每个至少 100,000 像素。

我很可能使用了错误的搜索词，但我无法找到任何可以解决这种（光栅化）LoS 案例的算法讨论。

Answer 1

我怀疑如果你的“墙”被表示为方程而不是光栅图像中的简单像素，这可以更有效地完成。例如，多边形/三角形、圆形、椭圆。

这就像 2D 中的光线追踪（搜索该术语）。换句话说，您可以考虑从图像中每个像素到兴趣点的光线/线，并仅在像素不与任何对象相交时为该像素着色。

此方法确实需要您测试图像中每个像素与每个对象的交集；但是，如果您查看光线追踪，您会发现许多有效的方法来测试这些交叉点。它们主要用于 3D 案例，但将它们转换为 2D 应该很简单。

有 3D 光线追踪器在大得多的图像上速度非常快，所以这应该是非常可行的。

Answer 2

您可以尝试对每种颜色进行 delaunay 三角剖分。我的意思是你可以试着用 DT 找出每种颜色的形状。