How to calculate which grid squares a circle touches?

I have an image consisting from roughly 4,000,000 pixels. Each pixel has a geographic XY-coordinate (the coordinate is located in the center of the pixel) and each pixel corresponds to a A x A meter square.

Lets say I drop a random point on to the image (with random XY-coordinates) and draw a circle of radius B meters around this point:

My question is: How can I efficiently calculate which squares the circle touches?

---

You need an effective function to determine whether circle intersects a square (also includes, also lies inside). This (Delphi implementation) doesn't use trigonometry ant square roots.

Note that this function is intended for single square. But this approach might be modified for square grid - you can evaluate horizontal shift value for the whole column once, and vertical shift value for the whole row once, then use calculated values 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;

链接地址: http://www.djcxy.com/p/84986.html

上一篇: 如何确定与切线垂直的圆弧上的点的距离？

下一篇: 如何计算一个圆圈接触哪个方格？