algorithm - 检查特定半径内所有像素的最佳方法是什么？

Question

我目前正在开发一个应用程序，可以在即将下雨时提醒用户。为此，我想检查用户位置周围的特定区域是否有降雨(降雨雷达图像强度的不同像素颜色)。我希望选中的区域是一个圆圈，但我不知道如何有效地做到这一点。

假设我想检查 50 公里的半径。我目前的想法是获取大小为 100kmx100km 的图像子集(用户 + 西 50 公里，用户 + 东 50 公里，用户 + 北 50 公里，用户 + 南 50 公里)，然后检查该子集中的每个像素是否离用户较近 50 公里。

我的问题是，是否有更好的解决方案可用于此类问题？

Answer 1

如果您正在搜索的事件(下雨或其他任何事件)的发生相对罕见，那么扫描一个正方形或像素并没有错，只有在该正方形中检测到下雨后，检查降雨是否在所需的 50 公里范围内。请注意，这里的关键点是您不需要检查正方形的每个像素是否在圆圈内(那样效率很低)，您必须搜索您的事件(下雨)首先也是只有当你找到它时，检查它是否落在 50 公里的圈内。为了有效地实现这一点，您还必须制定一些智能策略来处理图像上的多像素雨“污点”。

但是，由于您扫描的是光栅图像，因此可以轻松实现众所周知的 Bresenham circle algorithm为每条扫描线找到圆的起点和终点。这样您就可以轻松地将扫描限制在所需的 50 公里半径范围内。

转念一想，您甚至不需要 Bresenham 算法。对于正方形中的每一行像素，计算该行与 50 公里圆的交点(使用带平方根的常用教科书公式)，然后检查落在这些交点之间的所有像素。以相同的方式处理所有行，您就完成了。

附言不幸的是，我链接的维基百科页面根本没有介绍 Bresenham 算法。它有 Michener 圆算法的代码。 Michener 算法也适用于圆形光栅化目的，但不如 Bresenham 算法精确。如果您关心精确度，请在某处找到真正的 Bresenham。实际上，在网上很难找到它:大多数搜索结果错误地将 Michener 显示为 Bresenham。