Я использую алгоритм Bresenham circle для быстрого рисования круга. Тем не менее, я также хочу (по просьбе пользователя) нарисовать заполненный круг.
Есть ли быстрый и эффективный способ сделать это? Что-то такое же, что и в Брешенеме?
Язык, который я использую, это C.
setPixel(x0 + x, y0 + y);
setPixel(x0 - x, y0 + y);
и тому подобное, каждый раз, когда вы делаете
lineFrom(x0 - x, y0 + y, x0 + x, y0 + y);
То есть для каждой пары точек (с тем же y), что Bresenham у вас есть plot, вместо этого соединяется с линией.. p >
Просто используйте грубую силу. Этот метод повторяет несколько слишком много пикселей, но использует только целые умножения и дополнения. Вы полностью избегаете сложности Bresenham и возможного узкого места sqrt.
for(int y=-radius; y<=radius; y++)
for(int x=-radius; x<=radius; x++)
if(x*x+y*y <= radius*radius)
setpixel(origin.x+x, origin.y+y);
Здесь грубое руководство С# (не должно быть так сложно получить правильную идею для C) - это "сырая" форма без использования Bresenham для устранения повторяющихся квадратов.
Bitmap bmp = new Bitmap(200, 200);
int r = 50; // radius
int ox = 100, oy = 100; // origin
for (int x = -r; x < r ; x++)
{
int height = (int)Math.Sqrt(r * r - x * x);
for (int y = -height; y < height; y++)
bmp.SetPixel(x + ox, y + oy, Color.Red);
}
bmp.Save(@"c:\users\dearwicker\Desktop\circle.bmp");
Вы можете использовать это:
void DrawFilledCircle(int x0, int y0, int radius)
{
int x = radius;
int y = 0;
int xChange = 1 - (radius << 1);
int yChange = 0;
int radiusError = 0;
while (x >= y)
{
for (int i = x0 - x; i <= x0 + x; i++)
{
SetPixel(i, y0 + y);
SetPixel(i, y0 - y);
}
for (int i = x0 - y; i <= x0 + y; i++)
{
SetPixel(i, y0 + x);
SetPixel(i, y0 - x);
}
y++;
radiusError += yChange;
yChange += 2;
if (((radiusError << 1) + xChange) > 0)
{
x--;
radiusError += xChange;
xChange += 2;
}
}
}
Мне нравится palm3D ответ. Для того, чтобы быть грубой силой, это удивительно быстрое решение. Для замедления работы нет квадратного корня или тригонометрических функций. Его единственной слабостью является вложенный цикл.
Преобразование этого в один цикл делает эту функцию почти в два раза быстрее.
int r2 = r * r;
int area = r2 << 2;
int rr = r << 1;
for (int i = 0; i < area; i++)
{
int tx = (i % rr) - r;
int ty = (i / rr) - r;
if (tx * tx + ty * ty <= r2)
SetPixel(x + tx, y + ty, c);
}
Это одноконтурное решение сравнивает эффективность решения линейного чертежа.
int r2 = r * r;
for (int cy = -r; cy <= r; cy++)
{
int cx = (int)(Math.Sqrt(r2 - cy * cy) + 0.5);
int cyy = cy + y;
lineDDA(x - cx, cyy, x + cx, cyy, c);
}
Вот как я это делаю:
Я использую значения фиксированной точки с точностью до двух битов (нам нужно управлять полутонами и квадратными значениями полутонов)
Как упоминалось в предыдущем ответе, я также использую квадратные значения вместо квадратных корней.
Во-первых, я обнаруживаю границу границы моего круга в 1/8 части круга. Я использую симметричные эти точки, чтобы нарисовать 4 "границы" круга. Затем я рисую квадрат внутри круга.
В отличие от алгоритма окружности окружности, этот будет работать с четными диаметрами (и с реальными диаметрами чисел тоже с небольшими изменениями).
Пожалуйста, простите меня, если мои объяснения не ясны, я французский;)
void DrawFilledCircle(int circleDiameter, int circlePosX, int circlePosY)
{
const int FULL = (1 << 2);
const int HALF = (FULL >> 1);
int size = (circleDiameter << 2);// fixed point value for size
int ray = (size >> 1);
int dY2;
int ray2 = ray * ray;
int posmin,posmax;
int Y,X;
int x = ((circleDiameter&1)==1) ? ray : ray - HALF;
int y = HALF;
circlePosX -= (circleDiameter>>1);
circlePosY -= (circleDiameter>>1);
for (;; y+=FULL)
{
dY2 = (ray - y) * (ray - y);
for (;; x-=FULL)
{
if (dY2 + (ray - x) * (ray - x) <= ray2) continue;
if (x < y)
{
Y = (y >> 2);
posmin = Y;
posmax = circleDiameter - Y;
// Draw inside square and leave
while (Y < posmax)
{
for (X = posmin; X < posmax; X++)
setPixel(circlePosX+X, circlePosY+Y);
Y++;
}
// Just for a better understanding, the while loop does the same thing as:
// DrawSquare(circlePosX+Y, circlePosY+Y, circleDiameter - 2*Y);
return;
}
// Draw the 4 borders
X = (x >> 2) + 1;
Y = y >> 2;
posmax = circleDiameter - X;
int mirrorY = circleDiameter - Y - 1;
while (X < posmax)
{
setPixel(circlePosX+X, circlePosY+Y);
setPixel(circlePosX+X, circlePosY+mirrorY);
setPixel(circlePosX+Y, circlePosY+X);
setPixel(circlePosX+mirrorY, circlePosY+X);
X++;
}
// Just for a better understanding, the while loop does the same thing as:
// int lineSize = circleDiameter - X*2;
// Upper border:
// DrawHorizontalLine(circlePosX+X, circlePosY+Y, lineSize);
// Lower border:
// DrawHorizontalLine(circlePosX+X, circlePosY+mirrorY, lineSize);
// Left border:
// DrawVerticalLine(circlePosX+Y, circlePosY+X, lineSize);
// Right border:
// DrawVerticalLine(circlePosX+mirrorY, circlePosY+X, lineSize);
break;
}
}
}
void DrawSquare(int x, int y, int size)
{
for( int i=0 ; i<size ; i++ )
DrawHorizontalLine(x, y+i, size);
}
void DrawHorizontalLine(int x, int y, int width)
{
for(int i=0 ; i<width ; i++ )
SetPixel(x+i, y);
}
void DrawVerticalLine(int x, int y, int height)
{
for(int i=0 ; i<height ; i++ )
SetPixel(x, y+i);
}
Чтобы использовать нецелый диаметр, вы можете увеличить точность фиксированной точки или использовать двойные значения. Также возможно сделать какой-то антиалиас в зависимости от разницы между dY2 + (ray-x) * (ray-x) и ray2 (dx² + dy² и r²)
Если вы хотите быстрый алгоритм, рассмотрите рисование многоугольника с N сторонами, чем выше N, тем точнее будет круг.
Я бы просто сгенерировал список точек, а затем использовал функцию рисования многоугольника для рендеринга.