home *** CD-ROM | disk | FTP | other *** search
/ RISC DISC 3 / RISC_DISC_3.iso / resources / etexts / gems / gemsv / ch7_5 / readme. < prev    next >
Text File  |  1995-03-04  |  2KB  |  54 lines
  1.     This program is an implementation of a fast polygon
  2. triangulation algorithm based on the paper "A simple and fast
  3. incremental randomized algorithm for computing trapezoidal
  4. decompositions and for triangulating polygons" by Raimund Seidel.
  5.  
  6.     The input is specified as a list of points (x, y). If the
  7. polygon has n distinct vertices (the n+1 th vertex being the same as
  8. the 1st vertex), then the file should contain only the n distinct
  9. vertices in ANTI-CLOCKWISE order. Also, the polygon should be simple
  10. (i.e. non self-intersecting) with NO HOLES. A sample data file is
  11. included in the package (Notice the no point is repeated).
  12.  
  13.     Triangulation should produce (n - 2) triangles as the output.
  14. (i.e. no additional vertices are introduced). The result is available
  15. in the array triangles[][3], where each of triangles[0] to
  16. triangles[n-3] contain the 3 vertices forming the triangle (the
  17. vertices are numbered 1..n accoring to the input). The vertices of
  18. each triangle are output in anti-clockwise order.
  19.     
  20.     Use gmake to create the executable. (There sould not be
  21. any compilation problem. If log2() is not defined in your math
  22. library, you will have to supply the definition)
  23.  
  24.     
  25. USAGE:
  26.     triangulate <filename>
  27.  
  28. Bibliography:
  29.  
  30. (Seidel 1991) R. Seidel. A simple and fast incremental randomized
  31. algorithm for computing trapezoidal decompositions for triangulating
  32. polygons. Computational Geometry: Theory and applications,
  33. 1(1991):51-64. 
  34.  
  35. (Fournier et al. 84) A. Fournier and D.Y. Montuno, Triangulating
  36. simple polygons and equivalent problems, ACM Trans. on Graphics 3
  37. (1984) 153-174.
  38.  
  39. Implementation report: Narkhede A. and Manocha D., Fast polygon
  40.  triangulation algorithm based on Seidel's Algorithm, UNC-CH, 1994.
  41.  
  42. -------------------------------------------------------------------
  43.  
  44. This code is in the public domain. Specifically, we give to the public
  45. domain all rights for future licensing of the source code, all resale
  46. rights, and all publishing rights.
  47.  
  48. UNC-CH GIVES NO WARRANTY, EXPRESSED OR IMPLIED, FOR THE SOFTWARE
  49. AND/OR DOCUMENTATION PROVIDED, INCLUDING, WITHOUT LIMITATION, WARRANTY
  50. OF MERCHANTABILITY AND WARRANTY OF FITNESS FOR A PARTICULAR PURPOSE.
  51.  
  52.  
  53.                 - Atul Narkhede (narkhede@cs.unc.edu)
  54.