home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1993 #3 / NN_1993_3.iso / spool / comp / graphics / research / 460 < prev    next >
Encoding:
Internet Message Format  |  1993-01-21  |  2.1 KB
  1. Path: sparky!uunet!gatech!mailer.cc.fsu.edu!sun13!med.umich.edu
  2. From: spencer@med.umich.edu (Spencer W. Thomas)
  3. Newsgroups: comp.graphics.research
  4. Subject: Re: Clipping point generation
  5. Message-ID: <11781@sun13.scri.fsu.edu>
  6. Date: 20 Jan 93 23:17:33 GMT
  7. References: <11717@sun13.scri.fsu.edu>
  8. Sender: news@sun13.scri.fsu.edu
  9. Organization: University of Michigan
  10. Lines: 38
  11. Approved: murray@vs6.scri.fsu.edu
  12. Nntp-Posting-Host: guraldi.itn.med.umich.edu
  13. X-Submissions-To: graphics@scri1.scri.fsu.edu
  14. X-Administrivia-To: graphics-request@scri1.scri.fsu.edu
  15.  
  16. Here's a sketch of a proof that the upper bound is 2N+4:
  17.  
  18. A concave polygon P has Nx convex vertices and Nv concave vertices,
  19. where Nx >= (N+1)/2 and Nv<Nx.  (For N even, Nv <= Nx-2.)
  20.  
  21. A concave vertex flanked by two convex vertices can contribute 4
  22. vertices to the clipped polygon when all three vertices lie outside
  23. the clipping region.
  24.  
  25. 6 more vertices can be introduced by clipping the convex hull of the
  26. polygon against the clipping region.
  27.  
  28. For even N, the maximum number of concave vertices is N/2 - 1, so the
  29. number of clipped vertices from concave vertices is 
  30.     4*(N/2 - 1) = 2N - 2.
  31. Adding the 6 from the convex hull yields 2N + 4.
  32.  
  33. For odd N, the largest number of concave vertices that can be flanked
  34. by convex vertices on both sides is (N-1)/2 - 1, so the total becomes
  35.     4*((N-1)/2 - 1) + 6 (+ 1) = 2N-3 + 6 (+ 1) = 2N + 3 (+ 1)
  36. The (+ 1) in parentheses is potentially contributed by the "extra"
  37. convex vertex, if it is inside the clipping region, again yielding a
  38. maximum of 2N+4.
  39.  
  40. A more careful analysis would count the contribution by edges
  41. according to classification of their endpoints, but I am convinced
  42. that the result would be the same.
  43.  
  44. Of course, I'm equally happy to be proved wrong.
  45.  
  46. --
  47. =Spencer W. Thomas         |  Info Tech and Networking, B1911 CFOB, 0704
  48.    "Genome Informatician"    |  Univ of Michigan, Ann Arbor, MI 48109
  49. Spencer.W.Thomas@med.umich.edu    |  313-747-2778, FAX 313-764-4133
  50.  
  51. --
  52. Moderated by SCRI Vis <>           Submissions to: graphics@scri1.scri.fsu.edu
  53. Guy, John R. Murray   <> Administrivia to: graphics-request@scri1.scri.fsu.edu
  54.