查找极坐标中特定范围内的所有像素

Question

我想找到图像中所有的像素（在笛卡尔坐标中），它们位于r_min r_max theta_min和theta_max某个极性范围内。因此，换句话说，我有一些用上述参数定义的环形截面，我想找到位于其中的像素的整数x，y坐标。蛮力解决方案已经到了中间路线（遍历图像的所有像素并检查它是否在其中），但我想知道是否有一些更有效的解决方案。

谢谢

Answer 1

在蛮力解决方案中，您可以首先通过计算四个顶点并根据需要包括四个基本极限点来确定该区域的紧密边界框。然后，对于每个像素，您将必须求值两个圆（二次表达式）和两个直线（线性表达式）。通过递增地进行计算（X => X + 1），操作数减少到几乎没有。

在圆圈内

f(X,Y) = X²+Y²-2XXc-2YYc+Xc²+Yc²-R² <= 0

递增，

f(X+1,Y) = f(X,Y)+2X+1-2Xc <= 0

如果您真的想避免这种开销，则可以使用扫描线转换技术。首先考虑填充一个倾斜的矩形。通过中间顶点绘制两条水平线，可以将矩形分解为两个三角形和一个平行四边形。然后，对于穿过这些形状之一的任何扫描线，您都事先知道要相交的那对边。从那里，您知道需要填充扫描线的哪一部分。

您可以泛化为任何形状，尤其是圆弧段。准备好进行相对微妙的案例分析，但是找到交叉点本身并不难。这可能有助于通过垂直方向穿过中心的方式来划分区域，以使任何水平方向始终与轮廓相交两次，而不是四次。

Answer 2

为了简单起见，我们假定该部分的中心为0,0。如果没有，很容易通过偏移所有坐标来进行更改。

对于从r_max到-r_max的每个可能的y坐标，找到两个半径的圆的x坐标：-sqrt(r*r-y*y)和sqrt(r*r-y*y)。对于r_max圆之内和r_min圆之外的每个点，可能都是该部分的一部分，将需要进一步测试。

现在执行相同的x坐标计算，但是这次使用由角度描述的线段。您需要一些条件逻辑来确定该行的哪一侧在内部，哪一侧在外部，以及它是否影响该部分的上部或下部。