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

我有一个由大约400万像素组成的图像。 每个像素都有一个地理XY坐标（坐标位于像素的中心），每个像素对应一个A x A米的正方形。

比方说，我将一个随机点放在图像上（使用随机的XY坐标），并围绕此点绘制一个半径为B米的圆：

我的问题是：我如何有效地计算圆圈触及哪个方块？

---

你需要一个有效的函数来确定圆是否与正方形相交（也包括，也在里面）。 这个（Delphi实现）不使用三角蚂蚁平方根。

请注意，此功能用于单个方块。 但是这种方法可能会修改为方形网格 - 您可以评估整个列的水平偏移值一次，整个行的垂直偏移值一次，然后使用计算值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/84985.html

上一篇: How to calculate which grid squares a circle touches?

下一篇: Polygon area, perimeter and side length around the circle with python