Midpoint Circle Algorithm and Mid-Point Ellipse Drawing Algorithm: Derivation and Worked Examples

"Draw a circle using the midpoint circle algorithm" and "draw the ellipse with rx = 6, ry = 8" are two of the most predictable numericals in TU BSc CSIT Computer Graphics (CSC214), unit 2 "Scan Conversion Algorithm", and in BIT Computer Graphics (BIT304), unit 3 "Line and Circle Drawing Algorithms". Both questions are solved by filling a table of decision parameters, so accuracy with the arithmetic matters more than the theory.

This guide gives the circle drawing algorithm in computer graphics in its midpoint form, a worked circle for $r = 10$ , then the mid-point ellipse drawing algorithm with its two regions and a worked ellipse for $r_x = 6$ , $r_y = 8$ . It ends with how to shift the result to a centre such as $(15, 10)$ . Notes for the unit are on the CSC214 Scan Conversion Algorithm page and the BIT304 Line and Circle Drawing Algorithms page.

Why the midpoint circle algorithm

A circle of radius $r$ centred at the origin satisfies $x^2 + y^2 = r^2$ . Solving for y with a square root at every pixel is slow, and stepping x by one unit near the top of the circle leaves gaps where the curve becomes steep. The midpoint algorithm uses only integer additions and exploits eight-way symmetry: if $(x, y)$ is on the circle, so are $(\pm x, \pm y)$ and $(\pm y, \pm x)$ . Only one octant, from $x = 0$ to $x = y$ , has to be computed.

Decision parameter for the circle

Define the circle function

$f(x, y) = x^2 + y^2 - r^2$

which is negative inside the circle, zero on it and positive outside. Suppose pixel $(x_k, y_k)$ was just plotted. In the octant from the top, x increases by 1 each time, and the next pixel is either $(x_k + 1, y_k)$ or $(x_k + 1, y_k - 1)$ . The decision is made by evaluating $f$ at the midpoint between these two candidates:

$p_k = f\left(x_k + 1,\; y_k - \tfrac{1}{2}\right) = (x_k + 1)^2 + \left(y_k - \tfrac{1}{2}\right)^2 - r^2$

If $p_k < 0$ the midpoint is inside the circle, so the upper pixel $y_k$ is closer and is chosen. Otherwise the lower pixel $y_k - 1$ is chosen. Evaluating $p_{k+1}$ and subtracting gives the incremental forms, and the start value at $(0, r)$ is $p_0 = \tfrac{5}{4} - r$ , which is rounded to $1 - r$ because $p$ is only compared with zero and all other terms are integers.

Algorithm

Input the radius $r$ and centre $(x_c, y_c)$ , set $(x_0, y_0) = (0, r)$ and $p_0 = 1 - r$ .
At each $x_k$ , if $p_k < 0$ then the next point is $(x_k + 1, y_k)$ and $p_{k+1} = p_k + 2x_{k+1} + 1$ .
Otherwise the next point is $(x_k + 1, y_k - 1)$ and $p_{k+1} = p_k + 2x_{k+1} + 1 - 2y_{k+1}$ .
Plot the eight symmetric points, adding $(x_c, y_c)$ to each, and repeat while $x < y$ (continue until $x \ge y$ ).

Worked example: circle with r = 10

Take centre $(0, 0)$ and $r = 10$ . The start point is $(0, 10)$ and $p_0 = 1 - 10 = -9$ . At each row the sign of $p_k$ decides the next point and the update uses the new $x_{k+1}$ (and $y_{k+1}$ when y drops).

k	$p_k$	Next point $(x_{k+1}, y_{k+1})$	Update used
0	-9	(1, 10)	$p + 2(1) + 1 = -6$
1	-6	(2, 10)	$p + 2(2) + 1 = -1$
2	-1	(3, 10)	$p + 2(3) + 1 = 6$
3	6	(4, 9)	$p + 2(4) + 1 - 2(9) = -3$
4	-3	(5, 9)	$p + 2(5) + 1 = 8$
5	8	(6, 8)	$p + 2(6) + 1 - 2(8) = 5$
6	5	(7, 7)	$p + 2(7) + 1 - 2(7) = 6$

The octant ends at $(7, 7)$ because $x \ge y$ there. The points of the first octant are therefore $(0,10), (1,10), (2,10), (3,10), (4,9), (5,9), (6,8), (7,7)$ . Reflecting these through $(\pm y, \pm x)$ and the sign changes gives the full circle, for example $(10, 0)$ , $(9, 4)$ , $(8, 6)$ and $(-7, 7)$ .

Midpoint ellipse drawing algorithm

An ellipse centred at the origin with semi-axes $r_x$ and $r_y$ satisfies

$f(x, y) = r_y^2 x^2 + r_x^2 y^2 - r_x^2 r_y^2 = 0$

and has only four-way symmetry, so one quadrant is computed. The slope of the curve changes from shallower than $-1$ to steeper than $-1$ inside the quadrant, so the quadrant is split into two regions and the roles of x and y swap.

Region 1 runs from $(0, r_y)$ while the slope magnitude is below 1, which holds while $2r_y^2 x < 2r_x^2 y$ . Here x is the unit-step axis. The first parameter and updates are

$p1_0 = r_y^2 - r_x^2 r_y + \tfrac{1}{4} r_x^2$

If $p1_k < 0$ the next point is $(x_k + 1, y_k)$ and $p1_{k+1} = p1_k + 2r_y^2 x_{k+1} + r_y^2$ . Otherwise the next point is $(x_k + 1, y_k - 1)$ and $p1_{k+1} = p1_k + 2r_y^2 x_{k+1} - 2r_x^2 y_{k+1} + r_y^2$ .

Region 2 starts at the last point $(x_0, y_0)$ of region 1 and runs down to $y = 0$ , with y as the unit-step axis. The first parameter is

$p2_0 = r_y^2\left(x_0 + \tfrac{1}{2}\right)^2 + r_x^2 (y_0 - 1)^2 - r_x^2 r_y^2$

If $p2_k > 0$ the next point is $(x_k, y_k - 1)$ and $p2_{k+1} = p2_k - 2r_x^2 y_{k+1} + r_x^2$ . Otherwise the next point is $(x_k + 1, y_k - 1)$ and $p2_{k+1} = p2_k + 2r_y^2 x_{k+1} - 2r_x^2 y_{k+1} + r_x^2$ .

Worked example: ellipse with rx = 6, ry = 8

Here $r_x^2 = 36$ , $r_y^2 = 64$ , $2r_x^2 = 72$ , $2r_y^2 = 128$ . The start point is $(0, 8)$ and

$p1_0 = 64 - 36(8) + 9 = -215$

Region 1 continues while $128x < 72y$ .

k	Point $(x_k, y_k)$	$p1_k$	$128x_k$	$72y_k$	Next point
0	(0, 8)	-215	0	576	(1, 8)
1	(1, 8)	-23	128	576	(2, 8)
2	(2, 8)	297	256	576	(3, 7)
3	(3, 7)	241	384	504	(4, 6)
4	(4, 6)	385	512	432	switch

For example $p1_1 = -215 + 128(1) + 64 = -23$ , and since $p1_2 = -23 + 128(2) + 64 = 297$ is positive the next step lowers y, giving $p1_3 = 297 + 128(3) - 72(7) + 64 = 241$ . At $(4, 6)$ we have $128 \cdot 4 = 512 > 72 \cdot 6 = 432$ , so region 1 ends and $(4, 6)$ is the starting point of region 2.

For region 2 the first parameter is

$p2_0 = 64\left(4.5\right)^2 + 36(5)^2 - 36 \cdot 64 = 1296 + 900 - 2304 = -108$

Since $p2_0 < 0$ the next point is $(5, 5)$ , and $p2_1 = -108 + 128(5) - 72(5) + 36 = 208$ . This is positive, so x stays at 5 and y drops, giving $(5, 4)$ with $p2_2 = 208 - 72(4) + 36 = -44$ . Continuing in the same way the points are $(6, 3)$ , $(6, 2)$ , $(6, 1)$ and $(6, 0)$ , where y reaches 0.

The first-quadrant points are therefore $(0,8), (1,8), (2,8), (3,7), (4,6), (5,5), (5,4), (6,3), (6,2), (6,1), (6,0)$ . The other three quadrants follow by symmetry using $(\pm x, \pm y)$ .

Non-origin centre, such as (15, 10)

The algorithms always run as if the centre were the origin. At the moment of plotting, add the centre to every point: $(x + x_c,\; y + y_c)$ . For the ellipse above moved to centre $(15, 10)$ , the point $(0, 8)$ is plotted as $(15, 18)$ , $(3, 7)$ as $(18, 17)$ and $(6, 0)$ as $(21, 10)$ , together with the mirror points such as $(12, 17)$ and $(15, 2)$ . The same method answers questions such as $r_x = 14$ , $r_y = 10$ centre $(15, 10)$ , where $p1_0 = 100 - 196(10) + 49 = -1811$ , or $r_x = 2$ , $r_y = 4$ centre $(4, 5)$ : only the numbers change, never the procedure.

How to write it in the exam

Start with the circle or ellipse equation, state the decision parameter and its initial value, and give the update rules for each case in a short list. Then draw the table with one row per iteration, mark where region 1 ends in the ellipse, list the points of one octant or quadrant, and finish by stating the symmetric points and the shift by the centre. A neat table earns most of the marks even if one late value slips.

Related methods for lines are covered in the same unit, and the full subject pages are CSC214 Computer Graphics and BIT304 Computer Graphics.

"Draw a circle using the midpoint circle algorithm" and "draw the ellipse with rx = 6, ry = 8" are two of the most predictable numericals in TU BSc CSIT Computer Graphics (CSC214), unit 2 "Scan Conversion Algorithm", and in BIT Computer Graphics (BIT304), unit 3 "Line and Circle Drawing Algorithms". Both questions are solved by filling a table of decision parameters, so accuracy with the arithmetic matters more than the theory.

This guide gives the circle drawing algorithm in computer graphics in its midpoint form, a worked circle for $r = 10$, then the mid-point ellipse drawing algorithm with its two regions and a worked ellipse for $r_x = 6$, $r_y = 8$. It ends with how to shift the result to a centre such as $(15, 10)$. Notes for the unit are on the CSC214 Scan Conversion Algorithm page and the BIT304 Line and Circle Drawing Algorithms page.

Why the midpoint circle algorithm

A circle of radius $r$ centred at the origin satisfies $x^2 + y^2 = r^2$. Solving for y with a square root at every pixel is slow, and stepping x by one unit near the top of the circle leaves gaps where the curve becomes steep. The midpoint algorithm uses only integer additions and exploits eight-way symmetry: if $(x, y)$ is on the circle, so are $(\pm x, \pm y)$ and $(\pm y, \pm x)$. Only one octant, from $x = 0$ to $x = y$, has to be computed.

Decision parameter for the circle

Define the circle function

$$f(x, y) = x^2 + y^2 - r^2$$

which is negative inside the circle, zero on it and positive outside. Suppose pixel $(x_k, y_k)$ was just plotted. In the octant from the top, x increases by 1 each time, and the next pixel is either $(x_k + 1, y_k)$ or $(x_k + 1, y_k - 1)$. The decision is made by evaluating $f$ at the midpoint between these two candidates:

$$p_k = f\left(x_k + 1,; y_k - \tfrac{1}{2}\right) = (x_k + 1)^2 + \left(y_k - \tfrac{1}{2}\right)^2 - r^2$$

If $p_k < 0$ the midpoint is inside the circle, so the upper pixel $y_k$ is closer and is chosen. Otherwise the lower pixel $y_k - 1$ is chosen. Evaluating $p_{k+1}$ and subtracting gives the incremental forms, and the start value at $(0, r)$ is $p_0 = \tfrac{5}{4} - r$, which is rounded to $1 - r$ because $p$ is only compared with zero and all other terms are integers.

Algorithm

Input the radius $r$ and centre $(x_c, y_c)$, set $(x_0, y_0) = (0, r)$ and $p_0 = 1 - r$.
At each $x_k$, if $p_k < 0$ then the next point is $(x_k + 1, y_k)$ and $p_{k+1} = p_k + 2x_{k+1} + 1$.
Otherwise the next point is $(x_k + 1, y_k - 1)$ and $p_{k+1} = p_k + 2x_{k+1} + 1 - 2y_{k+1}$.
Plot the eight symmetric points, adding $(x_c, y_c)$ to each, and repeat while $x < y$ (continue until $x \ge y$).

Worked example: circle with r = 10

Take centre $(0, 0)$ and $r = 10$. The start point is $(0, 10)$ and $p_0 = 1 - 10 = -9$. At each row the sign of $p_k$ decides the next point and the update uses the new $x_{k+1}$ (and $y_{k+1}$ when y drops).

k	$p_k$	Next point $(x_{k+1}, y_{k+1})$	Update used
0	-9	(1, 10)	$p + 2(1) + 1 = -6$
1	-6	(2, 10)	$p + 2(2) + 1 = -1$
2	-1	(3, 10)	$p + 2(3) + 1 = 6$
3	6	(4, 9)	$p + 2(4) + 1 - 2(9) = -3$
4	-3	(5, 9)	$p + 2(5) + 1 = 8$
5	8	(6, 8)	$p + 2(6) + 1 - 2(8) = 5$
6	5	(7, 7)	$p + 2(7) + 1 - 2(7) = 6$

The octant ends at $(7, 7)$ because $x \ge y$ there. The points of the first octant are therefore $(0,10), (1,10), (2,10), (3,10), (4,9), (5,9), (6,8), (7,7)$. Reflecting these through $(\pm y, \pm x)$ and the sign changes gives the full circle, for example $(10, 0)$, $(9, 4)$, $(8, 6)$ and $(-7, 7)$.

Midpoint ellipse drawing algorithm

An ellipse centred at the origin with semi-axes $r_x$ and $r_y$ satisfies

$$f(x, y) = r_y^2 x^2 + r_x^2 y^2 - r_x^2 r_y^2 = 0$$

and has only four-way symmetry, so one quadrant is computed. The slope of the curve changes from shallower than $-1$ to steeper than $-1$ inside the quadrant, so the quadrant is split into two regions and the roles of x and y swap.

Region 1 runs from $(0, r_y)$ while the slope magnitude is below 1, which holds while $2r_y^2 x < 2r_x^2 y$. Here x is the unit-step axis. The first parameter and updates are

$$p1_0 = r_y^2 - r_x^2 r_y + \tfrac{1}{4} r_x^2$$

If $p1_k < 0$ the next point is $(x_k + 1, y_k)$ and $p1_{k+1} = p1_k + 2r_y^2 x_{k+1} + r_y^2$. Otherwise the next point is $(x_k + 1, y_k - 1)$ and $p1_{k+1} = p1_k + 2r_y^2 x_{k+1} - 2r_x^2 y_{k+1} + r_y^2$.

Region 2 starts at the last point $(x_0, y_0)$ of region 1 and runs down to $y = 0$, with y as the unit-step axis. The first parameter is

$$p2_0 = r_y^2\left(x_0 + \tfrac{1}{2}\right)^2 + r_x^2 (y_0 - 1)^2 - r_x^2 r_y^2$$

If $p2_k > 0$ the next point is $(x_k, y_k - 1)$ and $p2_{k+1} = p2_k - 2r_x^2 y_{k+1} + r_x^2$. Otherwise the next point is $(x_k + 1, y_k - 1)$ and $p2_{k+1} = p2_k + 2r_y^2 x_{k+1} - 2r_x^2 y_{k+1} + r_x^2$.

Worked example: ellipse with rx = 6, ry = 8

Here $r_x^2 = 36$, $r_y^2 = 64$, $2r_x^2 = 72$, $2r_y^2 = 128$. The start point is $(0, 8)$ and

$$p1_0 = 64 - 36(8) + 9 = -215$$

Region 1 continues while $128x < 72y$.

k	Point $(x_k, y_k)$	$p1_k$	$128x_k$	$72y_k$	Next point
0	(0, 8)	-215	0	576	(1, 8)
1	(1, 8)	-23	128	576	(2, 8)
2	(2, 8)	297	256	576	(3, 7)
3	(3, 7)	241	384	504	(4, 6)
4	(4, 6)	385	512	432	switch

For example $p1_1 = -215 + 128(1) + 64 = -23$, and since $p1_2 = -23 + 128(2) + 64 = 297$ is positive the next step lowers y, giving $p1_3 = 297 + 128(3) - 72(7) + 64 = 241$. At $(4, 6)$ we have $128 \cdot 4 = 512 > 72 \cdot 6 = 432$, so region 1 ends and $(4, 6)$ is the starting point of region 2.

For region 2 the first parameter is

$$p2_0 = 64\left(4.5\right)^2 + 36(5)^2 - 36 \cdot 64 = 1296 + 900 - 2304 = -108$$

Since $p2_0 < 0$ the next point is $(5, 5)$, and $p2_1 = -108 + 128(5) - 72(5) + 36 = 208$. This is positive, so x stays at 5 and y drops, giving $(5, 4)$ with $p2_2 = 208 - 72(4) + 36 = -44$. Continuing in the same way the points are $(6, 3)$, $(6, 2)$, $(6, 1)$ and $(6, 0)$, where y reaches 0.

The first-quadrant points are therefore $(0,8), (1,8), (2,8), (3,7), (4,6), (5,5), (5,4), (6,3), (6,2), (6,1), (6,0)$. The other three quadrants follow by symmetry using $(\pm x, \pm y)$.

Non-origin centre, such as (15, 10)

The algorithms always run as if the centre were the origin. At the moment of plotting, add the centre to every point: $(x + x_c,; y + y_c)$. For the ellipse above moved to centre $(15, 10)$, the point $(0, 8)$ is plotted as $(15, 18)$, $(3, 7)$ as $(18, 17)$ and $(6, 0)$ as $(21, 10)$, together with the mirror points such as $(12, 17)$ and $(15, 2)$. The same method answers questions such as $r_x = 14$, $r_y = 10$ centre $(15, 10)$, where $p1_0 = 100 - 196(10) + 49 = -1811$, or $r_x = 2$, $r_y = 4$ centre $(4, 5)$: only the numbers change, never the procedure.

How to write it in the exam

Start with the circle or ellipse equation, state the decision parameter and its initial value, and give the update rules for each case in a short list. Then draw the table with one row per iteration, mark where region 1 ends in the ellipse, list the points of one octant or quadrant, and finish by stating the symmetric points and the shift by the centre. A neat table earns most of the marks even if one late value slips.

Related methods for lines are covered in the same unit, and the full subject pages are CSC214 Computer Graphics and BIT304 Computer Graphics.

Keep studying

Solved past questions

Every TU CSIT, BIT and NEB subject, answered by unit.

NoteTok

30-second concept shorts from real exam questions.

Ask a question

Missing an answer? Submit it to the queue.