如何计算一个圆碰到哪些网格正方形？

Question

我有一个由大约4,000,000像素组成的图像。每个像素都有一个地理XY坐标（坐标位于像素的中心），每个像素对应于一个a×am平方。

假设我把一个随机点放在图像上（用随机的xy坐标），并围绕这个点画一个半径为B米的圆：

我的问题是：我怎样才能高效地计算出圆触及的是哪些正方形？

Answer 1

注意，这个函数是针对单正方形的。但是对于方形网格，可以修改这种方法--您可以计算整列的水平移位值一次，计算整行的垂直移位值一次，然后使用计算值squareddist=sqdistforrow[row]+sqdistforcolumn[Col]

function IsCircleIntersectsSquare
            (CX, CY, CR: Integer; {circle}
             SX, SY, A: Integer{square}): Boolean;
var
  halfA, dx, dy, t, SquaredDist: Integer;
begin

  //halfsize
  halfA := A div 2;

  //distances to square center
  dx := CX - SX;
  dy := CY - SY;

  SquaredDist := 0;

  //square sides divide plane to 9 parts
  t := dx + halfA;
  if t < 0 then
    SquaredDist := t * t
  else begin
    t := dx - halfA;
    if t > 0 then
      SquaredDist := t * t
  end;

  t := dy + halfA;
  if t < 0 then
    SquaredDist := SquaredDist + t * t
  else begin
    t := dy - halfA;
    if t > 0 then
      SquaredDist := SquaredDist + t * t
  end;

  Result := SquaredDist <= CR * CR
end;