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)
|