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