Алгоритм рисования среднего круга

Опубликовано: 19 Января, 2022

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

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

Алгоритм очень похож на алгоритм генерации средней точки. Здесь отличается только граничное условие.

Для любого заданного пикселя (x, y) следующий пиксель, который должен быть нанесен, будет либо (x, y + 1), либо (x-1, y + 1) . Это можно решить, выполнив следующие действия.

  1. Найдите среднюю точку p двух возможных пикселей, т.е. (x-0,5, y + 1)
  2. Если p лежит внутри или на периметре круга, мы рисуем пиксель (x, y + 1), в противном случае, если он снаружи, мы рисуем пиксель (x-1, y + 1)

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

Given a circle centered at (0,0) and radius r and a point p(x,y)
F(p) = x2 + y2 – r2

if F(p)<0, the point is inside the circle

F(p)=0, the point is on the perimeter

F(p)>0, the point is outside the circle

В нашей программе мы обозначаем F (p) через P. Значение P вычисляется в средней точке двух конкурирующих пикселей, то есть (x-0,5, y + 1). Каждый пиксель описывается индексом k.

Pk = (Xk — 0.5)2 + (yk + 1)2 – r2

Now,
xk+1 = xk or xk-1 , yk+1= yk +1

∴ Pk+1 = (xk+1 – 0.5)2 + (yk+1 +1)2 – r2
= (xk+1 – 0.5)2 + [(yk +1) + 1]2 – r2
= (xk+1 – 0.5)2 + (yk +1)2 + 2(yk + 1) + 1 – r2
= (xk+1 – 0.5)2 + [ – (xk – 0.5)2 +(xk – 0.5)2 ] + (yk + 1)2 – r2 + (yk + 1) + 1



= Pk + (xk+1 – 0.5)2 – (xk – 0.5)2 + 2(yk + 1) + 1
= Pk + (x2k+1 – x2k)2 + (xk+1 – xk)2 + 2(yk + 1) + 1
= Pk + 2(yk +1) + 1, when Pk <=0 i.e the midpoint is inside the circle
(xk+1 = xk)
Pk + 2(yk +1) – 2(xk – 1) + 1, when Pk>0 I.e the mid point is outside the circle(xk+1 = xk-1)

Первая точка, которую нужно построить, - это (r, 0) на оси x. Начальное значение P рассчитывается следующим образом: -

P1 = (r – 0.5)2 + (0+1)2 – r2
= 1.25 – r
= 1 -r (When rounded off)

Examples:

Input : Centre -> (0, 0), Radius -> 3
Output : (3, 0) (3, 0) (0, 3) (0, 3)
         (3, 1) (-3, 1) (3, -1) (-3, -1)
         (1, 3) (-1, 3) (1, -3) (-1, -3)
         (2, 2) (-2, 2) (2, -2) (-2, -2)


Input : Centre -> (4, 4), Radius -> 2
Output : (6, 4) (6, 4) (4, 6) (4, 6)
         (6, 5) (2, 5) (6, 3) (2, 3)
         (5, 6) (3, 6) (5, 2) (3, 2)

C

// C program for implementing
// Mid-Point Circle Drawing Algorithm
#include<stdio.h>
  
// Implementing Mid-Point Circle Drawing Algorithm
void midPointCircleDraw(int x_centre, int y_centre, int r)
{
    int x = r, y = 0;
      
    // Printing the initial point on the axes 
    // after translation
    printf("(%d, %d) ", x + x_centre, y + y_centre);
      
    // When radius is zero only a single
    // point will be printed
    if (r > 0)
    {
        printf("(%d, %d) ", x + x_centre, -y + y_centre);
        printf("(%d, %d) ", y + x_centre, x + y_centre);
        printf("(%d, %d) ", -y + x_centre, x + y_centre);
    }
      
    // Initialising the value of P
    int P = 1 - r;
    while (x > y)
    { 
        y++;
          
        // Mid-point is inside or on the perimeter
        if (P <= 0)
            P = P + 2*y + 1;
              
        // Mid-point is outside the perimeter
        else
        {
            x--;
            P = P + 2*y - 2*x + 1;
        }
          
        // All the perimeter points have already been printed
        if (x < y)
            break;
          
        // Printing the generated point and its reflection
        // in the other octants after translation
        printf("(%d, %d) ", x + x_centre, y + y_centre);
        printf("(%d, %d) ", -x + x_centre, y + y_centre);
        printf("(%d, %d) ", x + x_centre, -y + y_centre);
        printf("(%d, %d) ", -x + x_centre, -y + y_centre);
          
        // If the generated point is on the line x = y then 
        // the perimeter points have already been printed
        if (x != y)
        {
            printf("(%d, %d) ", y + x_centre, x + y_centre);
            printf("(%d, %d) ", -y + x_centre, x + y_centre);
            printf("(%d, %d) ", y + x_centre, -x + y_centre);
            printf("(%d, %d) ", -y + x_centre, -x + y_centre);
        }
    } 
}
  
// Driver code
int main()
{
    // To draw a circle of radius 3 centred at (0, 0)
    midPointCircleDraw(0, 0, 3);
    return 0;
}

CPP

// C++ program for implementing
// Mid-Point Circle Drawing Algorithm
#include<iostream>
using namespace std;
  
// Implementing Mid-Point Circle Drawing Algorithm
void midPointCircleDraw(int x_centre, int y_centre, int r)
{
    int x = r, y = 0;
      
    // Printing the initial point on the axes 
    // after translation
    cout << "(" << x + x_centre << ", " << y + y_centre << ") ";
      
    // When radius is zero only a single
    // point will be printed
    if (r > 0)
    {
        cout << "(" << x + x_centre << ", " << -y + y_centre << ") ";
        cout << "(" << y + x_centre << ", " << x + y_centre << ") ";
        cout << "(" << -y + x_centre << ", " << x + y_centre << ") ";
    }
      
    // Initialising the value of P
    int P = 1 - r;
    while (x > y)
    { 
        y++;
          
        // Mid-point is inside or on the perimeter
        if (P <= 0)
            P = P + 2*y + 1;
        // Mid-point is outside the perimeter
        else
        {
            x--;
            P = P + 2*y - 2*x + 1;
        }
          
        // All the perimeter points have already been printed
        if (x < y)
            break;
          
        // Printing the generated point and its reflection
        // in the other octants after translation
        cout << "(" << x + x_centre << ", " << y + y_centre << ") ";
        cout << "(" << -x + x_centre << ", " << y + y_centre << ") ";
        cout << "(" << x + x_centre << ", " << -y + y_centre << ") ";
        cout << "(" << -x + x_centre << ", " << -y + y_centre << ") ";
          
        // If the generated point is on the line x = y then 
        // the perimeter points have already been printed
        if (x != y)
        {
            cout << "(" << y + x_centre << ", " << x + y_centre << ") ";
            cout << "(" << -y + x_centre << ", " << x + y_centre << ") ";
            cout << "(" << y + x_centre << ", " << -x + y_centre << ") ";
            cout << "(" << -y + x_centre << ", " << -x + y_centre << ") ";
        }
    }
}
  
// Driver code
int main()
{
    // To draw a circle of radius 3 centred at (0, 0)
    midPointCircleDraw(0, 0, 3);
    return 0;
}

Java

// Java program for implementing
// Mid-Point Circle Drawing Algorithm
class GFG {
      
    // Implementing Mid-Point Circle
    // Drawing Algorithm
    static void midPointCircleDraw(int x_centre, 
                            int y_centre, int r) 
    {
          
        int x = r, y = 0;
      
        // Printing the initial point
        // on the axes after translation
        System.out.print("(" + (x + x_centre) 
                + ", " + (y + y_centre) + ")");
      
        // When radius is zero only a single
        // point will be printed
        if (r > 0) {
              
            System.out.print("(" + (x + x_centre) 
                + ", " + (-y + y_centre) + ")");
                  
            System.out.print("(" + (y + x_centre) 
                 + ", " + (x + y_centre) + ")");
                   
            System.out.println("(" + (-y + x_centre)
                   + ", " + (x + y_centre) + ")");
        }
      
        // Initialising the value of P
        int P = 1 - r;
        while (x > y) {
              
            y++;
          
            // Mid-point is inside or on the perimeter
            if (P <= 0)
                P = P + 2 * y + 1;
          
            // Mid-point is outside the perimeter
            else {
                x--;
                P = P + 2 * y - 2 * x + 1;
            }
          
            // All the perimeter points have already 
            // been printed
            if (x < y)
                break;
          
            // Printing the generated point and its 
            // reflection in the other octants after
            // translation
            System.out.print("(" + (x + x_centre) 
                    + ", " + (y + y_centre) + ")");
                      
            System.out.print("(" + (-x + x_centre) 
                    + ", " + (y + y_centre) + ")");
                      
            System.out.print("(" + (x + x_centre) + 
                    ", " + (-y + y_centre) + ")");
                      
            System.out.println("(" + (-x + x_centre) 
                    + ", " + (-y + y_centre) + ")");
          
            // If the generated point is on the 
            // line x = y then the perimeter points
            // have already been printed
            if (x != y) {
                  
                System.out.print("(" + (y + x_centre)
                      + ", " + (x + y_centre) + ")");
                        
                System.out.print("(" + (-y + x_centre) 
                      + ", " + (x + y_centre) + ")");
                        
                System.out.print("(" + (y + x_centre) 
                      + ", " + (-x + y_centre) + ")");
                        
                System.out.println("(" + (-y + x_centre) 
                    + ", " + (-x + y_centre) +")");
            }
        }
    }
      
    // Driver code
    public static void main(String[] args) {
          
        // To draw a circle of radius 
        // 3 centred at (0, 0)
        midPointCircleDraw(0, 0, 3);
    }
}
  
// This code is contributed by Anant Agarwal.

Python3

# Python3 program for implementing 
# Mid-Point Circle Drawing Algorithm 
  
def midPointCircleDraw(x_centre, y_centre, r):
    x = r
    y = 0
      
    # Printing the initial point the 
    # axes after translation 
    print("(", x + x_centre, ", ", 
               y + y_centre, ")", 
               sep = "", end = "") 
      
    # When radius is zero only a single 
    # point be printed 
    if (r > 0) :
      
        print("(", x + x_centre, ", ",
                  -y + y_centre, ")", 
                  sep = "", end = "") 
        print("(", y + x_centre, ", ", 
                   x + y_centre, ")",
                   sep = "", end = "") 
        print("(", -y + x_centre, ", ", 
                    x + y_centre, ")", sep = "") 
      
    # Initialising the value of P 
    P = 1 - r 
  
    while x > y:
      
        y += 1
          
        # Mid-point inside or on the perimeter
        if P <= 0: 
            P = P + 2 * y + 1
              
        # Mid-point outside the perimeter 
        else:         
            x -= 1
            P = P + 2 * y - 2 * x + 1
          
        # All the perimeter points have 
        # already been printed 
        if (x < y):
            break
          
        # Printing the generated point its reflection 
        
Алгоритмы Компьютерная графика

РЕКОМЕНДУЕМЫЕ СТАТЬИ

Разница между жадным алгоритмом и алгоритмом «разделяй и властвуй»
14 Февраля, 2023
Сжатие и распаковка текстовых файлов с использованием кодирования Хаффмана
21 Января, 2023
Введение в амортизированный анализ
12 Января, 2023
Как анализировать сложность рекуррентного отношения
12 Января, 2023
Наихудший, средний и лучший анализ алгоритмов
4 Января, 2023
Лист Google SDE: вопросы и ответы на собеседовании
12 Декабря, 2022
Что такое логарифмическая временная сложность? Полное руководство
12 Декабря, 2022
Amazon SDE Sheet: вопросы и ответы на собеседовании
12 Декабря, 2022