/[zanavi_public1]/navit/navit/maptool/poly2tri-c/001/seidel-1.0/README
ZANavi

Contents of /navit/navit/maptool/poly2tri-c/001/seidel-1.0/README

Parent Directory Parent Directory | Revision Log Revision Log


Revision 31 - (show annotations) (download)
Mon Feb 4 17:41:59 2013 UTC (11 years, 1 month ago) by zoff99
File size: 3189 byte(s)
new map version, lots of fixes and experimental new features
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
7 The algorithm handles simple polygons with holes. The input is
8 specified as contours. The outermost contour is anti-clockwise, while
9 all the inner contours must be clockwise. No point should be repeated
10 in the input. A sample input file 'data_1' is provided.
11
12
13 The output is a list of triangles. Each triangle gives a pair
14 (i, j, k) where i, j, and k are indices of the vertices specified in
15 the input array. (The index numbering starts from 1, since the first
16 location v[0] in the input array of vertices is unused). The number of
17 output triangles produced for a polygon with n points is,
18 (n - 2) + 2*(#holes)
19
20
21 The algorithm also generates a qyery structure which can be
22 used to answer point-location queries very fast.
23
24 int triangulate_polygon(...)
25 Time for triangulation: O(n log*n)
26
27 int is_point_inside_polygon(...)
28 Time for query: O(log n)
29
30 Both the routines are defined in 'tri.c'. See that file for
31 interfacing details. If not used stand_alone, include the header file
32 "interface.h" which contains the declarations for these
33 functions. Inclusion of "triangulation.h" is not necessary.
34
35
36 The implementation uses statically allocated arrays. Choose
37 appropriate value for SEGSIZE /* in triangulate.h */ depending on
38 input size.
39
40
41 There sould not be any compilation problem. If log2() is not
42 defined in your math library, you will have to supply the definition.
43
44
45 USAGE:
46 triangulate <filename> /* For standalone */
47
48
49 ------------------------------------------------------------------
50 Bibliography:
51
52
53 @article{Sei91,
54 AUTHOR = "R. Seidel",
55 TITLE = "A simple and Fast Randomized Algorithm for Computing Trapezoidal Decompositions and for Triangulating Polygons",
56 JOURNAL = "Computational Geometry Theory \& Applications",
57 PAGES = "51-64",
58 NUMBER = 1,
59 YEAR = 1991,
60 VOLUME = 1 }
61
62
63 @book{o-cgc-94
64 , author = "J. O'Rourke"
65 , title = "Computational Geometry in {C}"
66 , publisher = "Cambridge University Press"
67 , year = 1994
68 , note = "ISBN 0-521-44592-2/Pb \$24.95,
69 ISBN 0-521-44034-3/Hc \$49.95.
70 Cambridge University Press
71 40 West 20th Street
72 New York, NY 10011-4211
73 1-800-872-7423
74 346+xi pages, 228 exercises, 200 figures, 219 references"
75 , update = "94.05 orourke, 94.01 orourke"
76 , annote = "Textbook"
77 }
78
79
80
81 Implementation report: Narkhede A. and Manocha D., Fast polygon
82 triangulation algorithm based on Seidel's Algorithm, UNC-CH, 1994.
83
84 -------------------------------------------------------------------
85
86 This code is free for non-commercial use only.
87
88 UNC-CH GIVES NO WARRANTY, EXPRESSED OR IMPLIED, FOR THE SOFTWARE
89 AND/OR DOCUMENTATION PROVIDED, INCLUDING, WITHOUT LIMITATION, WARRANTY
90 OF MERCHANTABILITY AND WARRANTY OF FITNESS FOR A PARTICULAR PURPOSE.
91
92 - Atul Narkhede (narkhede@cs.unc.edu)

   
Visit the ZANavi Wiki