Как рассчитать, какие квадраты сетки касаются круга?

Question

У меня есть изображение, состоящее примерно из 4 000 000 пикселей. Каждый пиксель имеет географическую координату XY (координата расположена в центре пикселя), и каждый пиксель соответствует квадрату метра A x A.

Допустим, я бросаю случайную точку на изображении (со случайными XY-координат) и нарисуйте круг метров радиус B вокруг этой точки:

Мой вопрос: Как я могу эффективно рассчитать, какие квадраты касаются круга?

Answer 1

Вам нужна эффективная функция, чтобы определить, пересекает ли круг квадрат (также включает в себя и внутри). Это (реализация 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;