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

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

   
Visit the ZANavi Wiki