home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #31 / NN_1992_31.iso / spool / comp / graphics / 13165 < prev    next >
Encoding:
Text File  |  1992-12-23  |  1.5 KB  |  35 lines
  1. Newsgroups: comp.graphics
  2. Path: sparky!uunet!news.smith.edu!orourke
  3. From: orourke@sophia.smith.edu (Joseph O'Rourke)
  4. Subject: Re: How many dots in a circle?
  5. Message-ID: <1992Dec23.170712.9468@sophia.smith.edu>
  6. Organization: Smith College, Northampton, MA, US
  7. References: <1992Dec22.134450.15558@cactus.org> <1992Dec23.031735.13264@proto.com> <1992Dec23.161707.22424@unocal.com>
  8. Date: Wed, 23 Dec 1992 17:07:12 GMT
  9. Lines: 24
  10.  
  11. In article <1992Dec23.161707.22424@unocal.com> stgprao@st.unocal.COM (Richard Ottolini) writes:
  12. >In article <1992Dec23.031735.13264@proto.com> joe@proto.com (Joe Huffman) writes:
  13. >>The number of points in a single quadrant is 2 * radius.  In the entire 
  14. >>circle it follows that it is 8 * radius.  
  15. >
  16. >Counter example on a piece of graph paper for box edge = 15:
  17.  
  18. I believe Richard is on the right track, though.  In the octant between 45 deg
  19. and the vertical y-axis, most circle algorithms color one pixel per x value.
  20. So one only need count these and multiply by 8.  For a radius r circle,
  21. the x coordinate of the intersection of the circle with the 45 deg y=x line
  22. is (Sqrt[2]/2) r.  So the number of pixels colored in one octant is
  23.  
  24.     o = Floor[ (Sqrt[2]/2) r ]
  25.  
  26. Example: r=17, o = Floor[ 12.02 ] = 12.  The total (8 o) does not
  27. count the pixels directly on the four radii at 45, 135, 225, and 315 degs.
  28. So it must be incremented by 4.  The total number of pixels n is therefore
  29.  
  30.     n = 8 Floor[ (Sqrt[2]/2) r ]  +  4
  31.  
  32. Example: r=17, n = 100.
  33.     Maybe someone who has Bresenham's algorithm implemented can
  34. check my calculations?
  35.