c++ - 有效地访问一圈光线（找到最近的障碍物轮廓）

Question

有一个二进制网格（比如黑色和白色像素，黑色 = 空，白色 = 障碍物）。从黑色的给定点开始，我想向各个方向发射“射线”。当达到给定长度（例如 100）或撞击白色像素（在这种情况下，应标记该像素的位置，也就是障碍物轮廓）时，这些光线应该中止。那些标记的像素导致从给定点“可见”的所有障碍物轮廓的视图（未被其他障碍物阻挡）。

到目前为止，我所想到的只是简单地调用足够数量的 bresenham 行。在半径为 100 的情况下，这意味着 100*2*pi = 628 行来覆盖最外圈上的所有像素。然而，这会导致对靠近中心的相同像素进行多次多次检查。现在我可以将支票分成多个环，每个环都有不同密度的 bresenham 线，但这似乎也相当低效。

有人碰巧对此有更有效的算法想法吗？非常感谢提前！

标签： c++algorithmbresenham

Answer 1

设两点 (x1,y1) 和 (x2,y2) 之间的“平方距离”为 max(|x1-x2|,|y1-y2|)，使得围绕中心的“平方距离”增加的点为越来越大的广场。

现在，对于距中心点的每个平方距离d，按递增顺序，跟踪中心点可以看到距离 <= d 的所有障碍物的角度。

对于 d=0，您可以使用从 [(0,360)] 开始的角度间隔列表。

对于每个新距离，您可以检查列表，检查给定角度内的新像素，并在遇到障碍物时从间隔中删除角度。从中心点可以看到导致您修改间隔的每个障碍物，因此您可以将其标记为这样。

此方法仅检查一次像素，并且仅检查您可以看到的像素。然而，我上面写的方式需要三角函数，这很慢。对于一个实际的实现，而不是实际使用角度，使用只需要简单数学的斜率，并分别处理每个八分圆。