1/*
2 * Poly2Tri Copyright (c) 2009-2010, Poly2Tri Contributors
3 * http://code.google.com/p/poly2tri/
4 *
5 * All rights reserved.
6 *
7 * Redistribution and use in source and binary forms, with or without modification,
8 * are permitted provided that the following conditions are met:
9 *
10 * * Redistributions of source code must retain the above copyright notice,
11 * this list of conditions and the following disclaimer.
12 * * Redistributions in binary form must reproduce the above copyright notice,
13 * this list of conditions and the following disclaimer in the documentation
14 * and/or other materials provided with the distribution.
15 * * Neither the name of Poly2Tri nor the names of its contributors may be
16 * used to endorse or promote products derived from this software without specific
17 * prior written permission.
18 *
19 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
20 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
21 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
22 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR
23 * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
24 * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
25 * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
26 * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
27 * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
28 * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
29 * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
30 */
31#include "shapes.h"
32#include <iostream>
33
34namespace p2t {
35
36Triangle::Triangle(Point& a, Point& b, Point& c)
37{
38 points_[0] = &a; points_[1] = &b; points_[2] = &c;
39 neighbors_[0] = NULL; neighbors_[1] = NULL; neighbors_[2] = NULL;
40 constrained_edge[0] = constrained_edge[1] = constrained_edge[2] = false;
41 delaunay_edge[0] = delaunay_edge[1] = delaunay_edge[2] = false;
42 interior_ = false;
43}
44
45// Update neighbor pointers
46void Triangle::MarkNeighbor(Point* p1, Point* p2, Triangle* t)
47{
48 if ((p1 == points_[2] && p2 == points_[1]) || (p1 == points_[1] && p2 == points_[2]))
49 neighbors_[0] = t;
50 else if ((p1 == points_[0] && p2 == points_[2]) || (p1 == points_[2] && p2 == points_[0]))
51 neighbors_[1] = t;
52 else if ((p1 == points_[0] && p2 == points_[1]) || (p1 == points_[1] && p2 == points_[0]))
53 neighbors_[2] = t;
54 else
55 assert(0);
56}
57
58// Exhaustive search to update neighbor pointers
59void Triangle::MarkNeighbor(Triangle& t)
60{
61 if (t.Contains(p: points_[1], q: points_[2])) {
62 neighbors_[0] = &t;
63 t.MarkNeighbor(p1: points_[1], p2: points_[2], t: this);
64 } else if (t.Contains(p: points_[0], q: points_[2])) {
65 neighbors_[1] = &t;
66 t.MarkNeighbor(p1: points_[0], p2: points_[2], t: this);
67 } else if (t.Contains(p: points_[0], q: points_[1])) {
68 neighbors_[2] = &t;
69 t.MarkNeighbor(p1: points_[0], p2: points_[1], t: this);
70 }
71}
72
73/**
74 * Clears all references to all other triangles and points
75 */
76void Triangle::Clear()
77{
78 Triangle *t;
79 for (int i=0; i<3; i++)
80 {
81 t = neighbors_[i];
82 if (t != NULL)
83 {
84 t->ClearNeighbor( triangle: this );
85 }
86 }
87 ClearNeighbors();
88 points_[0]=points_[1]=points_[2] = NULL;
89}
90
91void Triangle::ClearNeighbor(Triangle *triangle )
92{
93 if (neighbors_[0] == triangle)
94 {
95 neighbors_[0] = NULL;
96 }
97 else if (neighbors_[1] == triangle)
98 {
99 neighbors_[1] = NULL;
100 }
101 else
102 {
103 neighbors_[2] = NULL;
104 }
105}
106
107void Triangle::ClearNeighbors()
108{
109 neighbors_[0] = NULL;
110 neighbors_[1] = NULL;
111 neighbors_[2] = NULL;
112}
113
114void Triangle::ClearDelunayEdges()
115{
116 delaunay_edge[0] = delaunay_edge[1] = delaunay_edge[2] = false;
117}
118
119Point* Triangle::OppositePoint(Triangle& t, Point& p)
120{
121 Point *cw = t.PointCW(point&: p);
122 return PointCW(point&: *cw);
123}
124
125// Legalized triangle by rotating clockwise around point(0)
126void Triangle::Legalize(Point& point)
127{
128 points_[1] = points_[0];
129 points_[0] = points_[2];
130 points_[2] = &point;
131}
132
133// Legalize triagnle by rotating clockwise around oPoint
134void Triangle::Legalize(Point& opoint, Point& npoint)
135{
136 if (&opoint == points_[0]) {
137 points_[1] = points_[0];
138 points_[0] = points_[2];
139 points_[2] = &npoint;
140 } else if (&opoint == points_[1]) {
141 points_[2] = points_[1];
142 points_[1] = points_[0];
143 points_[0] = &npoint;
144 } else if (&opoint == points_[2]) {
145 points_[0] = points_[2];
146 points_[2] = points_[1];
147 points_[1] = &npoint;
148 } else {
149 assert(0);
150 }
151}
152
153int Triangle::Index(const Point* p)
154{
155 if (p == points_[0]) {
156 return 0;
157 } else if (p == points_[1]) {
158 return 1;
159 } else if (p == points_[2]) {
160 return 2;
161 }
162 assert(0);
163}
164
165int Triangle::EdgeIndex(const Point* p1, const Point* p2)
166{
167 if (points_[0] == p1) {
168 if (points_[1] == p2) {
169 return 2;
170 } else if (points_[2] == p2) {
171 return 1;
172 }
173 } else if (points_[1] == p1) {
174 if (points_[2] == p2) {
175 return 0;
176 } else if (points_[0] == p2) {
177 return 2;
178 }
179 } else if (points_[2] == p1) {
180 if (points_[0] == p2) {
181 return 1;
182 } else if (points_[1] == p2) {
183 return 0;
184 }
185 }
186 return -1;
187}
188
189void Triangle::MarkConstrainedEdge(const int index)
190{
191 constrained_edge[index] = true;
192}
193
194void Triangle::MarkConstrainedEdge(Edge& edge)
195{
196 MarkConstrainedEdge(p: edge.p, q: edge.q);
197}
198
199// Mark edge as constrained
200void Triangle::MarkConstrainedEdge(Point* p, Point* q)
201{
202 if ((q == points_[0] && p == points_[1]) || (q == points_[1] && p == points_[0])) {
203 constrained_edge[2] = true;
204 } else if ((q == points_[0] && p == points_[2]) || (q == points_[2] && p == points_[0])) {
205 constrained_edge[1] = true;
206 } else if ((q == points_[1] && p == points_[2]) || (q == points_[2] && p == points_[1])) {
207 constrained_edge[0] = true;
208 }
209}
210
211// The point counter-clockwise to given point
212Point* Triangle::PointCW(Point& point)
213{
214 if (&point == points_[0]) {
215 return points_[2];
216 } else if (&point == points_[1]) {
217 return points_[0];
218 } else if (&point == points_[2]) {
219 return points_[1];
220 }
221 assert(0);
222}
223
224// The point counter-clockwise to given point
225Point* Triangle::PointCCW(Point& point)
226{
227 if (&point == points_[0]) {
228 return points_[1];
229 } else if (&point == points_[1]) {
230 return points_[2];
231 } else if (&point == points_[2]) {
232 return points_[0];
233 }
234 assert(0);
235}
236
237// The neighbor clockwise to given point
238Triangle* Triangle::NeighborCW(Point& point)
239{
240 if (&point == points_[0]) {
241 return neighbors_[1];
242 } else if (&point == points_[1]) {
243 return neighbors_[2];
244 }
245 return neighbors_[0];
246}
247
248// The neighbor counter-clockwise to given point
249Triangle* Triangle::NeighborCCW(Point& point)
250{
251 if (&point == points_[0]) {
252 return neighbors_[2];
253 } else if (&point == points_[1]) {
254 return neighbors_[0];
255 }
256 return neighbors_[1];
257}
258
259bool Triangle::GetConstrainedEdgeCCW(Point& p)
260{
261 if (&p == points_[0]) {
262 return constrained_edge[2];
263 } else if (&p == points_[1]) {
264 return constrained_edge[0];
265 }
266 return constrained_edge[1];
267}
268
269bool Triangle::GetConstrainedEdgeCW(Point& p)
270{
271 if (&p == points_[0]) {
272 return constrained_edge[1];
273 } else if (&p == points_[1]) {
274 return constrained_edge[2];
275 }
276 return constrained_edge[0];
277}
278
279void Triangle::SetConstrainedEdgeCCW(Point& p, bool ce)
280{
281 if (&p == points_[0]) {
282 constrained_edge[2] = ce;
283 } else if (&p == points_[1]) {
284 constrained_edge[0] = ce;
285 } else {
286 constrained_edge[1] = ce;
287 }
288}
289
290void Triangle::SetConstrainedEdgeCW(Point& p, bool ce)
291{
292 if (&p == points_[0]) {
293 constrained_edge[1] = ce;
294 } else if (&p == points_[1]) {
295 constrained_edge[2] = ce;
296 } else {
297 constrained_edge[0] = ce;
298 }
299}
300
301bool Triangle::GetDelunayEdgeCCW(Point& p)
302{
303 if (&p == points_[0]) {
304 return delaunay_edge[2];
305 } else if (&p == points_[1]) {
306 return delaunay_edge[0];
307 }
308 return delaunay_edge[1];
309}
310
311bool Triangle::GetDelunayEdgeCW(Point& p)
312{
313 if (&p == points_[0]) {
314 return delaunay_edge[1];
315 } else if (&p == points_[1]) {
316 return delaunay_edge[2];
317 }
318 return delaunay_edge[0];
319}
320
321void Triangle::SetDelunayEdgeCCW(Point& p, bool e)
322{
323 if (&p == points_[0]) {
324 delaunay_edge[2] = e;
325 } else if (&p == points_[1]) {
326 delaunay_edge[0] = e;
327 } else {
328 delaunay_edge[1] = e;
329 }
330}
331
332void Triangle::SetDelunayEdgeCW(Point& p, bool e)
333{
334 if (&p == points_[0]) {
335 delaunay_edge[1] = e;
336 } else if (&p == points_[1]) {
337 delaunay_edge[2] = e;
338 } else {
339 delaunay_edge[0] = e;
340 }
341}
342
343// The neighbor across to given point
344Triangle& Triangle::NeighborAcross(Point& opoint)
345{
346 if (&opoint == points_[0]) {
347 return *neighbors_[0];
348 } else if (&opoint == points_[1]) {
349 return *neighbors_[1];
350 }
351 return *neighbors_[2];
352}
353
354void Triangle::DebugPrint()
355{
356 using namespace std;
357 cout << points_[0]->x << "," << points_[0]->y << " ";
358 cout << points_[1]->x << "," << points_[1]->y << " ";
359 cout << points_[2]->x << "," << points_[2]->y << endl;
360}
361
362}
363
364

source code of qtlocation/src/3rdparty/poly2tri/common/shapes.cpp