--- title: "Midpoint circle algorithm and decision parameter" subject: "Computer Graphics" chapter: 2 key: "semester_5/computer_graphics:midpoint-circle-derive" source: https://www.bctengineer.com/q/semester_5/computer_graphics/midpoint-circle-derive site: BCT Engineering --- # Midpoint circle algorithm and decision parameter Computer Graphics · Chapter 2: Scan-Conversion - Asked in: 2073 Shrawan, 10 marks; 2069 Chaitra, 8 marks; 2075 Asoj, 7 marks; 2067 Mangsir (old course), 6 marks; 2078 Kartik, 4 marks; 2074 Chaitra, 4 marks; 2081 Chaitra (new course), 2 marks; 2068 Chaitra, 4 marks (asked 8 times) - Video: [The Midpoint Circle Algorithm Explained Step by Step](https://www.youtube.com/watch?v=hpiILbMkF9w) — NoBS Code - Answer checked by Claude Opus 5.5 (high effort) on 2026-10-14 - Page: https://www.bctengineer.com/q/semester_5/computer_graphics/midpoint-circle-derive - Whole chapter: https://www.bctengineer.com/md/semester_5/computer_graphics/chapter-2 ## Question Derive the decision parameter and write the midpoint algorithm for drawing a circle. ## Short answer Decision parameter p_k = f(x_k+1, y_k-1/2) = (x_k+1)^2 + (y_k-1/2)^2 - r^2. If p_k<0, choose (x_k+1, y_k), p_k+1 = p_k + 2x_k+3; else (x_k+1, y_k-1), p_k+1 = p_k + 2(x_k - y_k)+5. Start at (0,r) with p0=1-r, iterate while x 0 : point is outside the circle ``` Start at (0, r) and move in the +x direction (clockwise) in the octant where the slope has magnitude less than 1 (x increases by 1 each step). If the pixel (x_k, y_k) has been plotted, the next pixel is either **(x_k+1, y_k)** or **(x_k+1, y_k−1)**. The midpoint of these two candidates is (x_k+1, y_k−½). The decision parameter is the circle function at this midpoint: ```text p_k = f(x_k+1, y_k−½) = (x_k+1)² + (y_k−½)² − r² ``` - If p_k < 0, the midpoint is inside the circle, so the pixel at y_k is closer to the circle: choose (x_k+1, y_k). - If p_k ≥ 0, the midpoint is outside or on the circle, so the pixel at y_k−1 is closer: choose (x_k+1, y_k−1). **Incremental form.** The next parameter is ```text p_k+1 = f(x_k+1 + 1, y_k+1 − ½) = [(x_k+1)+1]² + (y_k+1 − ½)² − r² ``` Subtracting p_k: ```text p_k+1 = p_k + 2(x_k+1) + (y²_k+1 − y²_k) − (y_k+1 − y_k) + 1 ``` - Case p_k < 0 (y_k+1 = y_k): p_k+1 = p_k + 2x_k + 3 - Case p_k ≥ 0 (y_k+1 = y_k − 1): p_k+1 = p_k + 2x_k + 3 − 2y_k + 2 = p_k + 2(x_k − y_k) + 5 **Initial value.** At the start point (0, r) the first midpoint is (1, r−½): ```text p_0 = f(1, r−½) = 1 + (r−½)² − r² = 5/4 − r ``` For integer radius, 5/4 is rounded to 1 (all other terms are integers and p is only compared with 0), so **p_0 = 1 − r**. #### Midpoint circle algorithm (centre (xc, yc), radius r) ```text 1. Input r and centre (xc, yc). 2. x = 0, y = r. 3. p = 1 − r. 4. Plot the 8 symmetric points of (x, y) shifted by (xc, yc): (xc±x, yc±y) and (xc±y, yc±x). 5. While x < y: x = x + 1 if p < 0: p = p + 2x + 1 // 2x_k + 3 in terms of old x else: y = y − 1 p = p + 2(x − y) + 1 // 2(x_k − y_k) + 5 in terms of old values plot the 8 symmetric points of (x, y) 6. Stop. ``` (Here the updates use the new x, y: with x_new = x_k+1, 2x_k+3 = 2x_new+1 and 2(x_k−y_k)+5 = 2(x_new − y_new)+1.) #### Example, r = 10 p_0 = 1 − 10 = −9. The octant points are (0,10), (1,10), (2,10), (3,10), (4,9), (5,9), (6,8), (7,7). ## Check yourself The answer's key points as multiple-choice questions, with the correct option and why. 1. f(x,y) = x^2 + y^2 - r^2 < 0 means the point is A. outside B. on the circle C. at the centre D. inside the circle Answer: D. Negative means inside. (Key point: Circle function) 2. p_k is the circle function at A. (x_k + 1, y_k - 1/2) B. (x_k, y_k) C. (x_k + 1, y_k + 1/2) D. (x_k - 1, y_k) Answer: A. Midpoint of the candidates. (Key point: Decision parameter) 3. If p_k < 0 the next pixel is A. (x_k + 1, y_k - 1) B. (x_k + 1, y_k) C. (x_k, y_k - 1) D. (x_k - 1, y_k) Answer: B. Midpoint inside so y_k is closer. (Key point: Choice) 4. Initial p_0 for integer radius is A. 5/4 + r B. r - 1 C. 1 - r D. 2 - r Answer: C. 5/4 - r rounded to 1 - r. (Key point: Initial) ## Related in Computer Graphics - [Midpoint circle: r=7, centre (10,15)](https://www.bctengineer.com/question.md?key=semester_5%2Fcomputer_graphics%3Acircle-r7-center-10-15) — Computer Graphics, chapter 2 - [Midpoint circle: r=8, centre (10,10)](https://www.bctengineer.com/question.md?key=semester_5%2Fcomputer_graphics%3Acircle-r8-center-10-10) — Computer Graphics, chapter 2, asked 2× - [Midpoint circle: r=6, centre (20,10)](https://www.bctengineer.com/question.md?key=semester_5%2Fcomputer_graphics%3Acircle-r6-center-20-10) — Computer Graphics, chapter 2, asked 2× - [Midpoint circle: r=10, centre (20,30)](https://www.bctengineer.com/question.md?key=semester_5%2Fcomputer_graphics%3Acircle-r10-center-20-30) — Computer Graphics, chapter 2 - [Bresenham decision parameter, negative slope](https://www.bctengineer.com/question.md?key=semester_5%2Fcomputer_graphics%3Abresenham-negative-slope-derive) — Computer Graphics, chapter 2, asked 2× - [Bresenham decision parameter, |m| > 1](https://www.bctengineer.com/question.md?key=semester_5%2Fcomputer_graphics%3Abresenham-negative-slope-m-gt-1) — Computer Graphics, chapter 2 ## Related in other subjects - [Decision tree classifier and Hunt's algorithm](https://www.bctengineer.com/question.md?key=semester_7%2Fdata_mining%3Adecision-tree-hunt) — Data Mining, chapter 3 - [Magic tee diagram and S-parameter derivation](https://www.bctengineer.com/question.md?key=semester_7%2Frf_and_microwave_engineering%3Amagic-tee-s-parameter-derivation) — RF and Microwave Engineering, chapter 4 - [Principal stresses and Mohr's circle (30, 18, 75)](https://www.bctengineer.com/question.md?key=semester_3%2Fstrength_of_materials%3Aprincipal-stresses-mohr-30-18-75) — Strength of Materials, chapter 4 - [Principal stresses, plane BE, Mohr's circle](https://www.bctengineer.com/question.md?key=semester_3%2Fstrength_of_materials%3Aplane-stress-40-50-30-plane) — Strength of Materials, chapter 4