2.3.1 Midpoint Circle Algorithm

Cf. [FvDFH90, 3.3.2].

Figure: Midpoint circle algorithm

The midpoint circle algorithm of Bresenham [Bre77] and [BGP83] is analogously to that of straight lines and goes as follows:

$$F\left(x+1,\bar{y}+\frac12\right) = (x+1)^2+\left(\bar{y}+\frac12\right)^2-R^2 = F(x,\bar{y}) + 2x+\bar{y}+\frac{5}{4}$$

and in the next step:

$$E:\quad F\left(x+2,\bar{y}+\frac12\right)=F\left(x+1,\bar{y}+\frac12\right)+2x+3$$

$$NE: \quad F\left(x+2,\bar{y}+\frac32\right)=F\left(x+1,\bar{y}+\frac12\right)+2x+2\bar{y}+5$$

One can speed up things be calculating the linear increments recursively.