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

Contents of /navit/navit/maptool/poly2tri-c/002/poly2tri-c/refine/cdt-flipfix.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: 5897 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 <glib.h>
34
35 #include "point.h"
36 #include "edge.h"
37 #include "triangle.h"
38 #include "vedge.h"
39
40 #include "cdt-flipfix.h"
41
42
43 static P2trEdge* p2tr_cdt_try_flip (P2trCDT *self,
44 P2trEdge *to_flip);
45
46 /* This function implements "Lawson's algorithm", also known as "The
47 * diagonal swapping algorithm". This algorithm takes a CDT, and a list
48 * of triangles that were formed by the insertion of a new point into
49 * the triangular mesh, and makes the triangulation a CDT once more. Its
50 * logic is explained below:
51 *
52 * If a point is added to an existing triangular mesh then
53 * circumcircles are formed for all new triangles formed. If any of
54 * the neighbours lie inside the circumcircle of any triangle, then a
55 * quadrilateral is formed using the triangle and its neighbour. The
56 * diagonals of this quadrilateral are swapped to give a new
57 * triangulation. This process is continued till there are no more
58 * faulty triangles and no more swaps are required.
59 *
60 * The description above may seem slightly inaccurate, as it does not
61 * consider the case were the diagonals can not be swapped since the
62 * quadrilateral is concave (then swapping the diagonals would result
63 * in a diagonal outside the quad, which is undesired).
64 *
65 * However, the description above is accurate. If the opposite point
66 * is inside the circular cut created by the edge, then since the
67 * circular cut is inside the infinite area created by extending the
68 * two other edges of the triangle, therefor the point is also inside
69 * that area - meaning that the quadrilateral is not concave!
70 */
71
72 void
73 p2tr_cdt_flip_fix (P2trCDT *self,
74 P2trVEdgeSet *candidates)
75 {
76 P2trEdge *edge;
77 P2trVEdge *vedge;
78
79 while (p2tr_vedge_set_pop (candidates, &vedge))
80 {
81 if (! p2tr_vedge_try_get_and_unref (vedge, &edge))
82 continue;
83
84 if (! edge->constrained
85 /* TODO: we probably don't need this check... */
86 && ! p2tr_edge_is_removed (edge))
87 {
88 /* If the edge is not constrained, then it should be
89 * a part of two triangles */
90 P2trPoint *A = P2TR_EDGE_START(edge), *B = edge->end;
91 P2trPoint *C1 = p2tr_triangle_get_opposite_point (edge->tri, edge, FALSE);
92 P2trPoint *C2 = p2tr_triangle_get_opposite_point (edge->mirror->tri, edge->mirror, FALSE);
93
94 P2trEdge *flipped = p2tr_cdt_try_flip (self, edge);
95 if (flipped != NULL)
96 {
97 p2tr_vedge_set_add (candidates, p2tr_point_get_edge_to (A, C1, TRUE));
98 p2tr_vedge_set_add (candidates, p2tr_point_get_edge_to (A, C2, TRUE));
99 p2tr_vedge_set_add (candidates, p2tr_point_get_edge_to (B, C1, TRUE));
100 p2tr_vedge_set_add (candidates, p2tr_point_get_edge_to (B, C2, TRUE));
101 p2tr_edge_unref (flipped);
102 }
103 }
104
105 p2tr_edge_unref (edge);
106 }
107 }
108
109 /**
110 * Try to flip a given edge, If successfull, return the new edge (reffed!),
111 * otherwise return NULL
112 */
113 P2trEdge*
114 p2tr_cdt_try_flip (P2trCDT *self,
115 P2trEdge *to_flip)
116 {
117 /* C
118 * / | \
119 * B-----A to_flip: A->B
120 * \ | / to_flip.Tri: ABC
121 * D
122 */
123 P2trPoint *A, *B, *C, *D;
124 P2trEdge *AB, *CA, *AD, *DB, *BC, *DC;
125
126 g_assert (! to_flip->constrained && ! to_flip->delaunay);
127
128 A = P2TR_EDGE_START (to_flip);
129 B = to_flip->end;
130 C = p2tr_triangle_get_opposite_point (to_flip->tri, to_flip, FALSE);
131 D = p2tr_triangle_get_opposite_point (to_flip->mirror->tri, to_flip->mirror, FALSE);
132
133 AB = to_flip;
134
135 /* Check if the quadriliteral ADBC is concave (because if it is, we
136 * can't flip the edge) */
137 if (p2tr_triangle_circumcircle_contains_point (AB->tri, &D->c) != P2TR_INCIRCLE_IN)
138 return NULL;
139
140 CA = p2tr_point_get_edge_to (C, A, FALSE);
141 AD = p2tr_point_get_edge_to (A, D, FALSE);
142 DB = p2tr_point_get_edge_to (D, B, FALSE);
143 BC = p2tr_point_get_edge_to (B, C, FALSE);
144
145 p2tr_edge_remove (AB);
146
147 DC = p2tr_mesh_new_edge (self->mesh, D, C, FALSE);
148
149 p2tr_triangle_unref (p2tr_mesh_new_triangle (self->mesh,
150 CA, AD, DC));
151
152 p2tr_triangle_unref (p2tr_mesh_new_triangle (self->mesh,
153 DB, BC, DC->mirror));
154
155 return DC;
156 }
157
158
159

   
Visit the ZANavi Wiki