出于CCD集成的目的，在阵列上绘制圆

Question

我正在写一个在正方形数组上绘制近似圆的函数(在Matlab中，但这个问题主要是算法问题)。

目标是制造一种掩模，用于集成从衍射受限点源(其直径对应于CCD阵列上的几个像素)落在CCD传感器的一部分上的光。总而言之，CCD传感器看到的图案具有旋转对称性，当然没有必要以CCD的一个特定像素为中心(参见下面的示例图像)。

这是我目前用来产生我的离散化圆形蒙版的算法，它部分工作(Matlab/Octave代码)：

xt = linspace(-xmax, xmax, npixels_cam); % in physical coordinates (meters)
[X Y] = meshgrid(xt-center(1), xt-center(2)); % shifted coordinate matrices
[Theta R] = cart2pol(X,Y);
R = R'; % cart2pol uses a different convention for lines/columns
mask = (R<=radius);

正如您所看到的，我的算法选择(设置为1)物理距离(以米为单位)小于或等于半径的所有像素，这些像素不需要是整数。

我觉得我的算法可能不是解决这个问题的最佳方案。特别是，我希望它包含中心所在的像素，即使半径非常小。

有什么想法吗？

(有关http://i.stack.imgur.com/3mZ5X.png相机上衍射限制光斑的示例图像，请参见CCD )。

Answer 1

如果您希望在且仅当像素包含圆C的任何部分时才选择这些像素：

在每个像素中放置一个半径为该像素一半大小的小圆A，并在其周围放置另一个半径为R=sqrt(2)*该圆的一半大小的圆(外接圆)

要测试两个圆是否相互接触，只需计算中心到中心的距离，然后减去两个半径的总和。

如果测试圆C在A内，则选择像素。如果它在B内，但不在C内，则需要测试所有四个像素的边是否重叠，如下所示的Circle line-segment collision detection algorithm?

一种强力近似方法是在每个像素内创建一个更精细的网格，并测试该网格中的每个中心点。

Answer 2

这是一个经过充分研究的问题。有几个级别的优化是可能的：

• 你可以暴力检查每个像素是否都在圆内。(r^2 >= (x-x0)^2 + (y-y0)^2)
• You可以暴力检查圆周围的方块中的每个像素是否都在圆内。( |y-y0| < r)
• You和|x-x0| < r可以逐行执行(其中|y-y0| < r)，并计算起始x和结束x，并填充其间的所有行。(虽然平方根不是cheap.)
• There's，但更复杂算法的无限可能性。下面是一个常见的例子：http://en.wikipedia.org/wiki/Midpoint_circle_algorithm (作为练习，在圆圈中进行填充)

这真的取决于你想要变得多复杂，基于好的性能是多么迫切。