home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #16 / NN_1992_16.iso / spool / comp / graphics / 8228 < prev    next >
Encoding:
Internet Message Format  |  1992-07-28  |  2.2 KB
  1. Path: sparky!uunet!dtix!darwin.sura.net!mips!odin!fido!zhu
  2. From: zhu@sgi.com (Benjamin Zhu)
  3. Newsgroups: comp.graphics
  4. Subject: Re: Converting polygon with concave boundary to convex one anybody?
  5. Message-ID: <ns5o6r8@fido.asd.sgi.com>
  6. Date: 28 Jul 92 15:28:12 GMT
  7. References: <9207281143.AA27417@ucbvax.Berkeley.EDU>
  8. Sender: news@fido.asd.sgi.com (Usenet News Admin)
  9. Organization: Silicon Graphics, Inc.
  10. Lines: 39
  11.  
  12. In article <9207281143.AA27417@ucbvax.Berkeley.EDU> sm@cs.hull.ac.uk, S.Marshall@hull.ac.uk writes:
  13. >
  14. >I have a group of planar polygons with concave boundaries.  I wish to replace
  15. >each of these polygons with a number of triangular ones.  For a polygon with a
  16. >convex boundary, it's quiet easy.  All I do is pick a single polygon vertex and
  17. >form triangular facets, using this vertex, with successive pairs of vertices
  18. >around the polygon boundary.  The single polygon vertex is therefore common to
  19. >all triangular facets.
  20. >
  21. >This, of course, will not work for polygons whose boundaries are concave, since
  22. >a triangular facet may lie outside the boundary of the polygon.  So either I
  23. >must use a different method of generating triangular facets, or firstly
  24. >generate polygons with convex boundaries from the polygons with concave
  25. >boundaries.
  26. >
  27.  
  28.     Well, I finally got ten-minute free time before flying to Siggraph.
  29.     No rescue after siggraph though. Hopefully, I can help you out
  30.     before I plunge into endless ucode and bug fixes again.
  31.  
  32.     Look up Preparata and Shamos book, ``Introduction to Computational
  33.     Geometry.'' They elaborated a number of O(n*log(n)) algorithms
  34.     there to do what you wanted.
  35.  
  36.     As long as you have a 2-3 tree or an avl tree implementation around,
  37.     it should be pretty straightforward to implement any of these
  38.     algorithms.
  39.  
  40.     See you guys at siggraph. Do not forget to drop by our booth. Our
  41.     Venice machines (marketing buzz words, RealityEngine) are going to
  42.     knock many people's pants off:-)
  43.  
  44.     Ben
  45.  
  46. --
  47. Benjamin Zhu             ;;; ``Recently-promoted shinto'' priest of microcode
  48. Silicon Graphics, Inc.   ;;; ``Just call my name, I will be there.''
  49. zhu@graphack.asd.sgi.com ;;; ``Projective geometry is all geometry.'' - Cayley
  50. (415) 390-1187           ;;; ``Learn forever, young forever.'' - Anonymous
  51.