El algoritmo de dibujo de círculo de punto medio es un algoritmo utilizado para determinar los puntos necesarios para rasterizar un círculo.
Usamos el algoritmo del punto medio para calcular todos los puntos del perímetro del círculo en el primer octante y luego los imprimimos junto con sus puntos de espejo en los otros octantes. Esto funcionará porque un círculo es simétrico con respecto a su centro.
El algoritmo es muy similar al algoritmo de generación de línea de punto medio . Aquí, solo la condición de contorno es diferente.
Para cualquier píxel dado (x, y), el siguiente píxel a trazar es (x, y+1) o (x-1, y+1) . Esto se puede decidir siguiendo los pasos a continuación.
- Encuentre el punto medio p de los dos píxeles posibles, es decir (x-0.5, y+1)
- Si p está dentro o en el perímetro del círculo, trazamos el píxel (x, y+1), de lo contrario, si está fuera, trazamos el píxel (x-1, y+1)
Condición de contorno: se puede decidir si el punto medio se encuentra dentro o fuera del círculo mediante la fórmula:
Dado un círculo con centro en (0,0) y radio r y un punto p(x,y)
F(p) = x 2 + y 2 – r 2
si F(p)<0, el punto está dentro del círculo
F (p)=0, el punto está en el perímetro
F(p)>0, el punto está fuera del círculo
En nuestro programa, denotamos F(p) con P. El valor de P se calcula en el punto medio de los dos píxeles contendientes, es decir (x-0.5, y+1). Cada píxel se describe con un subíndice k.
P k = (X k — 0.5) 2 + (y k + 1) 2 – r 2
Ahora,
x k+1 = x k o x k-1 , y k+1 = y k +1
∴ P k+1 = (x k+1 – 0,5) 2 + (y k+1 +1) 2 – r 2
= (x k+1 – 0,5) 2 + [(y k +1) + 1] 2 – r 2
= ( x k+1 – 0.5) 2 + (y k +1)2 + 2(y k + 1) + 1 – r 2
= (x k+1 – 0,5) 2 + [ – (x k – 0,5) 2 +(x k – 0,5) 2 ] + (y k + 1) 2 – r 2 + 2(y k + 1) + 1
= PAGS k + (x k+1 – 0.5) 2 – (x k – 0.5) 2 + 2(y k + 1) + 1
= PAGS k + ( x 2 k+1 – x 2 k ) – (x k+1 – x k) + 2(y k + 1) + 1
= P k + 2(y k +1) + 1, cuando P k <=0 es decir, el punto medio está dentro del círculo
(x k+1 = x k )
P k + 2(y k +1) – 2(x k – 1) + 1, cuando P k >0 Es decir, el punto medio está fuera del círculo (x k+1 = x k -1)
El primer punto a trazar es (r, 0) en el eje x. El valor inicial de P se calcula de la siguiente manera:
P1 = (r – 0,5) 2 + (0+1) 2 – r 2
= 1,25 – r
= 1 -r (cuando se redondea)
Ejemplos:
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)
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 << ")\n";
}
// 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 << ")\n";
// 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 << ")\n";
}
}
}
// Driver code
int main()
{
// To draw a circle of radius 3 centered at (0, 0)
midPointCircleDraw(0, 0, 3);
return 0;
}
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)\n", -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)\n", -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)\n", -y + x_centre, -x + y_centre);
}
}
}
// Driver code
int main()
{
// To draw a circle of radius 3 centered 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 centered 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
# in the other octants after translation
print("(", x + x_centre, ", ", y + y_centre,
")", sep = "", end = "")
print("(", -x + x_centre, ", ", y + y_centre,
")", sep = "", end = "")
print("(", x + x_centre, ", ", -y + y_centre,
")", sep = "", end = "")
print("(", -x + x_centre, ", ", -y + y_centre,
")", sep = "")
# If the generated point on the line x = y then
# the perimeter points have already been printed
if x != y:
print("(", y + x_centre, ", ", x + y_centre,
")", sep = "", end = "")
print("(", -y + x_centre, ", ", x + y_centre,
")", sep = "", end = "")
print("(", y + x_centre, ", ", -x + y_centre,
")", sep = "", end = "")
print("(", -y + x_centre, ", ", -x + y_centre,
")", sep = "")
# Driver Code
if __name__ == '__main__':
# To draw a circle of radius 3
# centered at (0, 0)
midPointCircleDraw(0, 0, 3)
# Contributed by: SHUBHAMSINGH10
# Improved by: siddharthx_07
C#
// C# program for implementing Mid-Point
// Circle Drawing Algorithm
using System;
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
Console.Write("(" + (x + x_centre)
+ ", " + (y + y_centre) + ")");
// When radius is zero only a single
// point will be printed
if (r > 0)
{
Console.Write("(" + (x + x_centre)
+ ", " + (-y + y_centre) + ")");
Console.Write("(" + (y + x_centre)
+ ", " + (x + y_centre) + ")");
Console.WriteLine("(" + (-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
Console.Write("(" + (x + x_centre)
+ ", " + (y + y_centre) + ")");
Console.Write("(" + (-x + x_centre)
+ ", " + (y + y_centre) + ")");
Console.Write("(" + (x + x_centre) +
", " + (-y + y_centre) + ")");
Console.WriteLine("(" + (-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)
{
Console.Write("(" + (y + x_centre)
+ ", " + (x + y_centre) + ")");
Console.Write("(" + (-y + x_centre)
+ ", " + (x + y_centre) + ")");
Console.Write("(" + (y + x_centre)
+ ", " + (-x + y_centre) + ")");
Console.WriteLine("(" + (-y + x_centre)
+ ", " + (-x + y_centre) +")");
}
}
}
// Driver code
public static void Main()
{
// To draw a circle of radius
// 3 centered at (0, 0)
midPointCircleDraw(0, 0, 3);
}
}
// This code is contributed by nitin mittal.
PHP
<?php
// PHP program for implementing
// Mid-Point Circle Drawing Algorithm
// Implementing Mid-Point
// Circle Drawing Algorithm
function midPointCircleDraw($x_centre,
$y_centre,
$r)
{
$x = $r;
$y = 0;
// Printing the initial
// point on the axes
// after translation
echo "(",$x + $x_centre,",", $y + $y_centre,")";
// When radius is zero only a single
// point will be printed
if ($r > 0)
{
echo "(",$x + $x_centre,",", -$y + $y_centre,")";
echo "(",$y + $x_centre,",", $x + $y_centre,")";
echo "(",-$y + $x_centre,",", $x + $y_centre,")","\n";
}
// Initializing the value of P
$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
echo "(",$x + $x_centre,",", $y + $y_centre,")";
echo "(",-$x + $x_centre,",", $y + $y_centre,")";
echo "(",$x +$x_centre,",", -$y + $y_centre,")";
echo "(",-$x + $x_centre,",", -$y + $y_centre,")","\n";
// If the generated point is
// on the line x = y then
// the perimeter points have
// already been printed
if ($x != $y)
{
echo "(",$y + $x_centre,",", $x + $y_centre,")";
echo "(",-$y + $x_centre,",", $x + $y_centre,")";
echo "(",$y + $x_centre,",", -$x + $y_centre,")";
echo "(",-$y + $x_centre,",", -$x + $y_centre,")","\n";
}
}
}
// Driver code
// To draw a circle of radius
// 3 centered at (0, 0)
midPointCircleDraw(0, 0, 3);
// This code is contributed by nitin mittal.
?>
Javascript
<script>
// javascript program for implementing
// Mid-Point Circle Drawing Algorithm
// Implementing Mid-Point Circle
// Drawing Algorithm
function midPointCircleDraw(x_centre , y_centre , r) {
var x = r, y = 0;
// Printing the initial point
// on the axes after translation
document.write("(" + (x + x_centre) + ", " + (y + y_centre) + ")");
// When radius is zero only a single
// point will be printed
if (r > 0) {
document.write("(" + (x + x_centre) + ", " + (-y + y_centre) + ")");
document.write("(" + (y + x_centre) + ", " + (x + y_centre) + ")");
document.write("(" + (-y + x_centre) + ", " + (x + y_centre) + ")<br/>");
}
// Initialising the value of P
var 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
document.write("(" + (x + x_centre) + ", " + (y + y_centre) + ")");
document.write("(" + (-x + x_centre) + ", " + (y + y_centre) + ")");
document.write("(" + (x + x_centre) + ", " + (-y + y_centre) + ")");
document.write("(" + (-x + x_centre) + ", " + (-y + y_centre) + ")<br/>");
// If the generated point is on the
// line x = y then the perimeter points
// have already been printed
if (x != y) {
document.write("(" + (y + x_centre) + ", " + (x + y_centre) + ")");
document.write("(" + (-y + x_centre) + ", " + (x + y_centre) + ")");
document.write("(" + (y + x_centre) + ", " + (-x + y_centre) + ")");
document.write("(" + (-y + x_centre) + ", " + (-x + y_centre) + ")<br/>");
}
}
}
// Driver code
// To draw a circle of radius
// 3 centered at (0, 0)
midPointCircleDraw(0, 0, 3);
// This code is contributed by umadevi9616
</script>
Producción:
(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)
Complejidad de tiempo: O(x – y)
Espacio auxiliar: O(1)
Referencias: Algoritmo de círculo de punto medio
Referencias de imagen: octantes de un círculo , círculo rasterizado , las otras imágenes fueron creadas para este artículo por el geek
Gracias Tuhina Singh y Teva Zanker por mejorando este artículo.
Este artículo es una contribución de Nabaneet Roy . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA