/[zanavi_public1]/navit/navit/maptool/poly2tri-c/002/poly2tri-c/p2t/sweep/sweep_context.c
ZANavi

Contents of /navit/navit/maptool/poly2tri-c/002/poly2tri-c/p2t/sweep/sweep_context.c

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 MIME type: text/plain
File size: 8657 byte(s)
new map version, lots of fixes and experimental 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 #include "sweep_context.h"
37 #include "advancing_front.h"
38
39 void
40 p2t_sweepcontext_basin_init (P2tSweepContextBasin* THIS)
41 {
42 p2t_sweepcontext_basin_clear (THIS);
43 }
44
45 void
46 p2t_sweepcontext_basin_clear (P2tSweepContextBasin* THIS)
47 {
48 THIS->left_node = NULL;
49 THIS->bottom_node = NULL;
50 THIS->right_node = NULL;
51 THIS->width = 0.0;
52 THIS->left_highest = FALSE;
53 }
54
55 void
56 p2t_sweepcontext_edgeevent_init (P2tSweepContextEdgeEvent* THIS)
57 {
58 THIS->constrained_edge = NULL;
59 THIS->right = FALSE;
60 }
61
62 void
63 p2t_sweepcontext_init (P2tSweepContext* THIS, P2tPointPtrArray polyline)
64 {
65 int i;
66 THIS->edge_list = g_ptr_array_new ();
67 THIS->triangles_ = g_ptr_array_new ();
68 THIS->map_ = NULL;
69
70 p2t_sweepcontext_basin_init (&THIS->basin);
71 p2t_sweepcontext_edgeevent_init (&THIS->edge_event);
72
73 THIS->points_ = g_ptr_array_sized_new (polyline->len);
74 for (i = 0; i < polyline->len; i++)
75 g_ptr_array_add (THIS->points_, point_index (polyline, i));
76
77 p2t_sweepcontext_init_edges (THIS, THIS->points_);
78 }
79
80 P2tSweepContext*
81 p2t_sweepcontext_new (P2tPointPtrArray polyline)
82 {
83 P2tSweepContext* THIS = g_new (P2tSweepContext, 1);
84 p2t_sweepcontext_init (THIS, polyline);
85 return THIS;
86 }
87
88 void
89 p2t_sweepcontext_destroy (P2tSweepContext* THIS)
90 {
91 GList* iter;
92 int i;
93 /* Clean up memory */
94
95 p2t_point_free (THIS->head_);
96 p2t_point_free (THIS->tail_);
97 p2t_advancingfront_free (THIS->front_);
98 p2t_node_free (THIS->af_head_);
99 p2t_node_free (THIS->af_middle_);
100 p2t_node_free (THIS->af_tail_);
101
102 g_ptr_array_free (THIS->points_, TRUE);
103 g_ptr_array_free (THIS->triangles_, TRUE);
104
105 for (iter = g_list_first (THIS->map_); iter != NULL; iter = g_list_next (iter))
106 {
107 P2tTriangle* ptr = triangle_val (iter);
108 g_free (ptr);
109 }
110
111 g_list_free (THIS->map_);
112
113 for (i = 0; i < THIS->edge_list->len; i++)
114 {
115 p2t_edge_free (edge_index (THIS->edge_list, i));
116 }
117
118 g_ptr_array_free (THIS->edge_list, TRUE);
119
120 }
121
122 void
123 p2t_sweepcontext_delete (P2tSweepContext* THIS)
124 {
125 p2t_sweepcontext_destroy (THIS);
126 g_free(THIS);
127 }
128
129 void
130 p2t_sweepcontext_add_hole (P2tSweepContext *THIS, P2tPointPtrArray polyline)
131 {
132 int i;
133 p2t_sweepcontext_init_edges (THIS, polyline);
134 for (i = 0; i < polyline->len; i++)
135 {
136 g_ptr_array_add (THIS->points_, point_index (polyline, i));
137 }
138 }
139
140 void
141 p2t_sweepcontext_add_point (P2tSweepContext *THIS, P2tPoint* point)
142 {
143 g_ptr_array_add (THIS->points_, point);
144 }
145
146 P2tTrianglePtrArray
147 p2t_sweepcontext_get_triangles (P2tSweepContext *THIS)
148 {
149 return THIS->triangles_;
150 }
151
152 P2tTrianglePtrList
153 p2t_sweepcontext_get_map (P2tSweepContext *THIS)
154 {
155 return THIS->map_;
156 }
157
158 void
159 p2t_sweepcontext_init_triangulation (P2tSweepContext *THIS)
160 {
161 int i;
162 double xmax = point_index (THIS->points_, 0)->x, xmin = point_index (THIS->points_, 0)->x;
163 double ymax = point_index (THIS->points_, 0)->y, ymin = point_index (THIS->points_, 0)->y;
164 double dx, dy;
165
166 /* Calculate bounds. */
167 for (i = 0; i < THIS->points_->len; i++)
168 {
169 P2tPoint* p = point_index (THIS->points_, i);
170 if (p->x > xmax)
171 xmax = p->x;
172 if (p->x < xmin)
173 xmin = p->x;
174 if (p->y > ymax)
175 ymax = p->y;
176 if (p->y < ymin)
177 ymin = p->y;
178 }
179
180 dx = kAlpha * (xmax - xmin);
181 dy = kAlpha * (ymax - ymin);
182 THIS->head_ = p2t_point_new_dd (xmax + dx, ymin - dy);
183 THIS->tail_ = p2t_point_new_dd (xmin - dx, ymin - dy);
184
185 /* Sort points along y-axis */
186 g_ptr_array_sort (THIS->points_, p2t_point_cmp);
187 }
188
189 void
190 p2t_sweepcontext_init_edges (P2tSweepContext *THIS, P2tPointPtrArray polyline)
191 {
192 int i;
193 int num_points = polyline->len;
194 g_ptr_array_set_size (THIS->edge_list, THIS->edge_list->len + num_points); /* C-OPTIMIZATION */
195 for (i = 0; i < num_points; i++)
196 {
197 int j = i < num_points - 1 ? i + 1 : 0;
198 g_ptr_array_add (THIS->edge_list, p2t_edge_new (point_index (polyline, i), point_index (polyline, j)));
199 }
200 }
201
202 P2tPoint*
203 p2t_sweepcontext_get_point (P2tSweepContext *THIS, const int index)
204 {
205 return point_index (THIS->points_, index);
206 }
207
208 void
209 p2t_sweepcontext_add_to_map (P2tSweepContext *THIS, P2tTriangle* triangle)
210 {
211 THIS->map_ = g_list_append (THIS->map_, triangle);
212 }
213
214 P2tNode*
215 p2t_sweepcontext_locate_node (P2tSweepContext *THIS, P2tPoint* point)
216 {
217 /* TODO implement search tree */
218 return p2t_advancingfront_locate_node (THIS->front_, point->x);
219 }
220
221 void
222 p2t_sweepcontext_create_advancingfront (P2tSweepContext *THIS, P2tNodePtrArray nodes)
223 {
224 /* Initial triangle */
225 P2tTriangle* triangle = p2t_triangle_new (point_index (THIS->points_, 0), THIS->tail_, THIS->head_);
226
227 THIS->map_ = g_list_append (THIS->map_, triangle);
228
229 THIS->af_head_ = p2t_node_new_pt_tr (p2t_triangle_get_point (triangle, 1), triangle);
230 THIS->af_middle_ = p2t_node_new_pt_tr (p2t_triangle_get_point (triangle, 0), triangle);
231 THIS->af_tail_ = p2t_node_new_pt (p2t_triangle_get_point (triangle, 2));
232 THIS->front_ = p2t_advancingfront_new (THIS->af_head_, THIS->af_tail_);
233
234 /* TODO: More intuitiv if head is middles next and not previous?
235 * so swap head and tail */
236 THIS->af_head_->next = THIS->af_middle_;
237 THIS->af_middle_->next = THIS->af_tail_;
238 THIS->af_middle_->prev = THIS->af_head_;
239 THIS->af_tail_->prev = THIS->af_middle_;
240 }
241
242 void
243 p2t_sweepcontext_remove_node (P2tSweepContext *THIS, P2tNode* node)
244 {
245 g_free (node);
246 }
247
248 void
249 p2t_sweepcontext_map_triangle_to_nodes (P2tSweepContext *THIS, P2tTriangle* t)
250 {
251 int i;
252 for (i = 0; i < 3; i++)
253 {
254 if (!p2t_triangle_get_neighbor (t, i))
255 {
256 P2tNode* n = p2t_advancingfront_locate_point (THIS->front_, p2t_triangle_point_cw (t, p2t_triangle_get_point (t, i)));
257 if (n)
258 n->triangle = t;
259 }
260 }
261 }
262
263 void
264 p2t_sweepcontext_remove_from_map (P2tSweepContext *THIS, P2tTriangle* triangle)
265 {
266 THIS->map_ = g_list_remove (THIS->map_, triangle);
267 }
268
269 void
270 p2t_sweepcontext_mesh_clean (P2tSweepContext *THIS, P2tTriangle* triangle)
271 {
272 int i;
273 if (triangle != NULL && !p2t_triangle_is_interior (triangle))
274 {
275 p2t_triangle_is_interior_b (triangle, TRUE);
276 g_ptr_array_add (THIS->triangles_, triangle);
277 for (i = 0; i < 3; i++)
278 {
279 if (!triangle->constrained_edge[i])
280 p2t_sweepcontext_mesh_clean (THIS, p2t_triangle_get_neighbor (triangle, i));
281 }
282 }
283 }
284
285 P2tAdvancingFront*
286 p2t_sweepcontext_front (P2tSweepContext *THIS)
287 {
288 return THIS->front_;
289 }
290
291 int
292 p2t_sweepcontext_point_count (P2tSweepContext *THIS)
293 {
294 return THIS->points_->len;
295 }
296
297 void
298 p2t_sweepcontext_set_head (P2tSweepContext *THIS, P2tPoint* p1)
299 {
300 THIS->head_ = p1;
301 }
302
303 P2tPoint*
304 p2t_sweepcontext_head (P2tSweepContext *THIS)
305 {
306 return THIS->head_;
307 }
308
309 void
310 p2t_sweepcontext_set_tail (P2tSweepContext *THIS, P2tPoint* p1)
311 {
312 THIS->tail_ = p1;
313 }
314
315 P2tPoint*
316 p2t_sweepcontext_tail (P2tSweepContext *THIS)
317 {
318 return THIS->tail_;
319 }

   
Visit the ZANavi Wiki