/[zanavi_public1]/navit/navit/maptool/poly2tri-c/002/poly2tri-c/refine/cdt.c
ZANavi

Contents of /navit/navit/maptool/poly2tri-c/002/poly2tri-c/refine/cdt.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: 15441 byte(s)
new map version, lots of fixes and experimental new features
1 /*
2 * This file is a part of Poly2Tri-C
3 * (c) Barak Itkin <lightningismyname@gmail.com>
4 * http://code.google.com/p/poly2tri-c/
5 *
6 * All rights reserved.
7 *
8 * Redistribution and use in source and binary forms, with or without modification,
9 * are permitted provided that the following conditions are met:
10 *
11 * * Redistributions of source code must retain the above copyright notice,
12 * this list of conditions and the following disclaimer.
13 * * Redistributions in binary form must reproduce the above copyright notice,
14 * this list of conditions and the following disclaimer in the documentation
15 * and/or other materials provided with the distribution.
16 * * Neither the name of Poly2Tri nor the names of its contributors may be
17 * used to endorse or promote products derived from this software without specific
18 * prior written permission.
19 *
20 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
21 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
22 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
23 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR
24 * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
25 * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
26 * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
27 * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
28 * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
29 * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
30 * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
31 */
32
33 #include <stdarg.h>
34 #include <glib.h>
35
36 #include "point.h"
37 #include "edge.h"
38 #include "triangle.h"
39
40 #include "cdt.h"
41 #include "visibility.h"
42 #include "cdt-flipfix.h"
43
44 static gboolean p2tr_cdt_visible_from_tri (P2trCDT *self,
45 P2trTriangle *tri,
46 P2trVector2 *p);
47
48 static gboolean p2tr_cdt_has_empty_circum_circle (P2trCDT *self,
49 P2trTriangle *tri);
50
51 static P2trHashSet* p2tr_cdt_triangulate_fan (P2trCDT *self,
52 P2trPoint *center,
53 GList *edge_pts);
54
55 void
56 p2tr_cdt_validate_unused (P2trCDT* self)
57 {
58 P2trEdge *ed;
59 P2trTriangle *tri;
60 P2trHashSetIter iter;
61
62 p2tr_hash_set_iter_init (&iter, self->mesh->edges);
63 while (p2tr_hash_set_iter_next (&iter, (gpointer*)&ed))
64 {
65 g_assert (ed->mirror != NULL);
66 g_assert (! p2tr_edge_is_removed (ed));
67 }
68
69 p2tr_hash_set_iter_init (&iter, self->mesh->triangles);
70 while (p2tr_hash_set_iter_next (&iter, (gpointer*)&tri))
71 g_assert (! p2tr_triangle_is_removed (tri));
72 }
73
74 P2trCDT*
75 p2tr_cdt_new (P2tCDT *cdt)
76 {
77 P2tTrianglePtrArray cdt_tris = p2t_cdt_get_triangles (cdt);
78 GHashTable *point_map = g_hash_table_new (g_direct_hash, g_direct_equal);
79 P2trCDT *rmesh = g_slice_new (P2trCDT);
80 GHashTableIter iter;
81 P2trPoint *pt_iter = NULL;
82
83 P2trVEdgeSet *new_edges = p2tr_vedge_set_new ();
84
85 gint i, j;
86
87 rmesh->mesh = p2tr_mesh_new ();
88 rmesh->outline = p2tr_pslg_new ();
89
90 /* First iteration over the CDT - create all the points */
91 for (i = 0; i < cdt_tris->len; i++)
92 {
93 P2tTriangle *cdt_tri = triangle_index (cdt_tris, i);
94 for (j = 0; j < 3; j++)
95 {
96 P2tPoint *cdt_pt = p2t_triangle_get_point(cdt_tri, j);
97 P2trPoint *new_pt = (P2trPoint*) g_hash_table_lookup (point_map, cdt_pt);
98
99 if (new_pt == NULL)
100 {
101 new_pt = p2tr_mesh_new_point2 (rmesh->mesh, cdt_pt->x, cdt_pt->y);
102 g_hash_table_insert (point_map, cdt_pt, new_pt);
103 }
104 }
105 }
106
107 /* Second iteration over the CDT - create all the edges and find the
108 * outline */
109 for (i = 0; i < cdt_tris->len; i++)
110 {
111 P2tTriangle *cdt_tri = triangle_index (cdt_tris, i);
112
113 for (j = 0; j < 3; j++)
114 {
115 P2tPoint *start = p2t_triangle_get_point (cdt_tri, j);
116 P2tPoint *end = p2t_triangle_get_point (cdt_tri, (j + 1) % 3);
117 int edge_index = p2t_triangle_edge_index (cdt_tri, start, end);
118
119 P2trPoint *start_new = (P2trPoint*) g_hash_table_lookup (point_map, start);
120 P2trPoint *end_new = (P2trPoint*) g_hash_table_lookup (point_map, end);
121
122 if (! p2tr_point_has_edge_to (start_new, end_new))
123 {
124 gboolean constrained = cdt_tri->constrained_edge[edge_index]
125 || cdt_tri->neighbors_[edge_index] == NULL;
126 P2trEdge *edge = p2tr_mesh_new_edge (rmesh->mesh, start_new, end_new, constrained);
127
128 /* If the edge is constrained, we should add it to the
129 * outline */
130 if (constrained)
131 p2tr_pslg_add_new_line(rmesh->outline, &start_new->c,
132 &end_new->c);
133
134 /* We only wanted to create the edge now. We will use it
135 * later */
136 p2tr_vedge_set_add (new_edges, edge);
137 }
138 }
139 }
140
141 /* Third iteration over the CDT - create all the triangles */
142 for (i = 0; i < cdt_tris->len; i++)
143 {
144 P2tTriangle *cdt_tri = triangle_index (cdt_tris, i);
145
146 P2trPoint *pt1 = (P2trPoint*) g_hash_table_lookup (point_map, p2t_triangle_get_point (cdt_tri, 0));
147 P2trPoint *pt2 = (P2trPoint*) g_hash_table_lookup (point_map, p2t_triangle_get_point (cdt_tri, 1));
148 P2trPoint *pt3 = (P2trPoint*) g_hash_table_lookup (point_map, p2t_triangle_get_point (cdt_tri, 2));
149
150 P2trTriangle *new_tri = p2tr_mesh_new_triangle (rmesh->mesh,
151 p2tr_point_get_edge_to(pt1, pt2, FALSE),
152 p2tr_point_get_edge_to(pt2, pt3, FALSE),
153 p2tr_point_get_edge_to(pt3, pt1, FALSE));
154
155 /* We won't do any usage of the triangle, so just unref it */
156 p2tr_triangle_unref (new_tri);
157 }
158
159 /* And do an extra flip fix */
160 p2tr_cdt_flip_fix (rmesh, new_edges);
161
162 p2tr_vedge_set_free (new_edges);
163
164 /* Now finally unref the points we added into the map */
165 g_hash_table_iter_init (&iter, point_map);
166 while (g_hash_table_iter_next (&iter, NULL, (gpointer*)&pt_iter))
167 p2tr_point_unref (pt_iter);
168 g_hash_table_destroy (point_map);
169
170 return rmesh;
171 }
172
173 void
174 p2tr_cdt_free (P2trCDT *self)
175 {
176 p2tr_cdt_free_full (self, TRUE);
177 }
178
179 void
180 p2tr_cdt_free_full (P2trCDT* self, gboolean clear_mesh)
181 {
182 p2tr_pslg_free (self->outline);
183 if (clear_mesh)
184 p2tr_mesh_clear (self->mesh);
185 p2tr_mesh_unref (self->mesh);
186
187 g_slice_free (P2trCDT, self);
188 }
189
190 void
191 p2tr_cdt_validate_edges (P2trCDT *self)
192 {
193 P2trHashSetIter iter;
194 P2trEdge *e;
195
196 p2tr_hash_set_iter_init (&iter, self->mesh->edges);
197 while (p2tr_hash_set_iter_next (&iter, (gpointer*)&e))
198 {
199 if (! e->constrained && e->tri == NULL)
200 p2tr_exception_geometric ("Found a non constrained edge without a triangle");
201
202 if (e->tri != NULL)
203 {
204 gboolean found = FALSE;
205 gint i = 0;
206
207 for (i = 0; i < 3; i++)
208 if (e->tri->edges[i] == e)
209 {
210 found = TRUE;
211 break;
212 }
213
214 if (! found)
215 p2tr_exception_geometric ("An edge has a triangle to which it does not belong!");
216 }
217 }
218 }
219
220 gboolean
221 p2tr_cdt_visible_from_edge (P2trCDT *self,
222 P2trEdge *e,
223 P2trVector2 *p)
224 {
225 P2trBoundedLine line;
226
227 p2tr_bounded_line_init (&line, &P2TR_EDGE_START(e)->c, &e->end->c);
228
229 return p2tr_visibility_is_visible_from_edges (self->outline, p, &line, 1);
230 }
231
232 static gboolean
233 p2tr_cdt_visible_from_tri (P2trCDT *self,
234 P2trTriangle *tri,
235 P2trVector2 *p)
236 {
237 P2trBoundedLine lines[3];
238 gint i;
239
240 for (i = 0; i < 3; i++)
241 p2tr_bounded_line_init (&lines[i],
242 &P2TR_EDGE_START(tri->edges[i])->c,
243 &tri->edges[i]->end->c);
244
245 return p2tr_visibility_is_visible_from_edges (self->outline, p, lines, 3);
246 }
247
248 static gboolean
249 p2tr_cdt_has_empty_circum_circle (P2trCDT *self,
250 P2trTriangle *tri)
251 {
252 P2trCircle circum;
253 P2trPoint *p;
254 P2trHashSetIter iter;
255
256 p2tr_triangle_get_circum_circle (tri, &circum);
257
258 p2tr_hash_set_iter_init (&iter, self->mesh->points);
259 while (p2tr_hash_set_iter_next (&iter, (gpointer*)&p))
260 {
261 /** TODO: FIXME - is a point on a constrained edge really not a
262 * problem?! */
263 if (p2tr_point_has_constrained_edge (p)
264 /* The points of a triangle can't violate its own empty
265 * circumcircle property */
266 || p == tri->edges[0]->end
267 || p == tri->edges[1]->end
268 || p == tri->edges[2]->end)
269 continue;
270
271 if (! p2tr_circle_test_point_outside(&circum, &p->c)
272 && p2tr_cdt_visible_from_tri (self, tri, &p->c))
273 return FALSE;
274 }
275 return TRUE;
276 }
277
278 void
279 p2tr_cdt_validate_cdt (P2trCDT *self)
280 {
281 P2trHashSetIter iter;
282 P2trTriangle *tri;
283
284 p2tr_hash_set_iter_init (&iter, self->mesh->triangles);
285 while (p2tr_hash_set_iter_next (&iter, (gpointer*)&tri))
286 if (! p2tr_cdt_has_empty_circum_circle(self, tri))
287 p2tr_exception_geometric ("Not a CDT!");
288 }
289
290 P2trPoint*
291 p2tr_cdt_insert_point (P2trCDT *self,
292 const P2trVector2 *pc,
293 P2trTriangle *point_location_guess)
294 {
295 P2trTriangle *tri;
296 P2trPoint *pt;
297 gboolean inserted = FALSE;
298 gint i;
299
300 P2TR_CDT_VALIDATE_UNUSED (self);
301
302 if (point_location_guess == NULL)
303 tri = p2tr_mesh_find_point (self->mesh, pc);
304 else
305 tri = p2tr_mesh_find_point_local (self->mesh, pc, point_location_guess);
306
307 if (tri == NULL)
308 p2tr_exception_geometric ("Tried to add point outside of domain!");
309
310 pt = p2tr_mesh_new_point (self->mesh, pc);
311
312 /* If the point falls on a line, we should split the line */
313 for (i = 0; i < 3; i++)
314 {
315 P2trEdge *edge = tri->edges[i];
316 if (p2tr_math_orient2d (& P2TR_EDGE_START(edge)->c,
317 &edge->end->c, pc) == P2TR_ORIENTATION_LINEAR)
318 {
319 GList *parts = p2tr_cdt_split_edge (self, edge, pt), *eIter;
320 for (eIter = parts; eIter != NULL; eIter = eIter->next)
321 p2tr_edge_unref ((P2trEdge*)eIter->data);
322 inserted = TRUE;
323 break;
324 }
325 }
326
327 if (! inserted)
328 /* If we reached this line, then the point is inside the triangle */
329 p2tr_cdt_insert_point_into_triangle (self, pt, tri);
330
331 /* We no longer need the triangle */
332 p2tr_triangle_unref (tri);
333
334 P2TR_CDT_VALIDATE_UNUSED (self);
335 return pt;
336 }
337
338 /** Insert a point into a triangle. This function assumes the point is
339 * inside the triangle - not on one of its edges and not outside of it.
340 */
341 void
342 p2tr_cdt_insert_point_into_triangle (P2trCDT *self,
343 P2trPoint *P,
344 P2trTriangle *tri)
345 {
346 P2trVEdgeSet *flip_candidates = p2tr_vedge_set_new ();
347
348 P2trPoint *A = tri->edges[0]->end;
349 P2trPoint *B = tri->edges[1]->end;
350 P2trPoint *C = tri->edges[2]->end;
351
352 P2trEdge *CA = tri->edges[0];
353 P2trEdge *AB = tri->edges[1];
354 P2trEdge *BC = tri->edges[2];
355
356 P2trEdge *AP, *BP, *CP;
357
358 p2tr_triangle_remove (tri);
359
360 AP = p2tr_mesh_new_edge (self->mesh, A, P, FALSE);
361 BP = p2tr_mesh_new_edge (self->mesh, B, P, FALSE);
362 CP = p2tr_mesh_new_edge (self->mesh, C, P, FALSE);
363
364 p2tr_triangle_unref (p2tr_mesh_new_triangle (self->mesh, AB, BP, AP->mirror));
365 p2tr_triangle_unref (p2tr_mesh_new_triangle (self->mesh, BC, CP, BP->mirror));
366 p2tr_triangle_unref (p2tr_mesh_new_triangle (self->mesh, CA, AP, CP->mirror));
367
368 p2tr_vedge_set_add (flip_candidates, CP);
369 p2tr_vedge_set_add (flip_candidates, AP);
370 p2tr_vedge_set_add (flip_candidates, BP);
371
372 p2tr_vedge_set_add (flip_candidates, p2tr_edge_ref (CA));
373 p2tr_vedge_set_add (flip_candidates, p2tr_edge_ref (AB));
374 p2tr_vedge_set_add (flip_candidates, p2tr_edge_ref (BC));
375
376 /* Flip fix the newly created triangles to preserve the the
377 * constrained delaunay property. The flip-fix function will unref the
378 * new triangles for us! */
379 p2tr_cdt_flip_fix (self, flip_candidates);
380
381 p2tr_vedge_set_free (flip_candidates);
382 }
383
384 /**
385 * Triangulate a polygon by creating edges to a center point.
386 * 1. If there is a NULL point in the polygon, two triangles are not
387 * created (these are the two that would have used it)
388 * 2. THE RETURNED EDGES MUST BE UNREFFED!
389 */
390 static P2trVEdgeSet*
391 p2tr_cdt_triangulate_fan (P2trCDT *self,
392 P2trPoint *center,
393 GList *edge_pts)
394 {
395 P2trVEdgeSet* fan_edges = p2tr_vedge_set_new ();
396 GList *iter;
397
398 /* We can not triangulate unless at least two points are given */
399 if (edge_pts == NULL || edge_pts->next == NULL)
400 {
401 p2tr_exception_programmatic ("Not enough points to triangulate as"
402 " a star!");
403 }
404
405 for (iter = edge_pts; iter != NULL; iter = iter->next)
406 {
407 P2trPoint *A = (P2trPoint*) iter->data;
408 P2trPoint *B = (P2trPoint*) g_list_cyclic_next (edge_pts, iter)->data;
409 P2trEdge *AB, *BC, *CA;
410
411 if (A == NULL || B == NULL)
412 continue;
413
414 AB = p2tr_point_get_edge_to (A, B, TRUE);
415 BC = p2tr_mesh_new_or_existing_edge (self->mesh, B, center, FALSE);
416 CA = p2tr_mesh_new_or_existing_edge (self->mesh, center, A, FALSE);
417
418 p2tr_triangle_unref (p2tr_mesh_new_triangle (self->mesh, AB, BC, CA));
419
420 p2tr_vedge_set_add (fan_edges, CA);
421 p2tr_vedge_set_add (fan_edges, BC);
422 p2tr_vedge_set_add (fan_edges, AB);
423 }
424
425 return fan_edges;
426 }
427
428 GList*
429 p2tr_cdt_split_edge (P2trCDT *self,
430 P2trEdge *e,
431 P2trPoint *C)
432 {
433 /* W
434 * /|\
435 * / | \
436 * / | \ E.Mirror.Tri: YXW
437 * X*---*---*Y E: X->Y
438 * \ |C / E.Tri: XYV
439 * \ | /
440 * \|/
441 * V
442 */
443 P2trPoint *X = P2TR_EDGE_START (e), *Y = e->end;
444 P2trPoint *V = (e->tri != NULL) ? p2tr_triangle_get_opposite_point(e->tri, e, FALSE) : NULL;
445 P2trPoint *W = (e->mirror->tri != NULL) ? p2tr_triangle_get_opposite_point (e->mirror->tri, e->mirror, FALSE) : NULL;
446 gboolean constrained = e->constrained;
447 P2trEdge *XC, *CY;
448 GList *fan = NULL, *new_edges = NULL;
449 P2trHashSet *fan_edges;
450
451 P2TR_CDT_VALIDATE_UNUSED (self);
452
453 p2tr_edge_remove (e);
454
455 XC = p2tr_mesh_new_edge (self->mesh, X, C, constrained);
456 CY = p2tr_mesh_new_edge (self->mesh, C, Y, constrained);
457
458 fan = p2tr_utils_new_reversed_pointer_list (4, W, X, V, Y);
459 fan_edges = p2tr_cdt_triangulate_fan (self, C, fan);
460 g_list_free (fan);
461
462 /* Now make this a CDT again
463 * The new triangles will be unreffed by the flip_fix function, which
464 * is good since we receive them with an extra reference!
465 */
466 p2tr_cdt_flip_fix (self, fan_edges);
467 p2tr_hash_set_free (fan_edges);
468
469 if (constrained)
470 {
471 /* If this was a subsegment, then both parts of the subsegment
472 * should exist */
473 if (p2tr_edge_is_removed (XC) || p2tr_edge_is_removed (CY))
474 p2tr_exception_geometric ("Subsegments gone!");
475 else
476 {
477 new_edges = g_list_prepend (new_edges, CY);
478 new_edges = g_list_prepend (new_edges, XC);
479 }
480 }
481 else
482 {
483 p2tr_edge_unref (XC);
484 p2tr_edge_unref (CY);
485 }
486
487 P2TR_CDT_VALIDATE_UNUSED (self);
488
489 return new_edges;
490 }
491

   
Visit the ZANavi Wiki