home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #16 / NN_1992_16.iso / spool / comp / graphics / 8240 < prev    next >
Encoding:
Text File  |  1992-07-28  |  2.5 KB  |  49 lines
  1. Newsgroups: comp.graphics
  2. Path: sparky!uunet!stanford.edu!leland.Stanford.EDU!leland.Stanford.EDU!ledwards
  3. From: ledwards@leland.Stanford.EDU (Laurence James Edwards)
  4. Subject: Re: Converting polygon with concave boundary to convex one anybody?
  5. Message-ID: <1992Jul28.221518.27272@leland.Stanford.EDU>
  6. Sender: news@leland.Stanford.EDU (Mr News)
  7. Organization: DSG, Stanford University, CA 94305, USA
  8. References:  <9207281143.AA27417@ucbvax.Berkeley.EDU>
  9. Date: Tue, 28 Jul 92 22:15:18 GMT
  10. Lines: 37
  11.  
  12. In article <9207281143.AA27417@ucbvax.Berkeley.EDU>, S.Marshall@sequent.cc.hull.ac.uk (Simon Marshall) writes:
  13. |> Hi all.  I mailed this question a while back, but shortly after the machine I
  14. |> read news on hiccuped for a couple of days, and now I find out that our mailer
  15. |> fails, with a loss of incoming mail, on a regular basis.  If you've responded
  16. |> once, please do again, sorry!
  17. |> 
  18. |> I have a group of planar polygons with concave boundaries.  I wish to replace
  19. |> each of these polygons with a number of triangular ones.  For a polygon with a
  20. |> convex boundary, it's quiet easy.  All I do is pick a single polygon vertex and
  21. |> form triangular facets, using this vertex, with successive pairs of vertices
  22. |> around the polygon boundary.  The single polygon vertex is therefore common to
  23. |> all triangular facets.
  24. |> 
  25. |> This, of course, will not work for polygons whose boundaries are concave, since
  26. |> a triangular facet may lie outside the boundary of the polygon.  So either I
  27. |> must use a different method of generating triangular facets, or firstly
  28. |> generate polygons with convex boundaries from the polygons with concave
  29. |> boundaries.
  30. |> 
  31. |> The $64M question is, how do I convert a concave polygon to a convex one?  I
  32. |> thought there was a solution to this in Graphics GEMS, but nope...
  33.  
  34. Just Delauney triangulate the thing, throwing out edges that lie outside the
  35. polygon ... i.e. connect each vertex to its nearest neighbor, but only if the
  36. edge does not leave the polygon. This will leave you with a bunch of triangles
  37. and possibly some convex regions. Split up the convex regions using your
  38. old method.
  39.  
  40. The most straight forward way to do this is recursion ... go through the
  41. list of vertices for a polygon, when you find a vertex that you
  42. can connect to its nearest neighbor split the polygon and apply the
  43. same procedure to the 2 new polygons. If there are no vertices in the 
  44. polygon that can be connected to their nearest neighbor, then the polygon
  45. is convex and you can split it up with your old method and return.
  46.  
  47. Larry Edwards
  48. edwards@sunrise.stanford.edu
  49.