быстрый алгоритм рисования заполненных кругов?

Question

Я использую Bresenham's circle algorithm для быстрого рисования круга. Тем не менее, я также хочу (по просьбе пользователя) нарисовать заполненный круг.

Есть ли быстрый и эффективный способ сделать это? Что-то такое же, что и у Брешенема?

языка я использую C.

Answer 1

Начитавшись the Wikipedia page on Bresenham's (also 'Midpoint') circle algorithm, казалось бы, что проще всего сделать было бы изменить свои действия, таким образом, что вместо

setPixel(x0 + x, y0 + y); 
setPixel(x0 - x, y0 + y); 

и подобные, каждый раз, когда вы вместо того, чтобы сделать

lineFrom(x0 - x, y0 + y, x0 + x, y0 + y); 

То есть для каждой пары точек (с тем же y), что Bresenham у вас есть у вас участок, вы вместо этого подключитесь к строке.

Answer 2

Вот C# грубое руководство (не должно быть трудно получить правильное представление для 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"); 

Answer 3

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

Answer 4

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

Answer 5

Если вы хотите быстрый алгоритм, рассмотрим рисование многоугольника с N сторон, тем выше N, тем точнее будет круг.

Answer 6

Вот как я это делаю:
Я использую значение с фиксированной точкой с точностью два бита (мы должны управлять половину точками и квадратных значениями половины точек)
Как упоминался в предыдущем ответе, я m также используя квадратные значения вместо квадратных корней.
Во-первых, я определяю границу границы своего круга в 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 + (луч - x) * (луч - x) и ray2 (dx² + dy² и r²) должно быть возможно сделать какой-то антиалиас

Answer 7

Вы можете использовать это:

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; 
     } 
    } 
} 

Answer 8

Мне нравится ладонь3D. Для того, чтобы быть грубой силой, это удивительно быстрое решение. Для замедления работы нет квадратного корня или тригонометрических функций. Его единственной слабостью является вложенный цикл.

Преобразование этого в один цикл делает эту функцию почти в два раза быстрее.

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); 
      }