home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #20 / NN_1992_20.iso / spool / comp / graphics / 9586 < prev    next >
Encoding:
Text File  |  1992-09-09  |  2.3 KB  |  48 lines
  1. Newsgroups: comp.graphics
  2. Path: sparky!uunet!munnari.oz.au!bruce.cs.monash.edu.au!edwarda
  3. From: edwarda@cs.monash.edu.au (Edward Fok Iao Au)
  4. Subject: Polygon Decomposition & Delaunay Triangulation
  5. Message-ID: <edwarda.716104366@bruce.cs.monash.edu.au>
  6. Keywords: polygon decomposition triangulation voronoi Delaunay
  7. Sender: news@bruce.cs.monash.edu.au (USENET News System)
  8. Organization: Computer Science, Monash University, Australia
  9. Date: Thu, 10 Sep 1992 05:52:46 GMT
  10. Lines: 36
  11.  
  12. I have a problem with decomposing an arbitrary polygon into a set of
  13. optimal triangles.
  14.  
  15. At first, I considered using Delaunay Triangulation for this task, so
  16. I had written up a SGI GL-based GUI for Delaunay Triangulation using
  17. sweepline algorithm. When I fed a set of points into the program, it
  18. turned out fine and did produce a mesh of optimal triangles over the
  19. points.
  20.  
  21. However, the problem arises when it is applied to decomposing a polygon.
  22. Consider a hook-shaped polygon (ie. extremely concave), the sweepline
  23. triangulation algorithm tesselates the vertices without considering the
  24. integrity or structure of the polygon. The final tesselation would have
  25. triangles partially inside and outside the polgyon and hence would not
  26. serve to decompose the polygon.
  27.  
  28. What I really want is to be able to decompose an arbitary polygon (with
  29. no hole in it) into *optimal triangles*. I already have code to decompose
  30. such a polygon into triangles what are not optimal at all (the algorithm
  31. repeatedly finds a valid triangle and removes it from the vertex list,
  32. until only three vertices are left) but the code does not serve my need.
  33.  
  34. Could anyone please suggest how I might modify the sweepline algorithm to
  35. cater for polygon decomposition, or direct me to some other sources of
  36. generic optimal polygon decomposition algorithms, or anything pointers?
  37.  
  38. Thanks in advance,
  39.  
  40. Edward
  41. ______________________________________________________________________________
  42.  
  43. e-mail: edwarda@bruce.cs.monash.edu.au                           _--_|\
  44. Department of Computer Science                                  /      \
  45. Monash University (Clayton Campus)                              \_.--. /
  46. Australia                                                             V
  47. ______________________________________________________________________________
  48.