home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #26 / NN_1992_26.iso / spool / comp / graphics / 11617 < prev    next >
Encoding:
Internet Message Format  |  1992-11-09  |  3.4 KB

  1. Path: sparky!uunet!munnari.oz.au!bruce.cs.monash.edu.au!monu6!escargot!minyos.xx.rmit.oz.au!rcskb
  2. From: rcskb@minyos.xx.rmit.oz.au (Kendall Bennett)
  3. Newsgroups: comp.graphics
  4. Subject: Re: Simple Convexity Working Group (preliminary report)
  5. Date: 9 Nov 1992 01:58:44 GMT
  6. Organization: RMIT Computer Centre
  7. Lines: 78
  8. Message-ID: <1dkgkkINNj14@escargot.xx.rmit.OZ.AU>
  9. References: <720421504.10@freudsys.nl.mugnet>
  10. NNTP-Posting-Host: minyos.xx.rmit.oz.au
  11.  
  12. Kenneth.Sloan@freudsys.nl.mugnet.org (Kenneth Sloan) writes:
  13.  
  14. >Organization: CIS, University of Alabama at Birmingham
  15.  
  16. >>...A polygon is either 
  17. >>convex, or non-convex.
  18.  
  19. >Is the following polygon "convex"?
  20.  
  21. >0 0
  22. >1 0
  23. >1 1
  24. >0 0 
  25. >1 0
  26. >1 1
  27.  
  28. In my books it definitately is. It is not simple, but it is convex. Why
  29. would you ever need to handle this sort of poly except in dicussions about
  30. whether they are convex or not?
  31.  
  32. >>... Mathematical definitions of convex polygons abound,
  33.  
  34. >Please supply a pointer to an unambiguous, complete, authoritative
  35. >definition.  Definitions of convex sets abound.  Polygons (as we have
  36. >been treating them) , on the other hand, are *boundaries* - not the
  37. >interior.  The *path* of the boundary curve counts just as much as the
  38. >set of points enclosed by the boundary.
  39.  
  40. Polygons are generally used to model the set of points contained within
  41. the polygon boundary. How do you think you get the definition of which 
  42. pixels to draw for self intersecting polygons? Convex sets are bounded
  43. by convex polygons. In the paper that I mentione by Chazelle and Dobkin,
  44. a good defintion of a convex polygon is given. Obviously not complete
  45. and authoritative, since you would naturally find some counter example
  46. which no-one would ever see in practice.
  47.  
  48. >>so why the need to say that it is convex and SIMPLE? If it is convex, it
  49. >>MUST be simple.
  50.  
  51. >Oh really?  See the polygon above.  Is it "convex"?  Is it simple?  How
  52. >about this one:
  53.  
  54. Ok, so it may be non-simple but still convex as in the above example.
  55.  
  56. >0 0
  57. >2 0
  58. >1 2
  59. >1 1
  60. >1 2
  61.  
  62. >Is it convex?  Is it concave?  Is it simple?
  63.  
  64. It is concave. It is also simple in my books. It has two co-incident edges
  65. in it bounding an empty set of points, but if your traces it's border
  66. it is concave (ie: non-convex, you could scan convert this poly with a 
  67. general polygon scan conversion routine).
  68.  
  69. >> If it is not convex, then it must be concave.
  70.  
  71. >Why is it necessary to bring in the concept of "concave"?  We started
  72. >with "convex", and "simple", and constructed two classes: "convex and
  73. >simple" and "not convex or not simple".  Why do you need "concave"?
  74.  
  75. You don't. But why can't you simply say convex or not convex?
  76.  
  77. >By the way...we're still waiting for your code.
  78.  
  79. Yeah well, it is all hot air at the moment. I haven't had time to work
  80. on it, and I don't know when I will. Choose a winner without me :-)
  81.  
  82. +------------------------------------------+-------------------------------+
  83. | Kendall Bennett                          | Internet:                     |
  84. | RMIT Advanced Computer Graphics Centre   | kjb@citri.edu.au              |
  85. | CITRI Building, 723 Swanston Street      | rcskb@minyos.xx.rmit.oz.au    |
  86. | Carlton Victoria 3053 AUSTRALIA.         |                               | 
  87. +------------------------------------------+-------------------------------+
  88. | CoSysop (Bossman), PC Connection Australia:               +61 3 688 0909 |
  89. +--------------------------------------------------------------------------+
  90.