{"id":60,"date":"2018-07-20T05:18:07","date_gmt":"2018-07-20T05:18:07","guid":{"rendered":"http:\/\/csp06.epgpbooks.inflibnet.ac.in\/?post_type=chapter&#038;p=60"},"modified":"2018-12-26T12:03:15","modified_gmt":"2018-12-26T12:03:15","slug":"midpoint-circle-drawing-procedure","status":"publish","type":"chapter","link":"https:\/\/ebooks.inflibnet.ac.in\/csp06\/chapter\/midpoint-circle-drawing-procedure\/","title":{"rendered":"Midpoint Circle Drawing Procedure"},"content":{"raw":"<div><span style=\"float: right\"><a href=\"https:\/\/youtu.be\/UWp8R1-Gzzg\" target=\"_blank\" rel=\"noopener\"><img src=\"http:\/\/epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/2018\/11\/download.png\" alt=\"epgp books\" width=\"75px\" height=\"75px;\" \/><\/a>\r\n<\/span><\/div>\r\n<div>\r\n\r\n&nbsp;\r\n\r\n&nbsp;\r\n\r\n&nbsp;\r\n<p style=\"text-align: justify\">Before going into the Midpoint circle drawing procedure, Lets solve an example problem, to understand how Bresenham\u2019s procedure works for various lines. Consider examples as below.<\/p>\r\n&nbsp;\r\n\r\n<strong>Example Problem -1: <\/strong>(When |m|&lt;=1 and m is +ve)\r\n\r\n&nbsp;\r\n<p style=\"text-align: justify\"><strong>Problem: <\/strong>Scan convert the line between (2, 2) and (10, 5) using Bresenham\u2019s algorithm<\/p>\r\n&nbsp;\r\n\r\n<strong>Sol: <\/strong>Since the line has a slope m=3\/8 =0.375 the following set of equations would be valid\r\n\r\n&nbsp;\r\n\r\n<strong>P<\/strong><strong>0<\/strong><strong>=2\u2206y-\u2206x,<\/strong>\u00a0\u00a0\u00a0\u00a0 <strong>\u2206y=3,<\/strong>\u00a0\u00a0\u00a0 <strong>\u2206x=8<\/strong>\r\n\r\n<strong>P<\/strong><strong>0<\/strong><strong>=6-8=-2<\/strong>\r\n\r\n&nbsp;\r\n\r\nRepresent first pixel as (X0,Y0) =(2,2).\r\n<p style=\"text-align: justify\">P0=-2, since, P0 \u2013ve use case (i) i.e. next pixel is (X1,Y1) =(X0+1,Y0)=(3,2) and Compute P1 =P0 +2*3 = -2+6=4, P1 +ve use case (ii)<\/p>\r\n&nbsp;\r\n\r\n<img class=\"size-full wp-image-63 aligncenter\" src=\"http:\/\/csp06.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/52\/2018\/07\/1-27.png\" alt=\"\" width=\"184\" height=\"281\" \/>\r\n\r\n<strong>Example Problem -2: <\/strong>(When |m|&lt;=1 and m is -ve)\r\n\r\n&nbsp;\r\n\r\nProblem: Scan convert the line between (2, 8) and (10, 5) using Bresenham\u2019s algorithm\r\n\r\nSol:\u00a0 \u2206y = -3, \u2206x = 8\r\n\r\n<\/div>\r\n<div>\r\n\r\n&nbsp;\r\n<p style=\"text-align: justify\">Since the line has a slope m=-3\/8=-0.375 i.e. |m|&lt;1 the same set of equations used for the previous example would be valid.<\/p>\r\n&nbsp;\r\n\r\n<\/div>\r\n<div>\r\n\r\n<strong>\u00a0 \u00a0 P<\/strong><strong>0<\/strong><strong>=2|\u2206y|-|\u2206x|<\/strong>\r\n\r\n<strong>|\u2206y|=3<\/strong>\r\n\r\n<strong>|\u2206x|=8<\/strong>\r\n\r\n<strong>P<\/strong><strong>0<\/strong><strong>=6-8=-2<\/strong>\r\n\r\n&nbsp;\r\n\r\nRepresent first pixel as (X0,Y0) =(2,8)\r\n\r\nP0=-2\r\n\r\nuse case (i) i.e. next pixel is\r\n\r\n(X1,Y1)=(X0+1,Y0)=(3,8) and compute\r\n\r\nP1 =P0 +2*3 = -2+6=4\r\n\r\nSince P1\u00a0 is +ve use case (ii) so next pixel to be plotted is (4,7)\r\n\r\nP2=4+2x3-2x8 = -6\r\n\r\nSince P2 is \u2013ve, the next pixel to be plotted is (5, 7) and continue till we reach the end of line.\r\n\r\n&nbsp;\r\n\r\n<img class=\"size-full wp-image-64 aligncenter\" src=\"http:\/\/csp06.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/52\/2018\/07\/1-28.png\" alt=\"\" width=\"194\" height=\"367\" \/>\r\n<p style=\"text-align: justify\">Note that even if \u2206y is \u2013ve, we consider only the magnitude for all computations Observe that while x is increasing in increments of 1 from 3 to 9, while y is decreasing from 8 to 5 as per the algorithm.<\/p>\r\n&nbsp;\r\n\r\n<strong>Conclusion:<\/strong>\r\n<ul>\r\n \t<li style=\"text-align: justify\">Important observation while working with negative slopes is that do always compute magnitudes for \u0394x and \u0394y i.e. |\u0394x| and |\u0394y| and never consider signs.<\/li>\r\n \t<li style=\"text-align: justify\">Observe always that Pk should fluctuate about +ve and -ve<\/li>\r\n \t<li style=\"text-align: justify\">For Longer lines DDA line drifts away from the true line.<\/li>\r\n \t<li style=\"text-align: justify\">Bresenham\u2019s line fluctuates about the theoretical line.<\/li>\r\n \t<li style=\"text-align: justify\">Bresenham\u2019s line better approximates the theoretical line i.e., it never deviates from the theoretical line.<\/li>\r\n \t<li>No floating point calculations are involved.<\/li>\r\n<\/ul>\r\n<\/div>\r\n<img class=\"size-full wp-image-65 aligncenter\" src=\"http:\/\/csp06.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/52\/2018\/07\/1-29.png\" alt=\"\" width=\"286\" height=\"230\" \/>\r\n<div>\r\n\r\n&nbsp;\r\n\r\n<strong>Summary:<\/strong>\r\n<ul>\r\n \t<li>Outlined the Bresenham\u2019s line drawing procedure<\/li>\r\n \t<li>Noted the advantages of the procedure over DDA procedure.<\/li>\r\n<\/ul>\r\n&nbsp;\r\n\r\n<strong>Midpoint Circle Drawing Procedure:<\/strong>\r\n\r\n&nbsp;\r\n<p style=\"text-align: justify\">We have started with the first primitive, points, followed by lines, now followed by the third primitive of interest, the <strong>circle<\/strong>. A circle is fundamentally symmetric and exhibits octant symmetry. i.e. a circle is symmetric about its octants.<\/p>\r\n&nbsp;\r\n<p style=\"text-align: justify\">If we know a point on any one of the octants the remaining 7 symmetric points can be plotted by interchanging magnitudes of x and y and also signs Lets try to understand what octant symmetry is through the following diagram.<\/p>\r\n&nbsp;\r\n\r\n<img class=\"size-full wp-image-66 aligncenter\" src=\"http:\/\/csp06.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/52\/2018\/07\/1-30.png\" alt=\"\" width=\"240\" height=\"165\" \/>\r\n\r\n&nbsp;\r\n<p style=\"text-align: justify\">As shown in the diagram above, divide the circle into 8 parts (each is an octant) using 4 axes. Assume that we know a point say (2, 7) on one of the octants, the remaining 7 symmetric points on the seven octants can be easily plotted without making any computations. If we fold the octants about an axis, the octant exactly overlaps on the neighbouring octant due to symmetry.<\/p>\r\n&nbsp;\r\n<p style=\"text-align: justify\">It is enough that we compute points on one of the octants. The remaining points can be easily plotted without any computations.<\/p>\r\n&nbsp;\r\n<p style=\"text-align: justify\">Assuming the circle is centered at origin and has a radius <strong>r<\/strong> units, the algorithm can start with a known point (0, r) and proceed to compute points till the end of the octant is reached. For convenience, we shall chose the first octant i.e. that octant in which the relation x&lt;y is satisfied. We need to compute points on part of the circle shown in the diagram. How do we know where to stop so that the end of the octant is reached? We need to find out the stopping condition for the algorithm. The?? Symbols shown in the diagram represent the last\u00a0<span style=\"font-size: 1em;text-align: initial\">point on the chosen octant at which we should stop. Moreover the point (??) might lie on the axis which satisfies the equation, x=y, that means all points that lie on that axis are like, (2,2) (3,3) and so on. This axis divides the first positive quadrant into two zones or two octants. All points on the upper side of the axis satisfy the relation x&lt;y, while all the points on the lower side of the axis satisfy the relation x&gt;y. That is to fix our stopping condition as we go on computing points, it is just sufficient that we check the relation between x and y, i.e., as long as x&lt;=y we can do our computation, and stop when the relation x&lt;=y is not satisfied by the points. Also observe that in the chosen octant, while we proceed to compute points on the circle boundary, the slope of the circle changes from 0 (positive) to -1 (negative). While x increases, y decreases. Because the circle has slope that is almost flat, we can sample the circle along x-axis at unit steps and compute the corresponding y-values.<\/span><\/p>\r\n\r\n<\/div>\r\n<div>\r\n\r\n&nbsp;\r\n\r\n<img class=\"size-full wp-image-67 aligncenter\" src=\"http:\/\/csp06.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/52\/2018\/07\/1-31.png\" alt=\"\" width=\"194\" height=\"178\" \/>\r\n\r\n&nbsp;\r\n\r\n&nbsp;\r\n<ul>\r\n \t<li>Start at (0,r)<\/li>\r\n \t<li>End at (x,y) such that x&gt;=y i.e. whenever x becomes &gt;=y we can stop the algo.<\/li>\r\n \t<li style=\"text-align: justify\">Because the shape of the circle in this region is more flat, we can sample it along X-axis at unit intervals, and compute the corresponding y-values.<\/li>\r\n<\/ul>\r\n&nbsp;\r\n\r\nWhat is the principle behind Midpoint Circle drawing procedure?\r\n\r\n&nbsp;\r\n\r\nEquation of circle with centre at origin, and having a radius of r units is given by\r\n<p style=\"text-align: justify\">x2+y2=r2. We can start with a known point on the circle say (xk,yk) in the chosen octant. Let the next point to be computed be represented as (xk+1,yk+1). Since we are sampling on x-axis at unit x-intervals, it is evident that the next x, xk+1= xk+1.<\/p>\r\n&nbsp;\r\n\r\n<img class=\"size-full wp-image-68 aligncenter\" src=\"http:\/\/csp06.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/52\/2018\/07\/1-32.png\" alt=\"\" width=\"276\" height=\"185\" \/>\r\n\r\nAs we know from theory that any point x, y that satisfy the relation\r\n<ul>\r\n \t<li>x2+y2-r2 &lt;0 is a point that lies inside the circle boundary<\/li>\r\n \t<li>x2+y2-r2 &gt;0 is a point that lies outside the circle boundary<\/li>\r\n \t<li>x2+y2-r2 =0 is a point that lies on the circle boundary<\/li>\r\n<\/ul>\r\n<\/div>\r\n<div>\r\n<p style=\"text-align: justify\">For the next x position xk+1, we can choose between two y positions yk or yk-1. Compute midpoint for the two possible pixel locations (xk+1, yk) (xk+1, yk-1) and verify its position relative to the circle boundary. If the midpoint lies inside the circle boundary choose to plot the upper pixel else the lower pixel. The coordinates of the midpoint are for the two possible pixels positions (x<sub>k+1<\/sub>, y<sub>k<\/sub>) or (x<sub>k+1,<\/sub> y<sub>k-1<\/sub>) are (?<sub>?<\/sub> + ?, ?<sub>?<\/sub> \u2212 ?\/2\u00a0)<\/p>\r\n&nbsp;\r\n<p style=\"text-align: justify\">Now by substituting the coordinates of the midpoint, in the circle equation, we can check whether the midpoint lies inside, outside or on the circle boundary. Thus the decision parameter <strong><em>P<\/em><\/strong><strong><em>k<\/em><\/strong> for our derivation is given by<\/p>\r\n\r\n<\/div>\r\n<img class=\"size-full wp-image-69 aligncenter\" src=\"http:\/\/csp06.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/52\/2018\/07\/1-33.png\" alt=\"\" width=\"246\" height=\"27\" \/>\r\n<div>\r\n\r\n&nbsp;\r\n<p style=\"text-align: justify\">i.e., <strong><em>P<\/em><\/strong><strong><em>k<\/em><\/strong><strong><em>&lt;0,<\/em><\/strong> means that midpoint is inside the circle boundary, so the circle boundary is close to the upper pixel, thus choose the upper pixel (xk+1, yk) for plotting, otherwise if <strong><em>P<\/em><\/strong><strong><em>k<\/em><\/strong><strong><em>&gt;0,<\/em><\/strong> the midpoint is outside the circle boundary, so the circle boundary is close to the lower pixel, thus choose the lower pixel (xk+1, yk-1) for plotting, or otherwise if <strong><em>P<\/em><\/strong><strong><em>k<\/em><\/strong><strong>=<em>0<\/em><\/strong>, the midpoint lies on the circle boundary, so we can choose between either of upper and lower pixels and so for consistency we can choose the upper pixel, for this case.<\/p>\r\n&nbsp;\r\n\r\n&nbsp;\r\n\r\n<img class=\"size-full wp-image-70 aligncenter\" src=\"http:\/\/csp06.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/52\/2018\/07\/1-34.png\" alt=\"\" width=\"370\" height=\"406\" \/>\r\n\r\n&nbsp;\r\n\r\n&nbsp;\r\n\r\n<img class=\"size-full wp-image-71 aligncenter\" src=\"http:\/\/csp06.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/52\/2018\/07\/1-35.png\" alt=\"\" width=\"611\" height=\"220\" \/>\r\n\r\n&nbsp;\r\n\r\n<img class=\"size-full wp-image-72 aligncenter\" src=\"http:\/\/csp06.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/52\/2018\/07\/1-36.png\" alt=\"\" width=\"593\" height=\"533\" \/>\r\n\r\n<\/div>\r\n<p style=\"padding-left: 30px;text-align: justify\">Problem: Find the points on a circle on of its octants with the circle centered at (5,5) and has a radius of 8 units.<\/p>\r\n<p style=\"padding-left: 30px;text-align: justify\">Solution: Assume that the circle is centered at origin and proceed to solve. After finding the points add center (5, 5) to each point.<\/p>\r\n<p style=\"padding-left: 30px;text-align: justify\">The initial point (x0,y0)=(0,8)<\/p>\r\n<p style=\"padding-left: 30px;text-align: justify\">P0 = 1-r = 1-8=-7\r\n(x0,y0) = (0, 8)\r\nP0=-7\r\nP1=-7+2+1=-4 (-ve, case (i))\r\nP2=-4+4+1=1\r\n(+ve, case (ii))\r\nP3=1+6-14+1=-6 (-ve, case (i))<\/p>\r\n<img class=\"size-full wp-image-73 aligncenter\" src=\"http:\/\/csp06.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/52\/2018\/07\/1-37.png\" alt=\"\" width=\"206\" height=\"165\" \/>\r\n\r\n&nbsp;\r\n\r\n<strong>Conclusion:<\/strong>\r\n\r\n&nbsp;\r\n\r\nMidpoint circle drawing algorithm is more efficient, due to\r\n<ul>\r\n \t<li>Recursive nature of the algorithm<\/li>\r\n \t<li>No floating point calculations<\/li>\r\n \t<li>Accurate and simple<\/li>\r\n<\/ul>\r\n<img class=\"size-full wp-image-74 aligncenter\" src=\"http:\/\/csp06.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/52\/2018\/07\/1-38.png\" alt=\"\" width=\"654\" height=\"283\" \/>\r\n\r\n<table>\r\n<tbody>\r\n<tr>\r\n<td><strong>you can view video on Midpoint Circle Drawing Procedure<\/strong><\/td>\r\n<td><a href=\"https:\/\/youtu.be\/UWp8R1-Gzzg\" target=\"_blank\" rel=\"noopener\"><img class=\"alignnone wp-image-120\" src=\"http:\/\/epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/2018\/11\/download.png\" alt=\"\" width=\"36\" height=\"36\" \/><\/a><\/td>\r\n<\/tr>\r\n<\/tbody>\r\n<\/table>","rendered":"<div><span style=\"float: right\"><a href=\"https:\/\/youtu.be\/UWp8R1-Gzzg\" target=\"_blank\" rel=\"noopener\"><img decoding=\"async\" src=\"http:\/\/epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/2018\/11\/download.png\" alt=\"epgp books\" width=\"75px\" height=\"75px;\" \/><\/a><br \/>\n<\/span><\/div>\n<div>\n<p>&nbsp;<\/p>\n<p>&nbsp;<\/p>\n<p>&nbsp;<\/p>\n<p style=\"text-align: justify\">Before going into the Midpoint circle drawing procedure, Lets solve an example problem, to understand how Bresenham\u2019s procedure works for various lines. Consider examples as below.<\/p>\n<p>&nbsp;<\/p>\n<p><strong>Example Problem -1: <\/strong>(When |m|&lt;=1 and m is +ve)<\/p>\n<p>&nbsp;<\/p>\n<p style=\"text-align: justify\"><strong>Problem: <\/strong>Scan convert the line between (2, 2) and (10, 5) using Bresenham\u2019s algorithm<\/p>\n<p>&nbsp;<\/p>\n<p><strong>Sol: <\/strong>Since the line has a slope m=3\/8 =0.375 the following set of equations would be valid<\/p>\n<p>&nbsp;<\/p>\n<p><strong>P<\/strong><strong>0<\/strong><strong>=2\u2206y-\u2206x,<\/strong>\u00a0\u00a0\u00a0\u00a0 <strong>\u2206y=3,<\/strong>\u00a0\u00a0\u00a0 <strong>\u2206x=8<\/strong><\/p>\n<p><strong>P<\/strong><strong>0<\/strong><strong>=6-8=-2<\/strong><\/p>\n<p>&nbsp;<\/p>\n<p>Represent first pixel as (X0,Y0) =(2,2).<\/p>\n<p style=\"text-align: justify\">P0=-2, since, P0 \u2013ve use case (i) i.e. next pixel is (X1,Y1) =(X0+1,Y0)=(3,2) and Compute P1 =P0 +2*3 = -2+6=4, P1 +ve use case (ii)<\/p>\n<p>&nbsp;<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"size-full wp-image-63 aligncenter\" src=\"http:\/\/csp06.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/52\/2018\/07\/1-27.png\" alt=\"\" width=\"184\" height=\"281\" srcset=\"https:\/\/ebooks.inflibnet.ac.in\/csp06\/wp-content\/uploads\/sites\/52\/2018\/07\/1-27.png 184w, https:\/\/ebooks.inflibnet.ac.in\/csp06\/wp-content\/uploads\/sites\/52\/2018\/07\/1-27-65x99.png 65w\" sizes=\"auto, (max-width: 184px) 100vw, 184px\" \/><\/p>\n<p><strong>Example Problem -2: <\/strong>(When |m|&lt;=1 and m is -ve)<\/p>\n<p>&nbsp;<\/p>\n<p>Problem: Scan convert the line between (2, 8) and (10, 5) using Bresenham\u2019s algorithm<\/p>\n<p>Sol:\u00a0 \u2206y = -3, \u2206x = 8<\/p>\n<\/div>\n<div>\n<p>&nbsp;<\/p>\n<p style=\"text-align: justify\">Since the line has a slope m=-3\/8=-0.375 i.e. |m|&lt;1 the same set of equations used for the previous example would be valid.<\/p>\n<p>&nbsp;<\/p>\n<\/div>\n<div>\n<p><strong>\u00a0 \u00a0 P<\/strong><strong>0<\/strong><strong>=2|\u2206y|-|\u2206x|<\/strong><\/p>\n<p><strong>|\u2206y|=3<\/strong><\/p>\n<p><strong>|\u2206x|=8<\/strong><\/p>\n<p><strong>P<\/strong><strong>0<\/strong><strong>=6-8=-2<\/strong><\/p>\n<p>&nbsp;<\/p>\n<p>Represent first pixel as (X0,Y0) =(2,8)<\/p>\n<p>P0=-2<\/p>\n<p>use case (i) i.e. next pixel is<\/p>\n<p>(X1,Y1)=(X0+1,Y0)=(3,8) and compute<\/p>\n<p>P1 =P0 +2*3 = -2+6=4<\/p>\n<p>Since P1\u00a0 is +ve use case (ii) so next pixel to be plotted is (4,7)<\/p>\n<p>P2=4+2&#215;3-2&#215;8 = -6<\/p>\n<p>Since P2 is \u2013ve, the next pixel to be plotted is (5, 7) and continue till we reach the end of line.<\/p>\n<p>&nbsp;<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"size-full wp-image-64 aligncenter\" src=\"http:\/\/csp06.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/52\/2018\/07\/1-28.png\" alt=\"\" width=\"194\" height=\"367\" srcset=\"https:\/\/ebooks.inflibnet.ac.in\/csp06\/wp-content\/uploads\/sites\/52\/2018\/07\/1-28.png 194w, https:\/\/ebooks.inflibnet.ac.in\/csp06\/wp-content\/uploads\/sites\/52\/2018\/07\/1-28-159x300.png 159w, https:\/\/ebooks.inflibnet.ac.in\/csp06\/wp-content\/uploads\/sites\/52\/2018\/07\/1-28-65x123.png 65w\" sizes=\"auto, (max-width: 194px) 100vw, 194px\" \/><\/p>\n<p style=\"text-align: justify\">Note that even if \u2206y is \u2013ve, we consider only the magnitude for all computations Observe that while x is increasing in increments of 1 from 3 to 9, while y is decreasing from 8 to 5 as per the algorithm.<\/p>\n<p>&nbsp;<\/p>\n<p><strong>Conclusion:<\/strong><\/p>\n<ul>\n<li style=\"text-align: justify\">Important observation while working with negative slopes is that do always compute magnitudes for \u0394x and \u0394y i.e. |\u0394x| and |\u0394y| and never consider signs.<\/li>\n<li style=\"text-align: justify\">Observe always that Pk should fluctuate about +ve and -ve<\/li>\n<li style=\"text-align: justify\">For Longer lines DDA line drifts away from the true line.<\/li>\n<li style=\"text-align: justify\">Bresenham\u2019s line fluctuates about the theoretical line.<\/li>\n<li style=\"text-align: justify\">Bresenham\u2019s line better approximates the theoretical line i.e., it never deviates from the theoretical line.<\/li>\n<li>No floating point calculations are involved.<\/li>\n<\/ul>\n<\/div>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"size-full wp-image-65 aligncenter\" src=\"http:\/\/csp06.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/52\/2018\/07\/1-29.png\" alt=\"\" width=\"286\" height=\"230\" srcset=\"https:\/\/ebooks.inflibnet.ac.in\/csp06\/wp-content\/uploads\/sites\/52\/2018\/07\/1-29.png 286w, https:\/\/ebooks.inflibnet.ac.in\/csp06\/wp-content\/uploads\/sites\/52\/2018\/07\/1-29-65x52.png 65w, https:\/\/ebooks.inflibnet.ac.in\/csp06\/wp-content\/uploads\/sites\/52\/2018\/07\/1-29-225x181.png 225w\" sizes=\"auto, (max-width: 286px) 100vw, 286px\" \/><\/p>\n<div>\n<p>&nbsp;<\/p>\n<p><strong>Summary:<\/strong><\/p>\n<ul>\n<li>Outlined the Bresenham\u2019s line drawing procedure<\/li>\n<li>Noted the advantages of the procedure over DDA procedure.<\/li>\n<\/ul>\n<p>&nbsp;<\/p>\n<p><strong>Midpoint Circle Drawing Procedure:<\/strong><\/p>\n<p>&nbsp;<\/p>\n<p style=\"text-align: justify\">We have started with the first primitive, points, followed by lines, now followed by the third primitive of interest, the <strong>circle<\/strong>. A circle is fundamentally symmetric and exhibits octant symmetry. i.e. a circle is symmetric about its octants.<\/p>\n<p>&nbsp;<\/p>\n<p style=\"text-align: justify\">If we know a point on any one of the octants the remaining 7 symmetric points can be plotted by interchanging magnitudes of x and y and also signs Lets try to understand what octant symmetry is through the following diagram.<\/p>\n<p>&nbsp;<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"size-full wp-image-66 aligncenter\" src=\"http:\/\/csp06.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/52\/2018\/07\/1-30.png\" alt=\"\" width=\"240\" height=\"165\" srcset=\"https:\/\/ebooks.inflibnet.ac.in\/csp06\/wp-content\/uploads\/sites\/52\/2018\/07\/1-30.png 240w, https:\/\/ebooks.inflibnet.ac.in\/csp06\/wp-content\/uploads\/sites\/52\/2018\/07\/1-30-65x45.png 65w, https:\/\/ebooks.inflibnet.ac.in\/csp06\/wp-content\/uploads\/sites\/52\/2018\/07\/1-30-225x155.png 225w\" sizes=\"auto, (max-width: 240px) 100vw, 240px\" \/><\/p>\n<p>&nbsp;<\/p>\n<p style=\"text-align: justify\">As shown in the diagram above, divide the circle into 8 parts (each is an octant) using 4 axes. Assume that we know a point say (2, 7) on one of the octants, the remaining 7 symmetric points on the seven octants can be easily plotted without making any computations. If we fold the octants about an axis, the octant exactly overlaps on the neighbouring octant due to symmetry.<\/p>\n<p>&nbsp;<\/p>\n<p style=\"text-align: justify\">It is enough that we compute points on one of the octants. The remaining points can be easily plotted without any computations.<\/p>\n<p>&nbsp;<\/p>\n<p style=\"text-align: justify\">Assuming the circle is centered at origin and has a radius <strong>r<\/strong> units, the algorithm can start with a known point (0, r) and proceed to compute points till the end of the octant is reached. For convenience, we shall chose the first octant i.e. that octant in which the relation x&lt;y is satisfied. We need to compute points on part of the circle shown in the diagram. How do we know where to stop so that the end of the octant is reached? We need to find out the stopping condition for the algorithm. The?? Symbols shown in the diagram represent the last\u00a0<span style=\"font-size: 1em;text-align: initial\">point on the chosen octant at which we should stop. Moreover the point (??) might lie on the axis which satisfies the equation, x=y, that means all points that lie on that axis are like, (2,2) (3,3) and so on. This axis divides the first positive quadrant into two zones or two octants. All points on the upper side of the axis satisfy the relation x&lt;y, while all the points on the lower side of the axis satisfy the relation x&gt;y. That is to fix our stopping condition as we go on computing points, it is just sufficient that we check the relation between x and y, i.e., as long as x&lt;=y we can do our computation, and stop when the relation x&lt;=y is not satisfied by the points. Also observe that in the chosen octant, while we proceed to compute points on the circle boundary, the slope of the circle changes from 0 (positive) to -1 (negative). While x increases, y decreases. Because the circle has slope that is almost flat, we can sample the circle along x-axis at unit steps and compute the corresponding y-values.<\/span><\/p>\n<\/div>\n<div>\n<p>&nbsp;<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"size-full wp-image-67 aligncenter\" src=\"http:\/\/csp06.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/52\/2018\/07\/1-31.png\" alt=\"\" width=\"194\" height=\"178\" srcset=\"https:\/\/ebooks.inflibnet.ac.in\/csp06\/wp-content\/uploads\/sites\/52\/2018\/07\/1-31.png 194w, https:\/\/ebooks.inflibnet.ac.in\/csp06\/wp-content\/uploads\/sites\/52\/2018\/07\/1-31-65x60.png 65w\" sizes=\"auto, (max-width: 194px) 100vw, 194px\" \/><\/p>\n<p>&nbsp;<\/p>\n<p>&nbsp;<\/p>\n<ul>\n<li>Start at (0,r)<\/li>\n<li>End at (x,y) such that x&gt;=y i.e. whenever x becomes &gt;=y we can stop the algo.<\/li>\n<li style=\"text-align: justify\">Because the shape of the circle in this region is more flat, we can sample it along X-axis at unit intervals, and compute the corresponding y-values.<\/li>\n<\/ul>\n<p>&nbsp;<\/p>\n<p>What is the principle behind Midpoint Circle drawing procedure?<\/p>\n<p>&nbsp;<\/p>\n<p>Equation of circle with centre at origin, and having a radius of r units is given by<\/p>\n<p style=\"text-align: justify\">x2+y2=r2. We can start with a known point on the circle say (xk,yk) in the chosen octant. Let the next point to be computed be represented as (xk+1,yk+1). Since we are sampling on x-axis at unit x-intervals, it is evident that the next x, xk+1= xk+1.<\/p>\n<p>&nbsp;<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"size-full wp-image-68 aligncenter\" src=\"http:\/\/csp06.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/52\/2018\/07\/1-32.png\" alt=\"\" width=\"276\" height=\"185\" srcset=\"https:\/\/ebooks.inflibnet.ac.in\/csp06\/wp-content\/uploads\/sites\/52\/2018\/07\/1-32.png 276w, https:\/\/ebooks.inflibnet.ac.in\/csp06\/wp-content\/uploads\/sites\/52\/2018\/07\/1-32-65x44.png 65w, https:\/\/ebooks.inflibnet.ac.in\/csp06\/wp-content\/uploads\/sites\/52\/2018\/07\/1-32-225x151.png 225w\" sizes=\"auto, (max-width: 276px) 100vw, 276px\" \/><\/p>\n<p>As we know from theory that any point x, y that satisfy the relation<\/p>\n<ul>\n<li>x2+y2-r2 &lt;0 is a point that lies inside the circle boundary<\/li>\n<li>x2+y2-r2 &gt;0 is a point that lies outside the circle boundary<\/li>\n<li>x2+y2-r2 =0 is a point that lies on the circle boundary<\/li>\n<\/ul>\n<\/div>\n<div>\n<p style=\"text-align: justify\">For the next x position xk+1, we can choose between two y positions yk or yk-1. Compute midpoint for the two possible pixel locations (xk+1, yk) (xk+1, yk-1) and verify its position relative to the circle boundary. If the midpoint lies inside the circle boundary choose to plot the upper pixel else the lower pixel. The coordinates of the midpoint are for the two possible pixels positions (x<sub>k+1<\/sub>, y<sub>k<\/sub>) or (x<sub>k+1,<\/sub> y<sub>k-1<\/sub>) are (?<sub>?<\/sub> + ?, ?<sub>?<\/sub> \u2212 ?\/2\u00a0)<\/p>\n<p>&nbsp;<\/p>\n<p style=\"text-align: justify\">Now by substituting the coordinates of the midpoint, in the circle equation, we can check whether the midpoint lies inside, outside or on the circle boundary. Thus the decision parameter <strong><em>P<\/em><\/strong><strong><em>k<\/em><\/strong> for our derivation is given by<\/p>\n<\/div>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"size-full wp-image-69 aligncenter\" src=\"http:\/\/csp06.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/52\/2018\/07\/1-33.png\" alt=\"\" width=\"246\" height=\"27\" srcset=\"https:\/\/ebooks.inflibnet.ac.in\/csp06\/wp-content\/uploads\/sites\/52\/2018\/07\/1-33.png 246w, https:\/\/ebooks.inflibnet.ac.in\/csp06\/wp-content\/uploads\/sites\/52\/2018\/07\/1-33-65x7.png 65w, https:\/\/ebooks.inflibnet.ac.in\/csp06\/wp-content\/uploads\/sites\/52\/2018\/07\/1-33-225x25.png 225w\" sizes=\"auto, (max-width: 246px) 100vw, 246px\" \/><\/p>\n<div>\n<p>&nbsp;<\/p>\n<p style=\"text-align: justify\">i.e., <strong><em>P<\/em><\/strong><strong><em>k<\/em><\/strong><strong><em>&lt;0,<\/em><\/strong> means that midpoint is inside the circle boundary, so the circle boundary is close to the upper pixel, thus choose the upper pixel (xk+1, yk) for plotting, otherwise if <strong><em>P<\/em><\/strong><strong><em>k<\/em><\/strong><strong><em>&gt;0,<\/em><\/strong> the midpoint is outside the circle boundary, so the circle boundary is close to the lower pixel, thus choose the lower pixel (xk+1, yk-1) for plotting, or otherwise if <strong><em>P<\/em><\/strong><strong><em>k<\/em><\/strong><strong>=<em>0<\/em><\/strong>, the midpoint lies on the circle boundary, so we can choose between either of upper and lower pixels and so for consistency we can choose the upper pixel, for this case.<\/p>\n<p>&nbsp;<\/p>\n<p>&nbsp;<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"size-full wp-image-70 aligncenter\" src=\"http:\/\/csp06.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/52\/2018\/07\/1-34.png\" alt=\"\" width=\"370\" height=\"406\" srcset=\"https:\/\/ebooks.inflibnet.ac.in\/csp06\/wp-content\/uploads\/sites\/52\/2018\/07\/1-34.png 370w, https:\/\/ebooks.inflibnet.ac.in\/csp06\/wp-content\/uploads\/sites\/52\/2018\/07\/1-34-273x300.png 273w, https:\/\/ebooks.inflibnet.ac.in\/csp06\/wp-content\/uploads\/sites\/52\/2018\/07\/1-34-65x71.png 65w, https:\/\/ebooks.inflibnet.ac.in\/csp06\/wp-content\/uploads\/sites\/52\/2018\/07\/1-34-225x247.png 225w, https:\/\/ebooks.inflibnet.ac.in\/csp06\/wp-content\/uploads\/sites\/52\/2018\/07\/1-34-350x384.png 350w\" sizes=\"auto, (max-width: 370px) 100vw, 370px\" \/><\/p>\n<p>&nbsp;<\/p>\n<p>&nbsp;<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"size-full wp-image-71 aligncenter\" src=\"http:\/\/csp06.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/52\/2018\/07\/1-35.png\" alt=\"\" width=\"611\" height=\"220\" srcset=\"https:\/\/ebooks.inflibnet.ac.in\/csp06\/wp-content\/uploads\/sites\/52\/2018\/07\/1-35.png 611w, https:\/\/ebooks.inflibnet.ac.in\/csp06\/wp-content\/uploads\/sites\/52\/2018\/07\/1-35-300x108.png 300w, https:\/\/ebooks.inflibnet.ac.in\/csp06\/wp-content\/uploads\/sites\/52\/2018\/07\/1-35-65x23.png 65w, https:\/\/ebooks.inflibnet.ac.in\/csp06\/wp-content\/uploads\/sites\/52\/2018\/07\/1-35-225x81.png 225w, https:\/\/ebooks.inflibnet.ac.in\/csp06\/wp-content\/uploads\/sites\/52\/2018\/07\/1-35-350x126.png 350w\" sizes=\"auto, (max-width: 611px) 100vw, 611px\" \/><\/p>\n<p>&nbsp;<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"size-full wp-image-72 aligncenter\" src=\"http:\/\/csp06.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/52\/2018\/07\/1-36.png\" alt=\"\" width=\"593\" height=\"533\" srcset=\"https:\/\/ebooks.inflibnet.ac.in\/csp06\/wp-content\/uploads\/sites\/52\/2018\/07\/1-36.png 593w, https:\/\/ebooks.inflibnet.ac.in\/csp06\/wp-content\/uploads\/sites\/52\/2018\/07\/1-36-300x270.png 300w, https:\/\/ebooks.inflibnet.ac.in\/csp06\/wp-content\/uploads\/sites\/52\/2018\/07\/1-36-65x58.png 65w, https:\/\/ebooks.inflibnet.ac.in\/csp06\/wp-content\/uploads\/sites\/52\/2018\/07\/1-36-225x202.png 225w, https:\/\/ebooks.inflibnet.ac.in\/csp06\/wp-content\/uploads\/sites\/52\/2018\/07\/1-36-350x315.png 350w\" sizes=\"auto, (max-width: 593px) 100vw, 593px\" \/><\/p>\n<\/div>\n<p style=\"padding-left: 30px;text-align: justify\">Problem: Find the points on a circle on of its octants with the circle centered at (5,5) and has a radius of 8 units.<\/p>\n<p style=\"padding-left: 30px;text-align: justify\">Solution: Assume that the circle is centered at origin and proceed to solve. After finding the points add center (5, 5) to each point.<\/p>\n<p style=\"padding-left: 30px;text-align: justify\">The initial point (x0,y0)=(0,8)<\/p>\n<p style=\"padding-left: 30px;text-align: justify\">P0 = 1-r = 1-8=-7<br \/>\n(x0,y0) = (0, 8)<br \/>\nP0=-7<br \/>\nP1=-7+2+1=-4 (-ve, case (i))<br \/>\nP2=-4+4+1=1<br \/>\n(+ve, case (ii))<br \/>\nP3=1+6-14+1=-6 (-ve, case (i))<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"size-full wp-image-73 aligncenter\" src=\"http:\/\/csp06.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/52\/2018\/07\/1-37.png\" alt=\"\" width=\"206\" height=\"165\" srcset=\"https:\/\/ebooks.inflibnet.ac.in\/csp06\/wp-content\/uploads\/sites\/52\/2018\/07\/1-37.png 206w, https:\/\/ebooks.inflibnet.ac.in\/csp06\/wp-content\/uploads\/sites\/52\/2018\/07\/1-37-65x52.png 65w\" sizes=\"auto, (max-width: 206px) 100vw, 206px\" \/><\/p>\n<p>&nbsp;<\/p>\n<p><strong>Conclusion:<\/strong><\/p>\n<p>&nbsp;<\/p>\n<p>Midpoint circle drawing algorithm is more efficient, due to<\/p>\n<ul>\n<li>Recursive nature of the algorithm<\/li>\n<li>No floating point calculations<\/li>\n<li>Accurate and simple<\/li>\n<\/ul>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"size-full wp-image-74 aligncenter\" src=\"http:\/\/csp06.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/52\/2018\/07\/1-38.png\" alt=\"\" width=\"654\" height=\"283\" srcset=\"https:\/\/ebooks.inflibnet.ac.in\/csp06\/wp-content\/uploads\/sites\/52\/2018\/07\/1-38.png 654w, https:\/\/ebooks.inflibnet.ac.in\/csp06\/wp-content\/uploads\/sites\/52\/2018\/07\/1-38-300x130.png 300w, https:\/\/ebooks.inflibnet.ac.in\/csp06\/wp-content\/uploads\/sites\/52\/2018\/07\/1-38-65x28.png 65w, https:\/\/ebooks.inflibnet.ac.in\/csp06\/wp-content\/uploads\/sites\/52\/2018\/07\/1-38-225x97.png 225w, https:\/\/ebooks.inflibnet.ac.in\/csp06\/wp-content\/uploads\/sites\/52\/2018\/07\/1-38-350x151.png 350w\" sizes=\"auto, (max-width: 654px) 100vw, 654px\" \/><\/p>\n<table>\n<tbody>\n<tr>\n<td><strong>you can view video on Midpoint Circle Drawing Procedure<\/strong><\/td>\n<td><a href=\"https:\/\/youtu.be\/UWp8R1-Gzzg\" target=\"_blank\" rel=\"noopener\"><img loading=\"lazy\" decoding=\"async\" class=\"alignnone wp-image-120\" src=\"http:\/\/epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/2018\/11\/download.png\" alt=\"\" width=\"36\" height=\"36\" \/><\/a><\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n","protected":false},"author":3,"menu_order":4,"template":"","meta":{"pb_show_title":"on","pb_short_title":"","pb_subtitle":"","pb_authors":["dr-t-raghuveera"],"pb_section_license":""},"chapter-type":[],"contributor":[59],"license":[],"class_list":["post-60","chapter","type-chapter","status-publish","hentry","contributor-dr-t-raghuveera"],"part":3,"_links":{"self":[{"href":"https:\/\/ebooks.inflibnet.ac.in\/csp06\/wp-json\/pressbooks\/v2\/chapters\/60","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/ebooks.inflibnet.ac.in\/csp06\/wp-json\/pressbooks\/v2\/chapters"}],"about":[{"href":"https:\/\/ebooks.inflibnet.ac.in\/csp06\/wp-json\/wp\/v2\/types\/chapter"}],"author":[{"embeddable":true,"href":"https:\/\/ebooks.inflibnet.ac.in\/csp06\/wp-json\/wp\/v2\/users\/3"}],"version-history":[{"count":11,"href":"https:\/\/ebooks.inflibnet.ac.in\/csp06\/wp-json\/pressbooks\/v2\/chapters\/60\/revisions"}],"predecessor-version":[{"id":602,"href":"https:\/\/ebooks.inflibnet.ac.in\/csp06\/wp-json\/pressbooks\/v2\/chapters\/60\/revisions\/602"}],"part":[{"href":"https:\/\/ebooks.inflibnet.ac.in\/csp06\/wp-json\/pressbooks\/v2\/parts\/3"}],"metadata":[{"href":"https:\/\/ebooks.inflibnet.ac.in\/csp06\/wp-json\/pressbooks\/v2\/chapters\/60\/metadata\/"}],"wp:attachment":[{"href":"https:\/\/ebooks.inflibnet.ac.in\/csp06\/wp-json\/wp\/v2\/media?parent=60"}],"wp:term":[{"taxonomy":"chapter-type","embeddable":true,"href":"https:\/\/ebooks.inflibnet.ac.in\/csp06\/wp-json\/pressbooks\/v2\/chapter-type?post=60"},{"taxonomy":"contributor","embeddable":true,"href":"https:\/\/ebooks.inflibnet.ac.in\/csp06\/wp-json\/wp\/v2\/contributor?post=60"},{"taxonomy":"license","embeddable":true,"href":"https:\/\/ebooks.inflibnet.ac.in\/csp06\/wp-json\/wp\/v2\/license?post=60"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}