Branch data Line data Source code
1 : : /*
2 : : * Poly2Tri Copyright (c) 2009-2018, Poly2Tri Contributors
3 : : * https://github.com/jhasse/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 : :
33 : : #include <cassert>
34 : : #include <iostream>
35 : :
36 : : namespace p2t {
37 : :
38 : 0 : std::ostream& operator<<(std::ostream& out, const Point& point) {
39 : 0 : return out << point.x << "," << point.y;
40 : : }
41 : :
42 : 156 : Triangle::Triangle(Point& a, Point& b, Point& c)
43 : : {
44 : 156 : points_[0] = &a; points_[1] = &b; points_[2] = &c;
45 : 156 : neighbors_[0] = NULL; neighbors_[1] = NULL; neighbors_[2] = NULL;
46 : 156 : constrained_edge[0] = constrained_edge[1] = constrained_edge[2] = false;
47 : 156 : delaunay_edge[0] = delaunay_edge[1] = delaunay_edge[2] = false;
48 : 156 : interior_ = false;
49 : 156 : }
50 : :
51 : : // Update neighbor pointers
52 : 234 : void Triangle::MarkNeighbor(Point* p1, Point* p2, Triangle* t)
53 : : {
54 : 234 : if ((p1 == points_[2] && p2 == points_[1]) || (p1 == points_[1] && p2 == points_[2]))
55 : 13 : neighbors_[0] = t;
56 : 221 : else if ((p1 == points_[0] && p2 == points_[2]) || (p1 == points_[2] && p2 == points_[0]))
57 : 117 : neighbors_[1] = t;
58 : 104 : else if ((p1 == points_[0] && p2 == points_[1]) || (p1 == points_[1] && p2 == points_[0]))
59 : 104 : neighbors_[2] = t;
60 : : else
61 : 0 : assert(0);
62 : 234 : }
63 : :
64 : : // Exhaustive search to update neighbor pointers
65 : 234 : void Triangle::MarkNeighbor(Triangle& t)
66 : : {
67 : 234 : if (t.Contains(points_[1], points_[2])) {
68 : 156 : neighbors_[0] = &t;
69 : 156 : t.MarkNeighbor(points_[1], points_[2], this);
70 : 234 : } else if (t.Contains(points_[0], points_[2])) {
71 : 13 : neighbors_[1] = &t;
72 : 13 : t.MarkNeighbor(points_[0], points_[2], this);
73 : 78 : } else if (t.Contains(points_[0], points_[1])) {
74 : 65 : neighbors_[2] = &t;
75 : 65 : t.MarkNeighbor(points_[0], points_[1], this);
76 : 65 : }
77 : 234 : }
78 : :
79 : : /**
80 : : * Clears all references to all other triangles and points
81 : : */
82 : 0 : void Triangle::Clear()
83 : : {
84 : : Triangle *t;
85 : 0 : for( int i=0; i<3; i++ )
86 : : {
87 : 0 : t = neighbors_[i];
88 : 0 : if( t != NULL )
89 : : {
90 : 0 : t->ClearNeighbor( this );
91 : 0 : }
92 : 0 : }
93 : 0 : ClearNeighbors();
94 : 0 : points_[0]=points_[1]=points_[2] = NULL;
95 : 0 : }
96 : :
97 : 0 : void Triangle::ClearNeighbor(const Triangle *triangle )
98 : : {
99 : 0 : if( neighbors_[0] == triangle )
100 : : {
101 : 0 : neighbors_[0] = NULL;
102 : 0 : }
103 : 0 : else if( neighbors_[1] == triangle )
104 : : {
105 : 0 : neighbors_[1] = NULL;
106 : 0 : }
107 : : else
108 : : {
109 : 0 : neighbors_[2] = NULL;
110 : : }
111 : 0 : }
112 : :
113 : 26 : void Triangle::ClearNeighbors()
114 : : {
115 : 26 : neighbors_[0] = NULL;
116 : 26 : neighbors_[1] = NULL;
117 : 26 : neighbors_[2] = NULL;
118 : 26 : }
119 : :
120 : 0 : void Triangle::ClearDelunayEdges()
121 : : {
122 : 0 : delaunay_edge[0] = delaunay_edge[1] = delaunay_edge[2] = false;
123 : 0 : }
124 : :
125 : 221 : Point* Triangle::OppositePoint(Triangle& t, const Point& p)
126 : : {
127 : 221 : Point *cw = t.PointCW(p);
128 : 221 : return PointCW(*cw);
129 : : }
130 : :
131 : : // Legalized triangle by rotating clockwise around point(0)
132 : 0 : void Triangle::Legalize(Point& point)
133 : : {
134 : 0 : points_[1] = points_[0];
135 : 0 : points_[0] = points_[2];
136 : 0 : points_[2] = &point;
137 : 0 : }
138 : :
139 : : // Legalize triagnle by rotating clockwise around oPoint
140 : 26 : void Triangle::Legalize(Point& opoint, Point& npoint)
141 : : {
142 : 26 : if (&opoint == points_[0]) {
143 : 13 : points_[1] = points_[0];
144 : 13 : points_[0] = points_[2];
145 : 13 : points_[2] = &npoint;
146 : 26 : } else if (&opoint == points_[1]) {
147 : 13 : points_[2] = points_[1];
148 : 13 : points_[1] = points_[0];
149 : 13 : points_[0] = &npoint;
150 : 13 : } else if (&opoint == points_[2]) {
151 : 0 : points_[0] = points_[2];
152 : 0 : points_[2] = points_[1];
153 : 0 : points_[1] = &npoint;
154 : 0 : } else {
155 : 0 : assert(0);
156 : : }
157 : 26 : }
158 : :
159 : 221 : int Triangle::Index(const Point* p)
160 : : {
161 : 221 : if (p == points_[0]) {
162 : 13 : return 0;
163 : 208 : } else if (p == points_[1]) {
164 : 104 : return 1;
165 : 104 : } else if (p == points_[2]) {
166 : 104 : return 2;
167 : : }
168 : 0 : assert(0);
169 : : return -1;
170 : 221 : }
171 : :
172 : 208 : int Triangle::EdgeIndex(const Point* p1, const Point* p2)
173 : : {
174 : 208 : if (points_[0] == p1) {
175 : 26 : if (points_[1] == p2) {
176 : 0 : return 2;
177 : 26 : } else if (points_[2] == p2) {
178 : 26 : return 1;
179 : : }
180 : 182 : } else if (points_[1] == p1) {
181 : 65 : if (points_[2] == p2) {
182 : 0 : return 0;
183 : 65 : } else if (points_[0] == p2) {
184 : 65 : return 2;
185 : : }
186 : 117 : } else if (points_[2] == p1) {
187 : 0 : if (points_[0] == p2) {
188 : 0 : return 1;
189 : 0 : } else if (points_[1] == p2) {
190 : 0 : return 0;
191 : : }
192 : 0 : }
193 : 117 : return -1;
194 : 208 : }
195 : :
196 : 91 : void Triangle::MarkConstrainedEdge(int index)
197 : : {
198 : 91 : constrained_edge[index] = true;
199 : 91 : }
200 : :
201 : 0 : void Triangle::MarkConstrainedEdge(Edge& edge)
202 : : {
203 : 0 : MarkConstrainedEdge(edge.p, edge.q);
204 : 0 : }
205 : :
206 : : // Mark edge as constrained
207 : 39 : void Triangle::MarkConstrainedEdge(Point* p, Point* q)
208 : : {
209 : 39 : if ((q == points_[0] && p == points_[1]) || (q == points_[1] && p == points_[0])) {
210 : 0 : constrained_edge[2] = true;
211 : 39 : } else if ((q == points_[0] && p == points_[2]) || (q == points_[2] && p == points_[0])) {
212 : 0 : constrained_edge[1] = true;
213 : 39 : } else if ((q == points_[1] && p == points_[2]) || (q == points_[2] && p == points_[1])) {
214 : 39 : constrained_edge[0] = true;
215 : 39 : }
216 : 39 : }
217 : :
218 : : // The point counter-clockwise to given point
219 : 910 : Point* Triangle::PointCW(const Point& point)
220 : : {
221 : 910 : if (&point == points_[0]) {
222 : 416 : return points_[2];
223 : 494 : } else if (&point == points_[1]) {
224 : 169 : return points_[0];
225 : 325 : } else if (&point == points_[2]) {
226 : 325 : return points_[1];
227 : : }
228 : 0 : assert(0);
229 : : return NULL;
230 : 910 : }
231 : :
232 : : // The point counter-clockwise to given point
233 : 234 : Point* Triangle::PointCCW(const Point& point)
234 : : {
235 : 234 : if (&point == points_[0]) {
236 : 156 : return points_[1];
237 : 78 : } else if (&point == points_[1]) {
238 : 13 : return points_[2];
239 : 65 : } else if (&point == points_[2]) {
240 : 65 : return points_[0];
241 : : }
242 : 0 : assert(0);
243 : : return NULL;
244 : 234 : }
245 : :
246 : : // The neighbor clockwise to given point
247 : 26 : Triangle* Triangle::NeighborCW(const Point& point)
248 : : {
249 : 26 : if (&point == points_[0]) {
250 : 13 : return neighbors_[1];
251 : 13 : } else if (&point == points_[1]) {
252 : 13 : return neighbors_[2];
253 : : }
254 : 0 : return neighbors_[0];
255 : 26 : }
256 : :
257 : : // The neighbor counter-clockwise to given point
258 : 91 : Triangle* Triangle::NeighborCCW(const Point& point)
259 : : {
260 : 91 : if (&point == points_[0]) {
261 : 52 : return neighbors_[2];
262 : 39 : } else if (&point == points_[1]) {
263 : 26 : return neighbors_[0];
264 : : }
265 : 13 : return neighbors_[1];
266 : 91 : }
267 : :
268 : 26 : bool Triangle::GetConstrainedEdgeCCW(const Point& p)
269 : : {
270 : 26 : if (&p == points_[0]) {
271 : 13 : return constrained_edge[2];
272 : 13 : } else if (&p == points_[1]) {
273 : 13 : return constrained_edge[0];
274 : : }
275 : 0 : return constrained_edge[1];
276 : 26 : }
277 : :
278 : 39 : bool Triangle::GetConstrainedEdgeCW(const Point& p)
279 : : {
280 : 39 : if (&p == points_[0]) {
281 : 26 : return constrained_edge[1];
282 : 13 : } else if (&p == points_[1]) {
283 : 13 : return constrained_edge[2];
284 : : }
285 : 0 : return constrained_edge[0];
286 : 39 : }
287 : :
288 : 26 : void Triangle::SetConstrainedEdgeCCW(const Point& p, bool ce)
289 : : {
290 : 26 : if (&p == points_[0]) {
291 : 13 : constrained_edge[2] = ce;
292 : 26 : } else if (&p == points_[1]) {
293 : 0 : constrained_edge[0] = ce;
294 : 0 : } else {
295 : 13 : constrained_edge[1] = ce;
296 : : }
297 : 26 : }
298 : :
299 : 26 : void Triangle::SetConstrainedEdgeCW(const Point& p, bool ce)
300 : : {
301 : 26 : if (&p == points_[0]) {
302 : 0 : constrained_edge[1] = ce;
303 : 26 : } else if (&p == points_[1]) {
304 : 13 : constrained_edge[2] = ce;
305 : 13 : } else {
306 : 13 : constrained_edge[0] = ce;
307 : : }
308 : 26 : }
309 : :
310 : 26 : bool Triangle::GetDelunayEdgeCCW(const Point& p)
311 : : {
312 : 26 : if (&p == points_[0]) {
313 : 13 : return delaunay_edge[2];
314 : 13 : } else if (&p == points_[1]) {
315 : 13 : return delaunay_edge[0];
316 : : }
317 : 0 : return delaunay_edge[1];
318 : 26 : }
319 : :
320 : 26 : bool Triangle::GetDelunayEdgeCW(const Point& p)
321 : : {
322 : 26 : if (&p == points_[0]) {
323 : 13 : return delaunay_edge[1];
324 : 13 : } else if (&p == points_[1]) {
325 : 13 : return delaunay_edge[2];
326 : : }
327 : 0 : return delaunay_edge[0];
328 : 26 : }
329 : :
330 : 26 : void Triangle::SetDelunayEdgeCCW(const Point& p, bool e)
331 : : {
332 : 26 : if (&p == points_[0]) {
333 : 13 : delaunay_edge[2] = e;
334 : 26 : } else if (&p == points_[1]) {
335 : 0 : delaunay_edge[0] = e;
336 : 0 : } else {
337 : 13 : delaunay_edge[1] = e;
338 : : }
339 : 26 : }
340 : :
341 : 26 : void Triangle::SetDelunayEdgeCW(const Point& p, bool e)
342 : : {
343 : 26 : if (&p == points_[0]) {
344 : 0 : delaunay_edge[1] = e;
345 : 26 : } else if (&p == points_[1]) {
346 : 13 : delaunay_edge[2] = e;
347 : 13 : } else {
348 : 13 : delaunay_edge[0] = e;
349 : : }
350 : 26 : }
351 : :
352 : : // The neighbor across to given point
353 : 0 : Triangle& Triangle::NeighborAcross(const Point& opoint)
354 : : {
355 : 0 : if (&opoint == points_[0]) {
356 : 0 : return *neighbors_[0];
357 : 0 : } else if (&opoint == points_[1]) {
358 : 0 : return *neighbors_[1];
359 : : }
360 : 0 : return *neighbors_[2];
361 : 0 : }
362 : :
363 : 0 : void Triangle::DebugPrint()
364 : : {
365 : 0 : std::cout << *points_[0] << " " << *points_[1] << " " << *points_[2] << std::endl;
366 : 0 : }
367 : :
368 : 0 : bool Triangle::CircumcicleContains(const Point& point) const
369 : : {
370 : 0 : assert(IsCounterClockwise());
371 : 0 : const double dx = points_[0]->x - point.x;
372 : 0 : const double dy = points_[0]->y - point.y;
373 : 0 : const double ex = points_[1]->x - point.x;
374 : 0 : const double ey = points_[1]->y - point.y;
375 : 0 : const double fx = points_[2]->x - point.x;
376 : 0 : const double fy = points_[2]->y - point.y;
377 : :
378 : 0 : const double ap = dx * dx + dy * dy;
379 : 0 : const double bp = ex * ex + ey * ey;
380 : 0 : const double cp = fx * fx + fy * fy;
381 : :
382 : 0 : return (dx * (fy * bp - cp * ey) - dy * (fx * bp - cp * ex) + ap * (fx * ey - fy * ex)) < 0;
383 : : }
384 : :
385 : 0 : bool Triangle::IsCounterClockwise() const
386 : : {
387 : 0 : return (points_[1]->x - points_[0]->x) * (points_[2]->y - points_[0]->y) -
388 : 0 : (points_[2]->x - points_[0]->x) * (points_[1]->y - points_[0]->y) >
389 : : 0;
390 : : }
391 : :
392 : 0 : bool IsDelaunay(const std::vector<p2t::Triangle*>& triangles)
393 : : {
394 : 0 : for (const auto triangle : triangles) {
395 : 0 : for (const auto other : triangles) {
396 : 0 : if (triangle == other) {
397 : 0 : continue;
398 : : }
399 : 0 : for (int i = 0; i < 3; ++i) {
400 : 0 : if (triangle->CircumcicleContains(*other->GetPoint(i))) {
401 : 0 : return false;
402 : : }
403 : 0 : }
404 : : }
405 : : }
406 : 0 : return true;
407 : 0 : }
408 : :
409 : : }
|
