Координаты каждой точки по окружности окружности

Question

Прежде всего, обратите внимание, что этот вопрос не является дубликатом: 1st, 2nd и 3rd.

Я использую delphi и openCV, но я ищу алгоритм, решение, независимо от языка.

Для точного анализа изображения мне необходимо проверить изменения интенсивности пикселей в круговых областях. Поэтому я читаю значения пикселей по окружности непрерывно растущего круга. Чтобы это сделать, я, конечно, должен знать координаты пикселей.

Лучшее решение я нашел y:= Round(centerY + radius * sin(angle)), x:= Round(centerX + radius * cos(angle)), а потому, что отсчет только 360 градусов вряд ли достаточно, если радиус окружности больше, чем около 60px, то угол подсчитываются как это angle:= angle + (360/(2 * 3.14 * currentRadius)) -> Я несутся через каждый значение от 0 до 360, в то время как значение увеличивается на долю 360/окружность круга в пикселях. Но этот подход не очень точен. Чем больше круг, тем меньше должна быть доля угла, и прецессия страдает от неточности Pi, плюс округление.

Если я использую упомянутый метод, и попытаться сделать подсчитанные пикселей с этим кодом:

centerX:= 1700; 
    centerY:= 1200; 
    maxRadius:= 500; 

    for currentRadius:= 80 to maxRadius do 
    begin 

    angle:= 0; 
    while angle < 360 do 
    begin 

     xI:= Round(centerX + currentRadius * cos(angle)); 
     yI:= Round(centerY + currentRadius * sin(angle)); 
     angle:= angle + (360/(2 * 3.14 * currentRadius)); 

     //this is openCV function, to test the code, you can use anything, that will draw a dot... 
     cvLine(image,cvPoint(xI,yI),cvPoint(xI,yI),CV_RGB(0, 255, 0)); 

    end; 

    end; 

результат заключается в следующем:

Это не плохо, но, принимая во внимание, что ровно треть всех пикселей в круговой области черные, вы понимаете, что много пикселей было «пропущено». Плюс, внимательно глядя на край последнего круга, ясно видно, что некоторые точки с фактической окружности - еще один результат погрешности ...

Возможно, я мог бы использовать формулу (x - xorig)^2 + (y - yorig)^2 = r^2, чтобы проверить каждый возможный пиксель в прямоугольная область вокруг центра, немного больше, чем диаметр круга, если это так, или не падает на окружность царя. Но это было бы очень медленно повторять все это время, когда круг растет.

Есть ли что-то, что можно было бы сделать лучше? Может ли кто-нибудь помочь мне улучшить это? Я вообще не настаиваю на чем-либо от своего решения и соглашусь с любым другим решением, если оно дает желаемые результаты => Позвольте мне прочитать значения все (или подавляющее большинство - 95% +) пикселей на окружность окружности с заданным центром и радиусом. Чем быстрее, тем лучше ...

Answer 1

1) Создайте список пикселей с наименьшим радиусом окружности. Достаточно сохранить первый октант (диапазон 0..Pi/4 в первом квадранте системы координат) круга и получить симметричные точки с отражениями. Вы можете использовать, например, алгоритм круга Bresenham или просто уравнение окружности.

2) Для следующей итерации пройдите все координаты в списке (используйте правый, если есть две точки с одинаковым значением Y) и проверьте, находится ли соседний сосед (или два соседа!) Внутри следующего радиуса. Для последней точки проверьте также верхний, правый верхний сосед (по диагонали Pi/4). Вставьте хороших соседей (один или два) в следующий список координат.

Example for Y=5. 
R=8 X=5,6 //note that (5,5) point is not inside r=7 circle 
R=9 X=7 
R=10 X=8 
R=11 X=9 
R=12 X=10 
R=13 X=11,12 //! 
R=14 X=13 

При таком подходе вы будете использовать все пиксели максимального радиуса окружности без зазоров, и процесс проверки для генерации списка довольно быстро.

Редактировать: Код реализует немного другой подход, он использует нижнюю границу пикселя линии для построенной верхней строки.

Он генерирует круги в заданном диапазоне, окрашивает их в психоделические цвета. Вся математика находится в целых числах, без поплавков, без тригонометрических функций! Pixels используются только в демонстрационных целях.

procedure TForm1.Button16Click(Sender: TObject); 

    procedure FillCircles(CX, CY, RMin, RMax: Integer); 

    //control painting, slow due to Pixels using 
    procedure PaintPixels(XX, YY, rad: Integer); 
    var 
     Color: TColor; 
     r, g, B: Byte; 
    begin 
     g := (rad mod 16) * 16; 
     r := (rad mod 7) * 42; 
     B := (rad mod 11) * 25; 
     Color := RGB(r, g, B); 
    // Memo1.Lines.Add(Format('%d %d %d', [rad, XX, YY])); 
     Canvas.Pixels[CX + XX, CY + YY] := Color; 
     Canvas.Pixels[CX - YY, CY + XX] := Color; 
     Canvas.Pixels[CX - XX, CY - YY] := Color; 
     Canvas.Pixels[CX + YY, CY - XX] := Color; 
     if XX <> YY then begin 
     Canvas.Pixels[CX + YY, CY + XX] := Color; 
     Canvas.Pixels[CX - XX, CY + YY] := Color; 
     Canvas.Pixels[CX - YY, CY - XX] := Color; 
     Canvas.Pixels[CX + XX, CY - YY] := Color; 
     end; 
    end; 

    var 
    Pts: array of array [0 .. 1] of Integer; 
    iR, iY, SqD, SqrLast, SqrCurr, MX, LX, cnt: Integer; 
    begin 
    SetLength(Pts, RMax); 

    for iR := RMin to RMax do begin 
     SqrLast := Sqr(iR - 1) + 1; 
     SqrCurr := Sqr(iR); 
     LX := iR; // the most left X to check 

     for iY := 0 to RMax do begin 
     cnt := 0; 
     Pts[iY, 1] := 0; // no second point at this Y-line 
     for MX := LX to LX + 1 do begin 
      SqD := MX * MX + iY * iY; 
      if InRange(SqD, SqrLast, SqrCurr) then begin 
      Pts[iY, cnt] := MX; 
      Inc(cnt); 
      end; 
     end; 

     PaintPixels(Pts[iY, 0], iY, iR); 
     if cnt = 2 then 
      PaintPixels(Pts[iY, 1], iY, iR); 

     LX := Pts[iY, 0] - 1; // update left limit 
     if LX < iY then // angle Pi/4 is reached 
      Break; 
     end; 
    end; 
    // here Pts contains all point coordinates for current iR radius 
    //if list is not needed, remove Pts, just use PaintPixels-like output 
    end; 

begin 
    FillCircles(100, 100, 10, 100); 
    //enlarge your first quadrant to check for missed points 
    StretchBlt(Canvas.Handle, 0, 200, 800, 800, Canvas.Handle, 100, 100, 100, 
    100, SRCCOPY); 
end; 

Answer 2

Если вы хотите сделать ваш код быстрее, не называйте тригонометрические функции внутри внутреннего цикла, приращение sin(angle) и cos(angle) использованием

sin(n*step)=sin((n-1)*step)*cos(step)+sin(step)*cos((n-1)*step) 
cos(n*step)=cos((n-1)*step)*cos(step)-sin(step)*sin((n-1)*step) 

что

... 
    for currentRadius:= 80 to maxRadius do 
    begin 

    sinangle:= 0; 
    cosangle:= 1; 
    step:= 1/currentRadius; // ? 
    sinstep:= sin(step); 
    cosstep:= cos(step); 
    while {? } do 
    begin 

     xI:= Round(centerX + currentRadius * cosangle); 
     yI:= Round(centerY + currentRadius * sinangle); 

     newsin:= sinangle*cosstep + sinstep*cosangle; 
     newcos:= cosangle*cosstep - sinstep*sinangle; 

     sinangle:= newsin; 
     cosangle:= newcos; 

     ...  
    end; 

    end; 

Answer 3

Почему бы Вы просто используете больше цифр для Pi и перестаете округлять, чтобы повысить точность?

Далее я предлагаю вам использовать подпиксельные координаты для получения более точных значений интенсивности, если вы можете позволить себе интерполяцию.

Также очень редко используются градусы в расчетах. Я настоятельно рекомендую использовать радианы. Не уверенный, какие функции вы используете здесь, но сон и грех Delphi, похоже, ожидают радианов!

Answer 4

Прежде всего: вам нужны все точки на окружности круга. Если вы используете какой-либо (хороший) алгоритм, а также некоторую встроенную функцию круга, вы получаете действительно все точки, так как окружность связана. Что показывает ваша фотография, между соседними кругами есть отверстия, скажем r = 100 и r = 101. Это так для функций рисования окружности.

Теперь, если вы хотите, чтобы пикселы в пикселе установить, чтобы покрыть все пиксели с увеличивающимся радиусом, вы можете просто использовать следующий подход:

1. Построить набор кружком пикселей, скажем г = 101
2. построить набор кружком пикселя с г = 100
3. Исключить набор из набора

Алгоритм заполненного круга, как правило, более эффективен и проще, чем связанная окружность, поэтому вы не потеряете большую производительность.

Таким образом, вы получаете окружность, которая немного толще, чем 1 px, но этот комплект, несомненно, будет покрывать поверхность растущими радиусами без каких-либо отверстий. Но также может случиться так, что набор, построенный таким образом, имеет перекрывающиеся пиксели с предыдущим набором (r-1), поэтому вы бы знали, что лучше, если вы его протестируете.

PS: Также неясно, как любые тригонометрические функции появляются в вашем коде. Я не знаю ни одного эффективного алгоритма круга, который использует ничего, кроме квадратного корня.