/[zanavi_public1]/navit/navit/maptool/p2t/sweep/sweep.h
ZANavi

Contents of /navit/navit/maptool/p2t/sweep/sweep.h

Parent Directory Parent Directory | Revision Log Revision Log


Revision 37 - (show annotations) (download)
Sat Mar 8 21:37:20 2014 UTC (10 years ago) by zoff99
File MIME type: text/plain
File size: 9839 byte(s)
new market version, lots of new features
1 /*
2 * This file is a part of the C port of the Poly2Tri library
3 * Porting to C done by (c) Barak Itkin <lightningismyname@gmail.com>
4 * http://code.google.com/p/poly2tri-c/
5 *
6 * Poly2Tri Copyright (c) 2009-2010, Poly2Tri Contributors
7 * http://code.google.com/p/poly2tri/
8 *
9 * All rights reserved.
10 *
11 * Redistribution and use in source and binary forms, with or without modification,
12 * are permitted provided that the following conditions are met:
13 *
14 * * Redistributions of source code must retain the above copyright notice,
15 * this list of conditions and the following disclaimer.
16 * * Redistributions in binary form must reproduce the above copyright notice,
17 * this list of conditions and the following disclaimer in the documentation
18 * and/or other materials provided with the distribution.
19 * * Neither the name of Poly2Tri nor the names of its contributors may be
20 * used to endorse or promote products derived from this software without specific
21 * prior written permission.
22 *
23 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
24 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
25 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
26 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR
27 * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
28 * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
29 * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
30 * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
31 * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
32 * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
33 * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
34 */
35
36 /**
37 * Sweep-line, Constrained Delauney Triangulation (CDT) See: Domiter, V. and
38 * Zalik, B.(2008)'Sweep-line algorithm for constrained Delaunay triangulation',
39 * International Journal of Geographical Information Science
40 *
41 * "FlipScan" Constrained Edge Algorithm invented by Thomas �hl�n, thahlen@gmail.com
42 */
43
44 #ifndef __P2TC_P2T_SWEEP_H__
45 #define __P2TC_P2T_SWEEP_H__
46
47 #include "../common/poly2tri-private.h"
48 #include "../common/shapes.h"
49
50 struct Sweep_
51 {
52 /* private: */
53 P2tNodePtrArray nodes_;
54
55 };
56
57 void p2t_sweep_init (P2tSweep* THIS);
58 P2tSweep* p2t_sweep_new ();
59
60 /**
61 * Destructor - clean up memory
62 */
63 void p2t_sweep_destroy (P2tSweep* THIS);
64 void p2t_sweep_free (P2tSweep* THIS);
65
66 /**
67 * Triangulate
68 *
69 * @param tcx
70 */
71 void p2t_sweep_triangulate (P2tSweep *THIS, P2tSweepContext *tcx);
72
73 /**
74 * Start sweeping the Y-sorted point set from bottom to top
75 *
76 * @param tcx
77 */
78 void p2t_sweep_sweep_points (P2tSweep *THIS, P2tSweepContext *tcx);
79
80 /**
81 * Find closes node to the left of the new point and
82 * create a new triangle. If needed new holes and basins
83 * will be filled to.
84 *
85 * @param tcx
86 * @param point
87 * @return
88 */
89 P2tNode* p2t_sweep_point_event (P2tSweep *THIS, P2tSweepContext *tcx, P2tPoint* point);
90
91 /**
92 *
93 *
94 * @param tcx
95 * @param edge
96 * @param node
97 */
98 void p2t_sweep_edge_event_ed_n (P2tSweep *THIS, P2tSweepContext *tcx, P2tEdge* edge, P2tNode* node);
99
100 void p2t_sweep_edge_event_pt_pt_tr_pt (P2tSweep *THIS, P2tSweepContext *tcx, P2tPoint* ep, P2tPoint* eq, P2tTriangle* triangle, P2tPoint* point);
101
102 /**
103 * Creates a new front triangle and legalize it
104 *
105 * @param tcx
106 * @param point
107 * @param node
108 * @return
109 */
110 P2tNode* p2t_sweep_new_front_triangle (P2tSweep *THIS, P2tSweepContext *tcx, P2tPoint* point, P2tNode* node);
111
112 /**
113 * Adds a triangle to the advancing front to fill a hole.
114 * @param tcx
115 * @param node - middle node, that is the bottom of the hole
116 */
117 void p2t_sweep_fill (P2tSweep *THIS, P2tSweepContext *tcx, P2tNode* node);
118
119 /**
120 * Returns true if triangle was legalized
121 */
122 gboolean p2t_sweep_legalize (P2tSweep *THIS, P2tSweepContext *tcx, P2tTriangle *t);
123
124 /**
125 * <b>Requirement</b>:<br>
126 * 1. a,b and c form a triangle.<br>
127 * 2. a and d is know to be on opposite side of bc<br>
128 * <pre>
129 * a
130 * +
131 * / \
132 * / \
133 * b/ \c
134 * +-------+
135 * / d \
136 * / \
137 * </pre>
138 * <b>Fact</b>: d has to be in area B to have a chance to be inside the circle formed by
139 * a,b and c<br>
140 * d is outside B if orient2d(a,b,d) or orient2d(c,a,d) is CW<br>
141 * This preknowledge gives us a way to optimize the incircle test
142 * @param a - triangle point, opposite d
143 * @param b - triangle point
144 * @param c - triangle point
145 * @param d - point opposite a
146 * @return true if d is inside circle, false if on circle edge
147 */
148 gboolean p2t_sweep_incircle (P2tSweep *THIS, P2tPoint* pa, P2tPoint* pb, P2tPoint* pc, P2tPoint* pd);
149
150 /**
151 * Rotates a triangle pair one vertex CW
152 *<pre>
153 * n2 n2
154 * P +-----+ P +-----+
155 * | t /| |\ t |
156 * | / | | \ |
157 * n1| / |n3 n1| \ |n3
158 * | / | after CW | \ |
159 * |/ oT | | oT \|
160 * +-----+ oP +-----+
161 * n4 n4
162 * </pre>
163 */
164 void p2t_sweep_rotate_triangle_pair (P2tSweep *THIS, P2tTriangle *t, P2tPoint* p, P2tTriangle *ot, P2tPoint* op);
165
166 /**
167 * Fills holes in the Advancing Front
168 *
169 *
170 * @param tcx
171 * @param n
172 */
173 void p2t_sweep_fill_advancingfront (P2tSweep *THIS, P2tSweepContext *tcx, P2tNode* n);
174
175 /* Decision-making about when to Fill hole.
176 * Contributed by ToolmakerSteve2 */
177 gboolean p2t_sweep_large_hole_dont_fill (P2tSweep* THIS, P2tNode* node);
178 gboolean p2t_sweep_angle_exceeds_90_degrees (P2tSweep* THIS, P2tPoint* origin, P2tPoint* pa, P2tPoint* pb);
179 gboolean p2t_sweep_angle_exceeds_plus_90_degrees_or_is_negative (P2tSweep* THIS, P2tPoint* origin, P2tPoint* pa, P2tPoint* pb);
180 gdouble p2t_sweep_angle (P2tSweep* THIS, P2tPoint* origin, P2tPoint* pa, P2tPoint* pb);
181
182 /**
183 *
184 * @param node - middle node
185 * @return the angle between 3 front nodes
186 */
187 double p2t_sweep_hole_angle (P2tSweep *THIS, P2tNode* node);
188
189 /**
190 * The basin angle is decided against the horizontal line [1,0]
191 */
192 double p2t_sweep_basin_angle (P2tSweep *THIS, P2tNode* node);
193
194 /**
195 * Fills a basin that has formed on the Advancing Front to the right
196 * of given node.<br>
197 * First we decide a left,bottom and right node that forms the
198 * boundaries of the basin. Then we do a reqursive fill.
199 *
200 * @param tcx
201 * @param node - starting node, this or next node will be left node
202 */
203 void p2t_sweep_fill_basin (P2tSweep *THIS, P2tSweepContext *tcx, P2tNode* node);
204
205 /**
206 * Recursive algorithm to fill a Basin with triangles
207 *
208 * @param tcx
209 * @param node - bottom_node
210 * @param cnt - counter used to alternate on even and odd numbers
211 */
212 void p2t_sweep_fill_basin_req (P2tSweep *THIS, P2tSweepContext *tcx, P2tNode* node);
213
214 gboolean p2t_sweep_is_shallow (P2tSweep *THIS, P2tSweepContext *tcx, P2tNode* node);
215
216 gboolean p2t_sweep_is_edge_side_of_triangle (P2tSweep *THIS, P2tTriangle *triangle, P2tPoint* ep, P2tPoint* eq);
217
218 void p2t_sweep_fill_edge_event (P2tSweep *THIS, P2tSweepContext *tcx, P2tEdge* edge, P2tNode* node);
219
220 void p2t_sweep_fill_right_above_edge_event (P2tSweep *THIS, P2tSweepContext *tcx, P2tEdge* edge, P2tNode* node);
221
222 void p2t_sweep_fill_right_below_edge_event (P2tSweep *THIS, P2tSweepContext *tcx, P2tEdge* edge, P2tNode* node);
223
224 void p2t_sweep_fill_right_concave_edge_event (P2tSweep *THIS, P2tSweepContext *tcx, P2tEdge* edge, P2tNode* node);
225
226 void p2t_sweep_fill_right_convex_edge_event (P2tSweep *THIS, P2tSweepContext *tcx, P2tEdge* edge, P2tNode* node);
227
228 void p2t_sweep_fill_left_above_edge_event (P2tSweep *THIS, P2tSweepContext *tcx, P2tEdge* edge, P2tNode* node);
229
230 void p2t_sweep_fill_left_below_edge_event (P2tSweep *THIS, P2tSweepContext *tcx, P2tEdge* edge, P2tNode* node);
231
232 void p2t_sweep_fill_left_concave_edge_event (P2tSweep *THIS, P2tSweepContext *tcx, P2tEdge* edge, P2tNode* node);
233
234 void p2t_sweep_fill_left_convex_edge_event (P2tSweep *THIS, P2tSweepContext *tcx, P2tEdge* edge, P2tNode* node);
235
236 void p2t_sweep_flip_edge_event (P2tSweep *THIS, P2tSweepContext *tcx, P2tPoint* ep, P2tPoint* eq, P2tTriangle* t, P2tPoint* p);
237
238 /**
239 * After a flip we have two triangles and know that only one will still be
240 * intersecting the edge. So decide which to contiune with and legalize the other
241 *
242 * @param tcx
243 * @param o - should be the result of an orient2d( eq, op, ep )
244 * @param t - triangle 1
245 * @param ot - triangle 2
246 * @param p - a point shared by both triangles
247 * @param op - another point shared by both triangles
248 * @return returns the triangle still intersecting the edge
249 */
250 P2tTriangle* p2t_sweep_next_flip_triangle (P2tSweep *THIS, P2tSweepContext *tcx, int o, P2tTriangle *t, P2tTriangle *ot, P2tPoint* p, P2tPoint* op);
251
252 /**
253 * When we need to traverse from one triangle to the next we need
254 * the point in current triangle that is the opposite point to the next
255 * triangle.
256 *
257 * @param ep
258 * @param eq
259 * @param ot
260 * @param op
261 * @return
262 */
263 P2tPoint* p2t_sweep_next_flip_point (P2tSweep *THIS, P2tPoint* ep, P2tPoint* eq, P2tTriangle *ot, P2tPoint* op);
264
265 /**
266 * Scan part of the FlipScan algorithm<br>
267 * When a triangle pair isn't flippable we will scan for the next
268 * point that is inside the flip triangle scan area. When found
269 * we generate a new flipEdgeEvent
270 *
271 * @param tcx
272 * @param ep - last point on the edge we are traversing
273 * @param eq - first point on the edge we are traversing
274 * @param flipTriangle - the current triangle sharing the point eq with edge
275 * @param t
276 * @param p
277 */
278 void p2t_sweep_flip_scan_edge_event (P2tSweep *THIS, P2tSweepContext *tcx, P2tPoint* ep, P2tPoint* eq, P2tTriangle *flip_triangle, P2tTriangle *t, P2tPoint* p);
279
280 void p2t_sweep_finalization_polygon (P2tSweep *THIS, P2tSweepContext *tcx);
281
282 #endif

   
Visit the ZANavi Wiki