我正在编写一个函数来在方阵上绘制一个近似圆（在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）物理距离（以米为单位）的所有像素小于或等于半径，不需要是整数。
我觉得我的算法可能不是解决这个问题的最佳方案。特别是，我希望它包含中心所在的像素，即使半径非常小。
有什么想法吗？
（有关示例图像，请参阅 https://i.sstatic.net/3mZ5X.png CCD 相机上的衍射极限点）。
I am writing a function to draw an approximate circle on a square array (in Matlab, but the problem is mainly algorithmic).
The goal is to produce a mask for integrating light that falls on a portion of a CCD sensor from a diffraction-limited point source (whose diameter corresponds to a few pixels on the CCD array). In summary, the CCD sensor sees a pattern with revolution-symmetry, that has of course no obligation to be centered on one particular pixel of the CCD (see example image below).
Here is the algorithm that I currently use to produce my discretized circular mask, and which works partially (Matlab/Octave code):
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);
As you can see, my algorithm selects (sets to 1) all the pixels whose physical distance (in meters) is smaller or equal to a radius, which doesn't need to be an integer.
I feel like my algorithm may not be the best solution to this problem. In particular, I would like it to include the pixel in which the center is present, even when the radius is very small.
Any ideas ?
(See https://i.sstatic.net/3mZ5X.png for an example image of a diffraction-limited spot on a CCD camera).
发布评论
评论（2）
如果您想选择像素当且仅当它们包含圆 C 的任何部分时：
在每个像素中放置一个半径 = 像素大小一半的小圆 A，并在其周围放置另一个 R=sqrt(2)*圆的一半大小（外接圆）
要测试两个圆是否相互接触，您只需计算中心到中心的距离并减去两个半径的总和。
如果测试圆 C 在 A 内，则选择该像素。如果它在 B 内但不在 C 内，则需要测试所有四个像素边是否重叠，如下所示 圆线段碰撞检测算法？
强力近似方法是在每个像素内制作更精细的网格并测试该网格中的每个中心点。
if you like to select pixels if and only if they contain any part of the circle C:
in each pixel place a small circle A with the radius = halv size of the pixel, and another one around it with R=sqrt(2)*half size of the circle (a circumscribed circle)
To test if two circles touch each other you just calculate the center to center distances and subtract the sum of the two radii.
If the test circle C is within A then you select the pixel. If it's within B but not C you need to test all four pixel sides for overlap like this Circle line-segment collision detection algorithm?
A brute force approximate method is to make a much finer grid within each pixel and test each center point in that grid.
这是一个经过充分研究的问题。可以进行多个级别的优化：
您可以强力检查每个像素是否都在圆圈内。 (
r^2 >= (x-x0)^2 + (y-y0)^2)您可以强力检查圆周围的正方形中的每个像素是否都在内部圆圈。 (
r^2 >= (x-x0)^2 + (y-y0)^2其中|x-x0| 和 | y-y0| < r)您可以逐行（其中
|y-y0| < r）计算起始 x 结束 x 并填充之间的所有线条。 （尽管平方根并不便宜。）更复杂的算法有无限的可能性。这是一个常见的：http://en.wikipedia.org/wiki/Midpoint_circle_algorithm（填写圆圈留作练习）
这实际上取决于您想要达到的复杂程度以及良好表现的必要性。
This is a well-studied problem. Several levels of optimization are possible:
You can brute-force check if every pixel is inside the circle. (
r^2 >= (x-x0)^2 + (y-y0)^2)You can brute-force check if every pixel in a square bounding the circle is inside the circle. (
r^2 >= (x-x0)^2 + (y-y0)^2where|x-x0| < rand|y-y0| < r)You can go line-by-line (where
|y-y0| < r) and calculate the starting x ending x and fill all the lines in between. (Although square roots aren't cheap.)There's an infinite possibility of more sophisticated algorithms. Here's a common one: http://en.wikipedia.org/wiki/Midpoint_circle_algorithm (filling in the circle is left as an exercise)
It really depends on how sophisticated you want to be based on how imperative good performance is.