查找极坐标中一定范围内的所有像素
Finding All Pixels Within Certain Range in Polar Coordinates
我想找到图像中(在笛卡尔坐标系中)位于特定极坐标范围内的所有像素,r_min r_max theta_min 和 theta_max。所以换句话说,我有一些用上述参数定义的环形部分,我想找到位于其中的像素的整数 x,y 坐标。蛮力解决方案出现在中途(遍历图像的所有像素并检查它是否在其中)但我想知道是否有更有效的解决方案。
谢谢
为简单起见,我们假设该部分的中心位于 0,0。如果不是,通过偏移所有坐标很容易改变。
对于从 r_max
到 -r_max
的每个可能的 y 坐标,找到两个半径的圆的 x 坐标:-sqrt(r*r-y*y)
和 sqrt(r*r-y*y)
。对于 r_max
圆内和 r_min
圆外的每个点,它 可能 是该部分的一部分,需要进一步测试。
现在进行相同的 x 坐标计算,但这次使用角度描述的线段。您需要一些条件逻辑来确定线条的哪一侧在内部,哪一侧在外部,以及它是否影响该部分的上部或下部。
在蛮力解决方案中,您可以首先确定区域的紧密边界框,通过计算四个顶点并根据需要包括四个基数极值点。然后对于每个像素,您将必须评估两个圆(二次表达式)和两条直线(线性表达式)。通过增量计算 (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
如果您真的想避免这种开销,您将求助于扫描线转换技术。首先想到填充一个倾斜的矩形。通过中间顶点绘制两条水平线,将矩形分解为两个三角形和一个平行四边形。然后对于穿过这些形状之一的任何扫描线,您事先知道您将与哪一对边相交。从那里,您知道需要填充扫描线的哪一部分。
您可以概括为任何形状,尤其是您的圆弧段。准备好进行相对微妙的案例分析,但找到交叉点本身并不难。它可能有助于通过中心垂直分割域,以便任何水平总是与轮廓相交两次,而不是四次。
我想找到图像中(在笛卡尔坐标系中)位于特定极坐标范围内的所有像素,r_min r_max theta_min 和 theta_max。所以换句话说,我有一些用上述参数定义的环形部分,我想找到位于其中的像素的整数 x,y 坐标。蛮力解决方案出现在中途(遍历图像的所有像素并检查它是否在其中)但我想知道是否有更有效的解决方案。
谢谢
为简单起见,我们假设该部分的中心位于 0,0。如果不是,通过偏移所有坐标很容易改变。
对于从 r_max
到 -r_max
的每个可能的 y 坐标,找到两个半径的圆的 x 坐标:-sqrt(r*r-y*y)
和 sqrt(r*r-y*y)
。对于 r_max
圆内和 r_min
圆外的每个点,它 可能 是该部分的一部分,需要进一步测试。
现在进行相同的 x 坐标计算,但这次使用角度描述的线段。您需要一些条件逻辑来确定线条的哪一侧在内部,哪一侧在外部,以及它是否影响该部分的上部或下部。
在蛮力解决方案中,您可以首先确定区域的紧密边界框,通过计算四个顶点并根据需要包括四个基数极值点。然后对于每个像素,您将必须评估两个圆(二次表达式)和两条直线(线性表达式)。通过增量计算 (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
如果您真的想避免这种开销,您将求助于扫描线转换技术。首先想到填充一个倾斜的矩形。通过中间顶点绘制两条水平线,将矩形分解为两个三角形和一个平行四边形。然后对于穿过这些形状之一的任何扫描线,您事先知道您将与哪一对边相交。从那里,您知道需要填充扫描线的哪一部分。
您可以概括为任何形状,尤其是您的圆弧段。准备好进行相对微妙的案例分析,但找到交叉点本身并不难。它可能有助于通过中心垂直分割域,以便任何水平总是与轮廓相交两次,而不是四次。