具有二进制网格(例如黑色和白色像素，黑色=空，白色=障碍物)。
从黑色的给定点开始，我要向各个方向发出“射线”。当达到给定的长度(例如100)或击中白色像素时，这些射线应该中断(在这种情况下，应标记该像素的位置，也就是障碍物轮廓)。
这些标记的像素导致从给定点“可见”(不受其他障碍物阻挡)的所有障碍物轮廓的 View 。
到目前为止，我所想到的就是简单地调用足够数量的布雷森汉姆线。在半径为100的情况下，这意味着100 * 2 * pi = 628条线可以覆盖最外面的圆上的所有像素。
但是，这导致对同一像素更靠近中心的许多多次检查。现在，我可以将支票分成多个环，每个环具有不同的布雷森汉姆线密度，但这似乎效率也很低。
有人为此碰巧有一个更有效的算法思路吗？
提前非常感谢!
最佳答案
不幸的是，关于图形处理技术的提示虽然引人入胜，但不适用于我的情况，因为我无法使用着色器或相机等。
到目前为止，我自己已经找到了足够有效的解决方案。基本思想是从轮廓而不是从原点发出光线。此外，使用名为“reachable”的辅助网格，其中标记了从原点成功可见的所有像素。这样，只有很少的像素被读取两次，大部分仅被读取一次，而某些像素最多被写入一次。该代码还很凌乱，因此这里仅是伪代码:
Have desired origin O.x/O.y
Have obstacle bool grid Obstacle
Define bool grid Reachable[w][h]
Clear Reachable with false
Reachable[O.x][O.y] = true
For each Point C on all obstacle Contours // if not available, compute contours by finding all pixels adjacent to non-obstacle
For all Pixels A on Bresenham line from C to O
If Obstacle[A.x][A.y]
Continue with outer loop on contours // abort this line due to obstacle hit
If Reachable[A.x][A.y]
For all Pixels B on Bresenham line from C to A
Reachable[B.x][B.y] = true // mark all pixels on this line as Reachable
Mark C as a desired result pixel
Continue with outer loop on contours
关于c++ - 有效地进入一圈射线(找到最近的障碍物轮廓)，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/59752115/