Координаты каждой точки на окружности круга
Во-первых, обратите внимание, что этот вопрос не является дубликатом этих вопросов: 1-й, 2-й и 3-й.
Я использую 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/ окружность круга в пикселях. Но этот подход не очень точен. Чем больше круг, тем меньше должна быть доля угла, и точность страдает от неточности числа Пи плюс округление.
Если я использую упомянутый метод, и пытаюсь нарисовать подсчитанные пиксели с этим кодом:
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%+) пикселей на окружности круга с данным центром и радиусом. Чем быстрее тем лучше...
4 ответа
1) Создайте список пикселей с наименьшим радиусом окружности. Достаточно сохранить первый октант (диапазон 0..Pi/4 в 1-м квадранте системы координат) окружности и получить симметричные точки с отражениями. Вы можете использовать, например, алгоритм круга Брезенхэма или просто уравнение круга.
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;
Если вы хотите сделать свой код быстрее, не вызывайте тригонометрические функции во внутреннем цикле, увеличивайте 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;
Прежде всего: вы хотите, чтобы все точки на окружности окружности. Если вы используете какой-либо (хороший) алгоритм, а также некоторую встроенную функцию окружности, вы получите действительно все точки, так как окружность связана. Как видно из вашей картинки, между соседними кружками есть дыры, скажем, r=100 и r=101. Это так для функций рисования окружности.
Теперь, если вы хотите, чтобы пиксели в вашем пикселе были установлены так, чтобы покрывать все пиксели с увеличивающимися радиусами, вы можете просто использовать следующий подход:
- Создайте набор заполненных пикселей круга, скажем, r = 101
- Создайте набор заполненных круговых пикселей с r=100
- Исключить набор 2 из набора 1
Алгоритм с заполненной окружностью, как правило, более эффективен и проще, чем окружность, поэтому вы не потеряете производительность.
Таким образом, вы получите окружность, которая немного толще, чем 1 px, но этот набор наверняка покроет поверхность растущими радиусами без каких-либо отверстий. Но может также случиться, что набор, построенный таким образом, имеет перекрывающиеся пиксели с предыдущим набором (r-1), так что вы будете знать это лучше, если протестируете его.
PS: Также не ясно, как в вашем коде появляются тригонометрические функции. Я не знаю ни одного эффективного алгоритма окружности, который использовал бы что-либо кроме квадратного корня.
Почему бы вам просто не использовать больше цифр для числа Пи и прекратить округление для повышения точности?
Кроме того, я предлагаю вам использовать субпиксельные координаты, чтобы получить более точные значения интенсивности, если вы можете позволить интерполяцию.
Также очень редко использовать градусы в расчетах. Я настоятельно рекомендую использовать радианы. Не уверен, какие функции вы используете здесь, но Delphi, потому что и грех, кажется, ожидают радианы!