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 | |
34 | namespace p2t { |
35 | |
36 | Triangle::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 |
46 | void 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 |
59 | void 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 | */ |
76 | void 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 | |
91 | void 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 | |
107 | void Triangle::ClearNeighbors() |
108 | { |
109 | neighbors_[0] = NULL; |
110 | neighbors_[1] = NULL; |
111 | neighbors_[2] = NULL; |
112 | } |
113 | |
114 | void Triangle::ClearDelunayEdges() |
115 | { |
116 | delaunay_edge[0] = delaunay_edge[1] = delaunay_edge[2] = false; |
117 | } |
118 | |
119 | Point* 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) |
126 | void 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 |
134 | void 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 | |
153 | int 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 | |
165 | int 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 | |
189 | void Triangle::MarkConstrainedEdge(const int index) |
190 | { |
191 | constrained_edge[index] = true; |
192 | } |
193 | |
194 | void Triangle::MarkConstrainedEdge(Edge& edge) |
195 | { |
196 | MarkConstrainedEdge(p: edge.p, q: edge.q); |
197 | } |
198 | |
199 | // Mark edge as constrained |
200 | void 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 |
212 | Point* 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 |
225 | Point* 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 |
238 | Triangle* 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 |
249 | Triangle* 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 | |
259 | bool 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 | |
269 | bool 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 | |
279 | void 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 | |
290 | void 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 | |
301 | bool 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 | |
311 | bool 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 | |
321 | void 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 | |
332 | void 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 |
344 | Triangle& 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 | |
354 | void 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 | |