Midpoint Circle Drawing Algorithm in C

The mid-bespeak circle drawing algorithm is an algorithm used to determine the points needed for rasterizing a circumvolve.

We use the mid-signal algorithm to summate all the perimeter points of the circle in the first octant and so print them along with their mirror points in the other octants. This volition work considering a circle is symmetric well-nigh its centre.

The algorithm is very similar to the Mid-Point Line Generation Algorithm. Here, only the boundary status is different.

For whatever given pixel (x, y), the next pixel to exist plotted is either (x, y+1) or (x-1, y+1). This can exist decided by following the steps below.

1. Find the mid-point p of the two possible pixels i.east (ten-0.five, y+1)
2. If p lies inside or on the circle perimeter, we plot the pixel (x, y+1), otherwise if it's outside we plot the pixel (x-i, y+1)

Boundary Status : Whether the mid-bespeak lies within or outside the circumvolve tin exist decided past using the formula:-

Given a circle centered at (0,0) and radius r and a signal p(ten,y)
F(p) = x² + y² – r^two
if F(p)<0, the signal is inside the circle
F(p)=0, the point is on the perimeter
F(p)>0, the bespeak is outside the circle

In our program, we announce F(p) with P. The value of P is calculated at the mid-bespeak of the two contending pixels i.e. (x-0.5, y+ane). Each pixel is described with a subscript k.

P₁₀₀₀ = (X_k — 0.5)² + (y_g + 1)² – r²
At present,
ten_k+i = 10_k or ten_1000-one , y_m+i= y₁₀₀₀ +1
∴ P_yard+1 = (ten_k+1 – 0.5)² + (y_thou+1 +ane)² – r²
= (x_k+1 – 0.5)² + [(y_k +i) + 1]² – r²
= (x_{one thousand+i} – 0.5)^two + (y_k +1)^two + 2(y_k + 1) + 1 – r²
= (10_k+1 – 0.5)ⁱⁱ + [ – (x_thou – 0.5)² +(x_m – 0.5)^two ] + (y_k + i)² – r^two + ii(y_k + 1) + one
= P_k + (10_k+i – 0.5)² – (x_k – 0.v)² + 2(y_k + 1) + i
= P_{one thousand} + (tenⁱⁱ _k+i – ten^two _k) – (x_chiliad+1 – x_{one thousand}) + ii(y_thousand + 1) + i
= P_k + 2(y_{one thousand} +1) + one, when P_k <=0 i.e the midpoint is inside the circle
(x_yard+1 = ten_k)
P_k + 2(y_k +1) – 2(x_yard – 1) + 1, when P_k>0 I.east the mid point is exterior the circumvolve(x_g+ane = ten_thou-1)

The first point to be plotted is (r, 0) on the x-centrality. The initial value of P is calculated as follows:-

P1 = (r – 0.v)² + (0+1)² – r^two
= i.25 – r
= ane -r (When rounded off)

Examples:

          Input :          Middle -> (0, 0), Radius -> 3          Output :          (3, 0) (three, 0) (0, 3) (0, iii)          (3, one) (-iii, ane) (iii, -i) (-three, -one)          (1, three) (-1, iii) (one, -3) (-1, -3)          (2, ii) (-2, two) (2, -2) (-2, -2)

          Input :          Centre -> (4, 4), Radius -> 2          Output :          (6, 4) (half-dozen, 4) (four, 6) (4, half dozen)          (6, 5) (ii, 5) (6, three) (2, iii)          (five, 6) (3, 6) (5, 2) (3, 2)

CPP

#include<iostream>

using namespace std;

void midPointCircleDraw( int x_centre, int y_centre, int r)

{

int x = r, y = 0;

cout << "(" << x + x_centre << ", " << y + y_centre << ") " ;

if (r > 0)

{

cout << "(" << x + x_centre << ", " << -y + y_centre << ") " ;

cout << "(" << y + x_centre << ", " << x + y_centre << ") " ;

cout << "(" << -y + x_centre << ", " << ten + y_centre << ")\n" ;

}

int P = 1 - r;

while (x > y)

{

y++;

if (P <= 0)

P = P + 2*y + 1;

else

{

x--;

P = P + two*y - 2*10 + ane;

}

if (x < y)

break ;

cout << "(" << x + x_centre << ", " << y + y_centre << ") " ;

cout << "(" << -ten + x_centre << ", " << y + y_centre << ") " ;

cout << "(" << x + x_centre << ", " << -y + y_centre << ") " ;

cout << "(" << -10 + x_centre << ", " << -y + y_centre << ")\due north" ;

if (x != y)

{

cout << "(" << y + x_centre << ", " << ten + y_centre << ") " ;

cout << "(" << -y + x_centre << ", " << x + y_centre << ") " ;

cout << "(" << y + x_centre << ", " << -x + y_centre << ") " ;

cout << "(" << -y + x_centre << ", " << -x + y_centre << ")\n" ;

}

}

}

int main()

{

midPointCircleDraw(0, 0, 3);

render 0;

}

C

#include<stdio.h>

void midPointCircleDraw( int x_centre, int y_centre, int r)

{

int ten = r, y = 0;

printf ( "(%d, %d) " , x + x_centre, y + y_centre);

if (r > 0)

{

printf ( "(%d, %d) " , x + x_centre, -y + y_centre);

printf ( "(%d, %d) " , y + x_centre, x + y_centre);

printf ( "(%d, %d)\northward" , -y + x_centre, ten + y_centre);

}

int P = i - r;

while (x > y)

{

y++;

if (P <= 0)

P = P + 2*y + one;

else

{

10--;

P = P + 2*y - ii*x + one;

}

if (ten < y)

break ;

printf ( "(%d, %d) " , ten + 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 (x != y)

{

printf ( "(%d, %d) " , y + x_centre, x + y_centre);

printf ( "(%d, %d) " , -y + x_centre, ten + y_centre);

printf ( "(%d, %d) " , y + x_centre, -x + y_centre);

printf ( "(%d, %d)\due north" , -y + x_centre, -x + y_centre);

}

}

}

int primary()

{

midPointCircleDraw(0, 0, 3);

return 0;

}

Java

class GFG {

static void midPointCircleDraw( int x_centre,

int y_centre, int r)

{

int 10 = r, y = 0 ;

System.out.print( "(" + (10 + x_centre)

+ ", " + (y + y_centre) + ")" );

if (r > 0 ) {

System.out.impress( "(" + (x + x_centre)

+ ", " + (-y + y_centre) + ")" );

System.out.print( "(" + (y + x_centre)

+ ", " + (ten + y_centre) + ")" );

Organisation.out.println( "(" + (-y + x_centre)

+ ", " + (x + y_centre) + ")" );

}

int P = 1 - r;

while (x > y) {

y++;

if (P <= 0 )

P = P + ii * y + 1 ;

else {

x--;

P = P + 2 * y - 2 * x + 1 ;

}

if (ten < y)

break ;

System.out.impress( "(" + (x + x_centre)

+ ", " + (y + y_centre) + ")" );

System.out.print( "(" + (-10 + x_centre)

+ ", " + (y + y_centre) + ")" );

System.out.impress( "(" + (10 + x_centre) +

", " + (-y + y_centre) + ")" );

System.out.println( "(" + (-x + x_centre)

+ ", " + (-y + y_centre) + ")" );

if (x != y) {

Organisation.out.print( "(" + (y + x_centre)

+ ", " + (ten + y_centre) + ")" );

Arrangement.out.impress( "(" + (-y + x_centre)

+ ", " + (x + y_centre) + ")" );

System.out.print( "(" + (y + x_centre)

+ ", " + (-x + y_centre) + ")" );

Arrangement.out.println( "(" + (-y + x_centre)

+ ", " + (-x + y_centre) + ")" );

}

}

}

public static void chief(String[] args) {

midPointCircleDraw( 0 , 0 , 3 );

}

}

Python3

def midPointCircleDraw(x_centre, y_centre, r):

x = r

y = 0

print ( "(" , x + x_centre, ", " ,

y + y_centre, ")" ,

sep = " ", end = " ")

if (r > 0 ) :

impress ( "(" , 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 = "")

P = 1 - r

while 10 > y:

y + = 1

if P < = 0 :

P = P + 2 * y + one

else :

x - = 1

P = P + 2 * y - 2 * x + 1

if (x < y):

break

print ( "(" , x + x_centre, ", " , y + y_centre,

")" , sep = " ", finish = " ")

impress ( "(" , - x + x_centre, ", " , y + y_centre,

")" , sep = " ", end = " ")

print ( "(" , 10 + x_centre, ", " , - y + y_centre,

")" , sep = " ", end = " ")

impress ( "(" , - 10 + x_centre, ", " , - y + y_centre,

")" , sep = "")

if 10 ! = y:

print ( "(" , y + x_centre, ", " , x + y_centre,

")" , sep = " ", end = " ")

print ( "(" , - y + x_centre, ", " , x + y_centre,

")" , sep = " ", cease = " ")

impress ( "(" , y + x_centre, ", " , - x + y_centre,

")" , sep = " ", end = " ")

print ( "(" , - y + x_centre, ", " , - x + y_centre,

")" , sep = "")

if __name__ = = '__main__' :

midPointCircleDraw( 0 , 0 , three )

C#

using System;

class GFG {

static void midPointCircleDraw( int x_centre,

int y_centre, int r)

{

int x = r, y = 0;

Panel.Write( "(" + (x + x_centre)

+ ", " + (y + y_centre) + ")" );

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) + ")" );

}

int P = 1 - r;

while (10 > y)

{

y++;

if (P <= 0)

P = P + two * y + 1;

else

{

10--;

P = P + two * y - two * ten + one;

}

if (x < y)

interruption ;

Console.Write( "(" + (ten + 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 (10 != y)

{

Panel.Write( "(" + (y + x_centre)

+ ", " + (x + y_centre) + ")" );

Console.Write( "(" + (-y + x_centre)

+ ", " + (x + y_centre) + ")" );

Console.Write( "(" + (y + x_centre)

+ ", " + (-10 + y_centre) + ")" );

Panel.WriteLine( "(" + (-y + x_centre)

+ ", " + (-x + y_centre) + ")" );

}

}

}

public static void Main()

{

midPointCircleDraw(0, 0, 3);

}

}

PHP

<?php

function midPointCircleDraw( $x_centre ,

$y_centre ,

$r )

{

$10 = $r ;

$y = 0;

echo "(" , $x + $x_centre , "," , $y + $y_centre , ")" ;

if ( $r > 0)

{

echo "(" , $x + $x_centre , "," , - $y + $y_centre , ")" ;

echo "(" , $y + $x_centre , "," , $x + $y_centre , ")" ;

echo "(" ,- $y + $x_centre , "," , $ten + $y_centre , ")" , "\n" ;

}

$P = 1 - $r ;

while ( $x > $y )

{

$y ++;

if ( $P <= 0)

$P = $P + 2 * $y + 1;

else

{

$x --;

$P = $P + two * $y -

2 * $x + 1;

}

if ( $x < $y )

pause ;

echo "(" , $ten + $x_centre , "," , $y + $y_centre , ")" ;

repeat "(" ,- $x + $x_centre , "," , $y + $y_centre , ")" ;

repeat "(" , $x + $x_centre , "," , - $y + $y_centre , ")" ;

echo "(" ,- $x + $x_centre , "," , - $y + $y_centre , ")" , "\n" ;

if ( $x != $y )

{

echo "(" , $y + $x_centre , "," , $x + $y_centre , ")" ;

repeat "(" ,- $y + $x_centre , "," , $x + $y_centre , ")" ;

repeat "(" , $y + $x_centre , "," , - $x + $y_centre , ")" ;

repeat "(" ,- $y + $x_centre , "," , - $10 + $y_centre , ")" , "\n" ;

}

}

}

midPointCircleDraw(0, 0, three);

?>

Javascript

<script>

part midPointCircleDraw(x_centre , y_centre , r) {

var x = r, y = 0;

certificate.write( "(" + (10 + x_centre) + ", " + (y + y_centre) + ")" );

if (r > 0) {

document.write( "(" + (x + x_centre) + ", " + (-y + y_centre) + ")" );

document.write( "(" + (y + x_centre) + ", " + (ten + y_centre) + ")" );

certificate.write( "(" + (-y + x_centre) + ", " + (ten + y_centre) + ")<br/>" );

}

var P = i - r;

while (x > y) {

y++;

if (P <= 0)

P = P + 2 * y + 1;

else {

x--;

P = P + ii * y - 2 * x + 1;

}

if (x < y)

break ;

document.write( "(" + (x + x_centre) + ", " + (y + y_centre) + ")" );

document.write( "(" + (-x + x_centre) + ", " + (y + y_centre) + ")" );

certificate.write( "(" + (10 + x_centre) + ", " + (-y + y_centre) + ")" );

certificate.write( "(" + (-x + x_centre) + ", " + (-y + y_centre) + ")<br/>" );

if (ten != y) {

document.write( "(" + (y + x_centre) + ", " + (x + y_centre) + ")" );

document.write( "(" + (-y + x_centre) + ", " + (ten + y_centre) + ")" );

document.write( "(" + (y + x_centre) + ", " + (-ten + y_centre) + ")" );

document.write( "(" + (-y + x_centre) + ", " + (-x + y_centre) + ")<br/>" );

}

}

}

midPointCircleDraw(0, 0, three);

</script>

Output:

(3, 0) (3, 0) (0, 3) (0, three) (3, 1) (-3, one) (3, -1) (-3, -one) (1, three) (-ane, iii) (1, -three) (-1, -3) (2, 2) (-2, 2) (2, -2) (-2, -2)

Time Complexity: O(10 – y)
Auxiliary Space: O(1)
References : Midpoint Circle Algorithm
Prototype References : Octants of a circle, Rasterised Circle, the other images were created for this article by the geek
Thank you Tuhina Singh and Teva Zanker for improving this article.
This article is contributed by Nabaneet Roy. If you lot like GeeksforGeeks and would like to contribute, you tin besides write an commodity using write.geeksforgeeks.org or post your article to review-team@geeksforgeeks.org. See your article appearing on the GeeksforGeeks main folio and help other Geeks.
Delight write comments if you observe anything incorrect, or y'all want to share more information about the topic discussed above.

phippsforrich.blogspot.com

Source: https://www.geeksforgeeks.org/mid-point-circle-drawing-algorithm/

Share this post