GCC Code Coverage Report


Directory: ./
Coverage: low: ≥ 0% medium: ≥ 75.0% high: ≥ 90.0%
Coverage Exec / Excl / Total
Lines: 33.0% 384 / 0 / 1163
Functions: 57.5% 23 / 0 / 40
Branches: 30.1% 270 / 0 / 898

src/polypartition/polypartition.cpp
Line Branch Exec Source
1 //Copyright (C) 2011 by Ivan Fratric
2 //
3 //Permission is hereby granted, free of charge, to any person obtaining a copy
4 //of this software and associated documentation files (the "Software"), to deal
5 //in the Software without restriction, including without limitation the rights
6 //to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
7 //copies of the Software, and to permit persons to whom the Software is
8 //furnished to do so, subject to the following conditions:
9 //
10 //The above copyright notice and this permission notice shall be included in
11 //all copies or substantial portions of the Software.
12 //
13 //THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
14 //IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
15 //FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
16 //AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
17 //LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
18 //OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
19 //THE SOFTWARE.
20
21 #include <cstdio>
22 #include <cstring>
23 #include <cmath>
24 #include <list>
25 #include <algorithm>
26 #include <set>
27 #include <vector>
28 #include <stdexcept>
29
30 using namespace std;
31
32 #include "polypartition.h"
33
34 #define TPPL_VERTEXTYPE_REGULAR 0
35 #define TPPL_VERTEXTYPE_START 1
36 #define TPPL_VERTEXTYPE_END 2
37 #define TPPL_VERTEXTYPE_SPLIT 3
38 #define TPPL_VERTEXTYPE_MERGE 4
39
40 225994 TPPLPoly::TPPLPoly() {
41 225994 hole = false;
42 225994 numpoints = 0;
43 225994 points = NULL;
44 225994 }
45
46 225994 TPPLPoly::~TPPLPoly() {
47
2/2
✓ Branch 0 taken 200041 times.
✓ Branch 1 taken 25953 times.
225994 if (points) {
48
1/2
✓ Branch 0 taken 200041 times.
✗ Branch 1 not taken.
200041 delete[] points;
49 }
50 225994 }
51
52 112591 void TPPLPoly::Clear() {
53
2/2
✓ Branch 0 taken 55190 times.
✓ Branch 1 taken 57401 times.
112591 if (points) {
54
1/2
✓ Branch 0 taken 55190 times.
✗ Branch 1 not taken.
55190 delete[] points;
55 }
56 112591 hole = false;
57 112591 numpoints = 0;
58 112591 points = NULL;
59 112591 }
60
61 109679 void TPPLPoly::Init(long numpoints) {
62 109679 Clear();
63 109679 this->numpoints = numpoints;
64
1/2
✓ Branch 0 taken 109679 times.
✗ Branch 1 not taken.
109679 points = new TPPLPoint[numpoints];
65 109679 }
66
67 74281 void TPPLPoly::Triangle(TPPLPoint& p1, TPPLPoint& p2, TPPLPoint& p3) {
68 74281 Init(3);
69 74281 points[0] = p1;
70 74281 points[1] = p2;
71 74281 points[2] = p3;
72 74281 }
73
74 142640 TPPLPoly::TPPLPoly(const TPPLPoly& src) : TPPLPoly() {
75 142640 hole = src.hole;
76 142640 numpoints = src.numpoints;
77
78
1/2
✓ Branch 0 taken 142640 times.
✗ Branch 1 not taken.
142640 if (numpoints > 0) {
79
2/3
✓ Branch 0 taken 142640 times.
✗ Branch 1 not taken.
✓ Branch 4 taken 142640 times.
142640 points = new TPPLPoint[numpoints];
80 142640 memcpy(points, src.points, numpoints * sizeof(TPPLPoint));
81 }
82 142640 }
83
84 2912 TPPLPoly& TPPLPoly::operator=(const TPPLPoly& src) {
85 2912 Clear();
86 2912 hole = src.hole;
87 2912 numpoints = src.numpoints;
88
89
1/2
✓ Branch 0 taken 2912 times.
✗ Branch 1 not taken.
2912 if (numpoints > 0) {
90
1/2
✓ Branch 0 taken 2912 times.
✗ Branch 1 not taken.
2912 points = new TPPLPoint[numpoints];
91 2912 memcpy(points, src.points, numpoints * sizeof(TPPLPoint));
92 }
93
94 2912 return *this;
95 }
96
97 97770 int TPPLPoly::GetOrientation() const {
98 long i1;
99 long i2;
100 97770 tppl_float area = 0;
101
2/2
✓ Branch 0 taken 327221 times.
✓ Branch 1 taken 97770 times.
424991 for (i1 = 0; i1 < numpoints; i1++) {
102 327221 i2 = i1 + 1;
103
2/2
✓ Branch 0 taken 97770 times.
✓ Branch 1 taken 229451 times.
327221 if (i2 == numpoints) {
104 97770 i2 = 0;
105 }
106 327221 area += points[i1].x * points[i2].y - points[i1].y * points[i2].x;
107 }
108
2/2
✓ Branch 0 taken 94528 times.
✓ Branch 1 taken 3242 times.
97770 if (area > 0) {
109 94528 return TPPL_CCW;
110 }
111
1/2
✓ Branch 0 taken 3242 times.
✗ Branch 1 not taken.
3242 if (area < 0) {
112 3242 return TPPL_CW;
113 }
114 ✗ return 0;
115 }
116
117 97770 void TPPLPoly::SetOrientation(int orientation) {
118 97770 int polyorientation = GetOrientation();
119
3/4
✓ Branch 0 taken 97770 times.
✗ Branch 1 not taken.
✓ Branch 2 taken 69732 times.
✓ Branch 3 taken 28038 times.
97770 if ((polyorientation != 0) && (polyorientation != orientation)) {
120 69732 Invert();
121 }
122 97770 }
123
124 69732 void TPPLPoly::Invert() {
125 69732 std::reverse(points, points + numpoints);
126 69732 }
127
128 125513 TPPLPartition::PartitionVertex::PartitionVertex() : previous(NULL), next(NULL) {}
129
130 374740 TPPLPoint TPPLPartition::Normalize(const TPPLPoint& p) {
131 TPPLPoint r;
132 374740 tppl_float n = std::sqrt(p.x * p.x + p.y * p.y);
133
2/2
✓ Branch 0 taken 374641 times.
✓ Branch 1 taken 99 times.
374740 if (n != 0) {
134 374641 r = p / n;
135 } else {
136 99 r.x = 0;
137 99 r.y = 0;
138 }
139 374740 return r;
140 }
141
142 ✗ tppl_float TPPLPartition::Distance(const TPPLPoint& p1, const TPPLPoint& p2) {
143 tppl_float dx;
144 tppl_float dy;
145 ✗ dx = p2.x - p1.x;
146 ✗ dy = p2.y - p1.y;
147 ✗ return (std::sqrt(dx * dx + dy * dy));
148 }
149
150 //checks if two lines intersect
151 1028096 int TPPLPartition::Intersects(TPPLPoint& p11, TPPLPoint& p12, TPPLPoint& p21, TPPLPoint& p22) {
152
3/4
✓ Branch 0 taken 38268 times.
✓ Branch 1 taken 989828 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 38268 times.
1028096 if ((p11.x == p21.x) && (p11.y == p21.y)) {
153 ✗ return 0;
154 }
155
3/4
✓ Branch 0 taken 40623 times.
✓ Branch 1 taken 987473 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 40623 times.
1028096 if ((p11.x == p22.x) && (p11.y == p22.y)) {
156 ✗ return 0;
157 }
158
4/4
✓ Branch 0 taken 109459 times.
✓ Branch 1 taken 918637 times.
✓ Branch 2 taken 26684 times.
✓ Branch 3 taken 82775 times.
1028096 if ((p12.x == p21.x) && (p12.y == p21.y)) {
159 26684 return 0;
160 }
161
4/4
✓ Branch 0 taken 96894 times.
✓ Branch 1 taken 904518 times.
✓ Branch 2 taken 26648 times.
✓ Branch 3 taken 70246 times.
1001412 if ((p12.x == p22.x) && (p12.y == p22.y)) {
162 26648 return 0;
163 }
164
165 TPPLPoint v1ort;
166 TPPLPoint v2ort;
167 TPPLPoint v;
168 tppl_float dot11;
169 tppl_float dot12;
170 tppl_float dot21;
171 tppl_float dot22;
172
173 974764 v1ort.x = p12.y - p11.y;
174 974764 v1ort.y = p11.x - p12.x;
175
176 974764 v2ort.x = p22.y - p21.y;
177 974764 v2ort.y = p21.x - p22.x;
178
179 974764 v = p21 - p11;
180 974764 dot21 = v.x * v1ort.x + v.y * v1ort.y;
181 974764 v = p22 - p11;
182 974764 dot22 = v.x * v1ort.x + v.y * v1ort.y;
183
184 974764 v = p11 - p21;
185 974764 dot11 = v.x * v2ort.x + v.y * v2ort.y;
186 974764 v = p12 - p21;
187 974764 dot12 = v.x * v2ort.x + v.y * v2ort.y;
188
189
2/2
✓ Branch 0 taken 673846 times.
✓ Branch 1 taken 300918 times.
974764 if (dot11 * dot12 > 0) {
190 673846 return 0;
191 }
192
2/2
✓ Branch 0 taken 284717 times.
✓ Branch 1 taken 16201 times.
300918 if (dot21 * dot22 > 0) {
193 284717 return 0;
194 }
195
196 16201 return 1;
197 }
198
199 //removes holes from inpolys by merging them with non-holes
200 26540 int TPPLPartition::RemoveHoles(TPPLPolyList* inpolys, TPPLPolyList* outpolys) {
201 26540 TPPLPolyList polys;
202 26540 TPPLPolyList::iterator holeiter;
203 26540 TPPLPolyList::iterator polyiter;
204 26540 TPPLPolyList::iterator iter;
205 26540 TPPLPolyList::iterator iter2;
206 long i;
207 long i2;
208 long holepointindex;
209 long polypointindex;
210 TPPLPoint holepoint;
211 TPPLPoint polypoint;
212 TPPLPoint bestpolypoint;
213 TPPLPoint linep1;
214 TPPLPoint linep2;
215 TPPLPoint v1;
216 TPPLPoint v2;
217
1/1
✓ Branch 1 taken 26540 times.
26540 TPPLPoly newpoly;
218 bool hasholes;
219 bool pointvisible;
220 bool pointfound;
221
222 //check for trivial case (no holes)
223 26540 hasholes = false;
224
2/2
✓ Branch 4 taken 28051 times.
✓ Branch 5 taken 25029 times.
53080 for (iter = inpolys->begin(); iter != inpolys->end(); iter++) {
225
2/2
✓ Branch 2 taken 1511 times.
✓ Branch 3 taken 26540 times.
28051 if (iter->IsHole()) {
226 1511 hasholes = true;
227 1511 break;
228 }
229 }
230
2/2
✓ Branch 0 taken 25029 times.
✓ Branch 1 taken 1511 times.
26540 if (!hasholes) {
231
2/2
✓ Branch 4 taken 25029 times.
✓ Branch 5 taken 25029 times.
50058 for (iter = inpolys->begin(); iter != inpolys->end(); iter++) {
232
1/1
✓ Branch 2 taken 25029 times.
25029 outpolys->push_back(*iter);
233 }
234 25029 return 1;
235 }
236
237
1/1
✓ Branch 1 taken 1511 times.
1511 polys = *inpolys;
238
239 while (true) {
240 //find the hole point with the largest x
241 4484 hasholes = false;
242
2/2
✓ Branch 4 taken 19229 times.
✓ Branch 5 taken 4484 times.
23713 for (iter = polys.begin(); iter != polys.end(); iter++) {
243
2/2
✓ Branch 2 taken 4484 times.
✓ Branch 3 taken 14745 times.
19229 if (!iter->IsHole()) {
244 4484 continue;
245 }
246
247
2/2
✓ Branch 0 taken 2973 times.
✓ Branch 1 taken 11772 times.
14745 if (!hasholes) {
248 2973 hasholes = true;
249 2973 holeiter = iter;
250 2973 holepointindex = 0;
251 }
252
253
2/2
✓ Branch 2 taken 59024 times.
✓ Branch 3 taken 14745 times.
73769 for (i = 0; i < iter->GetNumPoints(); i++) {
254
2/2
✓ Branch 4 taken 3953 times.
✓ Branch 5 taken 55071 times.
59024 if (iter->GetPoint(i).x > holeiter->GetPoint(holepointindex).x) {
255 3953 holeiter = iter;
256 3953 holepointindex = i;
257 }
258 }
259 }
260
2/2
✓ Branch 0 taken 1511 times.
✓ Branch 1 taken 2973 times.
4484 if (!hasholes) {
261 1511 break;
262 }
263 2973 holepoint = holeiter->GetPoint(holepointindex);
264
265 2973 pointfound = false;
266
2/2
✓ Branch 4 taken 17718 times.
✓ Branch 5 taken 2973 times.
20691 for (iter = polys.begin(); iter != polys.end(); iter++) {
267
2/2
✓ Branch 2 taken 14745 times.
✓ Branch 3 taken 2973 times.
17718 if (iter->IsHole()) {
268 14745 continue;
269 }
270
2/2
✓ Branch 2 taken 83589 times.
✓ Branch 3 taken 2973 times.
86562 for (i = 0; i < iter->GetNumPoints(); i++) {
271
2/2
✓ Branch 2 taken 12216 times.
✓ Branch 3 taken 71373 times.
83589 if (iter->GetPoint(i).x <= holepoint.x) {
272 12216 continue;
273 }
274
3/3
✓ Branch 11 taken 71373 times.
✓ Branch 13 taken 39222 times.
✓ Branch 14 taken 32151 times.
142746 if (!InCone(iter->GetPoint((i + iter->GetNumPoints() - 1) % (iter->GetNumPoints())), iter->GetPoint(i),
275 71373 iter->GetPoint((i + 1) % (iter->GetNumPoints())), holepoint)) {
276 39222 continue;
277 }
278 32151 polypoint = iter->GetPoint(i);
279
2/2
✓ Branch 0 taken 15759 times.
✓ Branch 1 taken 16392 times.
32151 if (pointfound) {
280
1/1
✓ Branch 2 taken 15759 times.
15759 v1 = Normalize(polypoint - holepoint);
281
1/1
✓ Branch 2 taken 15759 times.
15759 v2 = Normalize(bestpolypoint - holepoint);
282
2/2
✓ Branch 0 taken 9676 times.
✓ Branch 1 taken 6083 times.
15759 if (v2.x > v1.x) {
283 9676 continue;
284 }
285 }
286 22475 pointvisible = true;
287
2/2
✓ Branch 4 taken 212357 times.
✓ Branch 5 taken 6274 times.
218631 for (iter2 = polys.begin(); iter2 != polys.end(); iter2++) {
288
2/2
✓ Branch 2 taken 189882 times.
✓ Branch 3 taken 22475 times.
212357 if (iter2->IsHole()) {
289 189882 continue;
290 }
291
2/2
✓ Branch 2 taken 1028096 times.
✓ Branch 3 taken 6274 times.
1034370 for (i2 = 0; i2 < iter2->GetNumPoints(); i2++) {
292 1028096 linep1 = iter2->GetPoint(i2);
293 1028096 linep2 = iter2->GetPoint((i2 + 1) % (iter2->GetNumPoints()));
294
3/3
✓ Branch 1 taken 1028096 times.
✓ Branch 3 taken 16201 times.
✓ Branch 4 taken 1011895 times.
1028096 if (Intersects(holepoint, polypoint, linep1, linep2) != 0) {
295 16201 pointvisible = false;
296 16201 break;
297 }
298 }
299
2/2
✓ Branch 0 taken 16201 times.
✓ Branch 1 taken 6274 times.
22475 if (!pointvisible) {
300 16201 break;
301 }
302 }
303
2/2
✓ Branch 0 taken 6274 times.
✓ Branch 1 taken 16201 times.
22475 if (pointvisible) {
304 6274 pointfound = true;
305 6274 bestpolypoint = polypoint;
306 6274 polyiter = iter;
307 6274 polypointindex = i;
308 }
309 }
310 }
311
312
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 2973 times.
2973 if (!pointfound) {
313 ✗ return 0;
314 }
315
316
1/1
✓ Branch 5 taken 2973 times.
2973 newpoly.Init(holeiter->GetNumPoints() + polyiter->GetNumPoints() + 2);
317 2973 i2 = 0;
318
2/2
✓ Branch 0 taken 59922 times.
✓ Branch 1 taken 2973 times.
62895 for (i = 0; i <= polypointindex; i++) {
319 59922 newpoly[i2] = polyiter->GetPoint(i);
320 59922 i2++;
321 }
322
2/2
✓ Branch 2 taken 14909 times.
✓ Branch 3 taken 2973 times.
17882 for (i = 0; i <= holeiter->GetNumPoints(); i++) {
323 14909 newpoly[i2] = holeiter->GetPoint((i + holepointindex) % holeiter->GetNumPoints());
324 14909 i2++;
325 }
326
2/2
✓ Branch 2 taken 26640 times.
✓ Branch 3 taken 2973 times.
29613 for (i = polypointindex; i < polyiter->GetNumPoints(); i++) {
327 26640 newpoly[i2] = polyiter->GetPoint(i);
328 26640 i2++;
329 }
330
331 2973 polys.erase(holeiter);
332 2973 polys.erase(polyiter);
333
1/1
✓ Branch 1 taken 2973 times.
2973 polys.push_back(newpoly);
334 }
335
336
2/2
✓ Branch 4 taken 1511 times.
✓ Branch 5 taken 1511 times.
3022 for (iter = polys.begin(); iter != polys.end(); iter++) {
337
1/1
✓ Branch 2 taken 1511 times.
1511 outpolys->push_back(*iter);
338 }
339
340 1511 return 1;
341 26540 }
342
343 3631444 bool TPPLPartition::IsConvex(TPPLPoint& p1, TPPLPoint& p2, TPPLPoint& p3) {
344 tppl_float tmp;
345 3631444 tmp = (p3.y - p1.y) * (p2.x - p1.x) - (p3.x - p1.x) * (p2.y - p1.y);
346
2/2
✓ Branch 0 taken 1995620 times.
✓ Branch 1 taken 1635824 times.
3631444 if (tmp > 0) {
347 1995620 return true;
348 } else {
349 1635824 return false;
350 }
351 }
352
353 2943 bool TPPLPartition::IsReflex(TPPLPoint& p1, TPPLPoint& p2, TPPLPoint& p3) {
354 tppl_float tmp;
355 2943 tmp = (p3.y - p1.y) * (p2.x - p1.x) - (p3.x - p1.x) * (p2.y - p1.y);
356
2/2
✓ Branch 0 taken 761 times.
✓ Branch 1 taken 2182 times.
2943 if (tmp < 0) {
357 761 return true;
358 } else {
359 2182 return false;
360 }
361 }
362
363 1765788 bool TPPLPartition::IsInside(TPPLPoint& p1, TPPLPoint& p2, TPPLPoint& p3, TPPLPoint& p) {
364
2/2
✓ Branch 1 taken 780155 times.
✓ Branch 2 taken 985633 times.
1765788 if (IsConvex(p1, p, p2)) {
365 780155 return false;
366 }
367
2/2
✓ Branch 1 taken 473675 times.
✓ Branch 2 taken 511958 times.
985633 if (IsConvex(p2, p, p3)) {
368 473675 return false;
369 }
370
2/2
✓ Branch 1 taken 493832 times.
✓ Branch 2 taken 18126 times.
511958 if (IsConvex(p3, p, p1)) {
371 493832 return false;
372 }
373 18126 return true;
374 }
375
376 71373 bool TPPLPartition::InCone(TPPLPoint& p1, TPPLPoint& p2, TPPLPoint& p3, TPPLPoint& p) {
377 bool convex;
378
379 71373 convex = IsConvex(p1, p2, p3);
380
381
2/2
✓ Branch 0 taken 35241 times.
✓ Branch 1 taken 36132 times.
71373 if (convex) {
382
2/2
✓ Branch 1 taken 16042 times.
✓ Branch 2 taken 19199 times.
35241 if (!IsConvex(p1, p2, p)) {
383 16042 return false;
384 }
385
2/2
✓ Branch 1 taken 10670 times.
✓ Branch 2 taken 8529 times.
19199 if (!IsConvex(p2, p3, p)) {
386 10670 return false;
387 }
388 8529 return true;
389 } else {
390
2/2
✓ Branch 1 taken 13621 times.
✓ Branch 2 taken 22511 times.
36132 if (IsConvex(p1, p2, p)) {
391 13621 return true;
392 }
393
2/2
✓ Branch 1 taken 10001 times.
✓ Branch 2 taken 12510 times.
22511 if (IsConvex(p2, p3, p)) {
394 10001 return true;
395 }
396 12510 return false;
397 }
398 }
399
400 ✗ bool TPPLPartition::InCone(PartitionVertex* v, TPPLPoint& p) {
401 TPPLPoint p1;
402 TPPLPoint p2;
403 TPPLPoint p3;
404
405 ✗ p1 = v->previous->p;
406 ✗ p2 = v->p;
407 ✗ p3 = v->next->p;
408
409 ✗ return InCone(p1, p2, p3, p);
410 }
411
412 ✗ void TPPLPartition::UpdateVertexReflexity(PartitionVertex* v) {
413 ✗ PartitionVertex* v1 = NULL;
414 ✗ PartitionVertex* v3 = NULL;
415 ✗ v1 = v->previous;
416 ✗ v3 = v->next;
417 ✗ v->isConvex = !IsReflex(v1->p, v->p, v3->p);
418 ✗ }
419
420 171611 void TPPLPartition::UpdateVertex(PartitionVertex* v, PartitionVertex* vertices, long numvertices) {
421 long i;
422 171611 PartitionVertex* v1 = NULL;
423 171611 PartitionVertex* v3 = NULL;
424 TPPLPoint vec1;
425 TPPLPoint vec3;
426
427 171611 v1 = v->previous;
428 171611 v3 = v->next;
429
430
1/1
✓ Branch 1 taken 171611 times.
171611 v->isConvex = IsConvex(v1->p, v->p, v3->p);
431
432
1/1
✓ Branch 2 taken 171611 times.
171611 vec1 = Normalize(v1->p - v->p);
433
1/1
✓ Branch 2 taken 171611 times.
171611 vec3 = Normalize(v3->p - v->p);
434 171611 v->angle = vec1.x * vec3.x + vec1.y * vec3.y;
435
436
2/2
✓ Branch 0 taken 153387 times.
✓ Branch 1 taken 18224 times.
171611 if (v->isConvex) {
437 153387 v->isEar = true;
438
2/2
✓ Branch 0 taken 2262338 times.
✓ Branch 1 taken 135261 times.
2397599 for (i = 0; i < numvertices; i++) {
439
4/4
✓ Branch 0 taken 385770 times.
✓ Branch 1 taken 1876568 times.
✓ Branch 2 taken 174123 times.
✓ Branch 3 taken 211647 times.
2262338 if ((vertices[i].p.x == v->p.x) && (vertices[i].p.y == v->p.y)) {
440 174123 continue;
441 }
442
4/4
✓ Branch 0 taken 303014 times.
✓ Branch 1 taken 1785201 times.
✓ Branch 2 taken 156864 times.
✓ Branch 3 taken 146150 times.
2088215 if ((vertices[i].p.x == v1->p.x) && (vertices[i].p.y == v1->p.y)) {
443 156864 continue;
444 }
445
4/4
✓ Branch 0 taken 313671 times.
✓ Branch 1 taken 1617680 times.
✓ Branch 2 taken 165563 times.
✓ Branch 3 taken 148108 times.
1931351 if ((vertices[i].p.x == v3->p.x) && (vertices[i].p.y == v3->p.y)) {
446 165563 continue;
447 }
448
3/3
✓ Branch 1 taken 1765788 times.
✓ Branch 3 taken 18126 times.
✓ Branch 4 taken 1747662 times.
1765788 if (IsInside(v1->p, v->p, v3->p, vertices[i].p)) {
449 18126 v->isEar = false;
450 18126 break;
451 }
452 }
453 } else {
454 18224 v->isEar = false;
455 }
456 171611 }
457
458 //triangulation by ear removal
459 26429 int TPPLPartition::Triangulate_EC(TPPLPoly* poly, TPPLPolyList* triangles) {
460
1/2
✗ Branch 1 not taken.
✓ Branch 2 taken 26429 times.
26429 if (!poly->Valid()) {
461 ✗ return 0;
462 }
463
464 long numvertices;
465 26429 PartitionVertex* vertices = NULL;
466 26429 PartitionVertex* ear = NULL;
467
1/1
✓ Branch 1 taken 26429 times.
26429 TPPLPoly triangle;
468 long i;
469 long j;
470 bool earfound;
471
472
1/2
✗ Branch 1 not taken.
✓ Branch 2 taken 26429 times.
26429 if (poly->GetNumPoints() < 3) {
473 ✗ return 0;
474 }
475
2/2
✓ Branch 1 taken 813 times.
✓ Branch 2 taken 25616 times.
26429 if (poly->GetNumPoints() == 3) {
476
1/1
✓ Branch 1 taken 813 times.
813 triangles->push_back(*poly);
477 813 return 1;
478 }
479
480 25616 numvertices = poly->GetNumPoints();
481
482
5/8
✓ Branch 0 taken 25616 times.
✗ Branch 1 not taken.
✓ Branch 4 taken 25616 times.
✓ Branch 7 taken 125513 times.
✓ Branch 9 taken 125513 times.
✓ Branch 10 taken 25616 times.
✗ Branch 11 not taken.
✗ Branch 12 not taken.
151129 vertices = new PartitionVertex[numvertices];
483
2/2
✓ Branch 0 taken 125513 times.
✓ Branch 1 taken 25616 times.
151129 for (i = 0; i < numvertices; i++) {
484 125513 vertices[i].isActive = true;
485 125513 vertices[i].p = poly->GetPoint(i);
486
2/2
✓ Branch 0 taken 25616 times.
✓ Branch 1 taken 99897 times.
125513 if (i == (numvertices - 1)) {
487 25616 vertices[i].next = &(vertices[0]);
488 } else {
489 99897 vertices[i].next = &(vertices[i + 1]);
490 }
491
2/2
✓ Branch 0 taken 25616 times.
✓ Branch 1 taken 99897 times.
125513 if (i == 0) {
492 25616 vertices[i].previous = &(vertices[numvertices - 1]);
493 } else {
494 99897 vertices[i].previous = &(vertices[i - 1]);
495 }
496 }
497
2/2
✓ Branch 0 taken 125513 times.
✓ Branch 1 taken 25616 times.
151129 for (i = 0; i < numvertices; i++) {
498
1/1
✓ Branch 1 taken 125513 times.
125513 UpdateVertex(&vertices[i], vertices, numvertices);
499 }
500
501
1/2
✓ Branch 0 taken 48665 times.
✗ Branch 1 not taken.
48665 for (i = 0; i < numvertices - 3; i++) {
502 48665 earfound = false;
503 //find the most extruded ear
504
2/2
✓ Branch 0 taken 1218626 times.
✓ Branch 1 taken 48665 times.
1267291 for (j = 0; j < numvertices; j++) {
505
2/2
✓ Branch 0 taken 511983 times.
✓ Branch 1 taken 706643 times.
1218626 if (!vertices[j].isActive) {
506 511983 continue;
507 }
508
2/2
✓ Branch 0 taken 448123 times.
✓ Branch 1 taken 258520 times.
706643 if (!vertices[j].isEar) {
509 448123 continue;
510 }
511
2/2
✓ Branch 0 taken 48665 times.
✓ Branch 1 taken 209855 times.
258520 if (!earfound) {
512 48665 earfound = true;
513 48665 ear = &(vertices[j]);
514 } else {
515
2/2
✓ Branch 0 taken 21464 times.
✓ Branch 1 taken 188391 times.
209855 if (vertices[j].angle > ear->angle) {
516 21464 ear = &(vertices[j]);
517 }
518 }
519 }
520
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 48665 times.
48665 if (!earfound) {
521 ✗ delete[] vertices;
522 ✗ return 0;
523 }
524
525
1/1
✓ Branch 1 taken 48665 times.
48665 triangle.Triangle(ear->previous->p, ear->p, ear->next->p);
526
1/1
✓ Branch 1 taken 48665 times.
48665 triangles->push_back(triangle);
527
528 48665 ear->isActive = false;
529 48665 ear->previous->next = ear->next;
530 48665 ear->next->previous = ear->previous;
531
532
2/2
✓ Branch 0 taken 25616 times.
✓ Branch 1 taken 23049 times.
48665 if (i == numvertices - 4) {
533 25616 break;
534 }
535
536
1/1
✓ Branch 1 taken 23049 times.
23049 UpdateVertex(ear->previous, vertices, numvertices);
537
1/1
✓ Branch 1 taken 23049 times.
23049 UpdateVertex(ear->next, vertices, numvertices);
538 }
539
1/2
✓ Branch 0 taken 57685 times.
✗ Branch 1 not taken.
57685 for (i = 0; i < numvertices; i++) {
540
2/2
✓ Branch 0 taken 25616 times.
✓ Branch 1 taken 32069 times.
57685 if (vertices[i].isActive) {
541
1/1
✓ Branch 1 taken 25616 times.
25616 triangle.Triangle(vertices[i].previous->p, vertices[i].p, vertices[i].next->p);
542
1/1
✓ Branch 1 taken 25616 times.
25616 triangles->push_back(triangle);
543 25616 break;
544 }
545 }
546
547
1/2
✓ Branch 0 taken 25616 times.
✗ Branch 1 not taken.
25616 delete[] vertices;
548
549 25616 return 1;
550 26429 }
551
552 25668 int TPPLPartition::Triangulate_EC(TPPLPolyList* inpolys, TPPLPolyList* triangles) {
553 25668 TPPLPolyList outpolys;
554 25668 TPPLPolyList::iterator iter;
555
556
2/3
✓ Branch 1 taken 25668 times.
✗ Branch 3 not taken.
✓ Branch 4 taken 25668 times.
25668 if (RemoveHoles(inpolys, &outpolys) == 0) {
557 ✗ return 0;
558 }
559
2/2
✓ Branch 4 taken 25668 times.
✓ Branch 5 taken 25668 times.
51336 for (iter = outpolys.begin(); iter != outpolys.end(); iter++) {
560
2/3
✓ Branch 2 taken 25668 times.
✗ Branch 4 not taken.
✓ Branch 5 taken 25668 times.
25668 if (Triangulate_EC(&(*iter), triangles) == 0) {
561 ✗ return 0;
562 }
563 }
564 25668 return 1;
565 25668 }
566
567 872 int TPPLPartition::ConvexPartition_HM(TPPLPoly* poly, TPPLPolyList* parts) {
568
1/2
✗ Branch 1 not taken.
✓ Branch 2 taken 872 times.
872 if (!poly->Valid()) {
569 ✗ return 0;
570 }
571
572 872 TPPLPolyList triangles;
573 872 TPPLPolyList::iterator iter1;
574 872 TPPLPolyList::iterator iter2;
575 872 TPPLPoly* poly1 = NULL;
576 872 TPPLPoly* poly2 = NULL;
577
1/1
✓ Branch 1 taken 872 times.
872 TPPLPoly newpoly;
578 TPPLPoint d1;
579 TPPLPoint d2;
580 TPPLPoint p1;
581 TPPLPoint p2;
582 TPPLPoint p3;
583 long i11;
584 long i12;
585 long i21;
586 long i22;
587 long i13;
588 long i23;
589 long j;
590 long k;
591 bool isdiagonal;
592 long numreflex;
593
594 //check if the poly is already convex
595 872 numreflex = 0;
596
2/2
✓ Branch 1 taken 2943 times.
✓ Branch 2 taken 111 times.
3054 for (i11 = 0; i11 < poly->GetNumPoints(); i11++) {
597
2/2
✓ Branch 0 taken 872 times.
✓ Branch 1 taken 2071 times.
2943 if (i11 == 0) {
598 872 i12 = poly->GetNumPoints() - 1;
599 } else {
600 2071 i12 = i11 - 1;
601 }
602
2/2
✓ Branch 1 taken 111 times.
✓ Branch 2 taken 2832 times.
2943 if (i11 == (poly->GetNumPoints() - 1)) {
603 111 i13 = 0;
604 } else {
605 2832 i13 = i11 + 1;
606 }
607
3/3
✓ Branch 4 taken 2943 times.
✓ Branch 6 taken 761 times.
✓ Branch 7 taken 2182 times.
2943 if (IsReflex(poly->GetPoint(i12), poly->GetPoint(i11), poly->GetPoint(i13))) {
608 761 numreflex = 1;
609 761 break;
610 }
611 }
612
2/2
✓ Branch 0 taken 111 times.
✓ Branch 1 taken 761 times.
872 if (numreflex == 0) {
613
1/1
✓ Branch 1 taken 111 times.
111 parts->push_back(*poly);
614 111 return 1;
615 }
616
617
2/3
✓ Branch 1 taken 761 times.
✗ Branch 3 not taken.
✓ Branch 4 taken 761 times.
761 if (Triangulate_EC(poly, &triangles) == 0) {
618 ✗ return 0;
619 }
620
621
2/2
✓ Branch 4 taken 3925 times.
✓ Branch 5 taken 761 times.
4686 for (iter1 = triangles.begin(); iter1 != triangles.end(); iter1++) {
622 3925 poly1 = &(*iter1);
623
2/2
✓ Branch 1 taken 23062 times.
✓ Branch 2 taken 3925 times.
26987 for (i11 = 0; i11 < poly1->GetNumPoints(); i11++) {
624 23062 d1 = poly1->GetPoint(i11);
625 23062 i12 = (i11 + 1) % (poly1->GetNumPoints());
626 23062 d2 = poly1->GetPoint(i12);
627
628 23062 isdiagonal = false;
629
2/2
✓ Branch 3 taken 131758 times.
✓ Branch 4 taken 16132 times.
147890 for (iter2 = iter1; iter2 != triangles.end(); iter2++) {
630
2/2
✓ Branch 1 taken 23062 times.
✓ Branch 2 taken 108696 times.
131758 if (iter1 == iter2) {
631 23062 continue;
632 }
633 108696 poly2 = &(*iter2);
634
635
2/2
✓ Branch 1 taken 316179 times.
✓ Branch 2 taken 101766 times.
417945 for (i21 = 0; i21 < poly2->GetNumPoints(); i21++) {
636
6/6
✓ Branch 1 taken 43138 times.
✓ Branch 2 taken 273041 times.
✓ Branch 4 taken 23240 times.
✓ Branch 5 taken 19898 times.
✓ Branch 6 taken 296281 times.
✓ Branch 7 taken 19898 times.
316179 if ((d2.x != poly2->GetPoint(i21).x) || (d2.y != poly2->GetPoint(i21).y)) {
637 296281 continue;
638 }
639 19898 i22 = (i21 + 1) % (poly2->GetNumPoints());
640
6/6
✓ Branch 1 taken 7281 times.
✓ Branch 2 taken 12617 times.
✓ Branch 4 taken 351 times.
✓ Branch 5 taken 6930 times.
✓ Branch 6 taken 12968 times.
✓ Branch 7 taken 6930 times.
19898 if ((d1.x != poly2->GetPoint(i22).x) || (d1.y != poly2->GetPoint(i22).y)) {
641 12968 continue;
642 }
643 6930 isdiagonal = true;
644 6930 break;
645 }
646
2/2
✓ Branch 0 taken 6930 times.
✓ Branch 1 taken 101766 times.
108696 if (isdiagonal) {
647 6930 break;
648 }
649 }
650
651
2/2
✓ Branch 0 taken 16132 times.
✓ Branch 1 taken 6930 times.
23062 if (!isdiagonal) {
652 16132 continue;
653 }
654
655 6930 p2 = poly1->GetPoint(i11);
656
2/2
✓ Branch 0 taken 710 times.
✓ Branch 1 taken 6220 times.
6930 if (i11 == 0) {
657 710 i13 = poly1->GetNumPoints() - 1;
658 } else {
659 6220 i13 = i11 - 1;
660 }
661 6930 p1 = poly1->GetPoint(i13);
662
2/2
✓ Branch 1 taken 3155 times.
✓ Branch 2 taken 3775 times.
6930 if (i22 == (poly2->GetNumPoints() - 1)) {
663 3155 i23 = 0;
664 } else {
665 3775 i23 = i22 + 1;
666 }
667 6930 p3 = poly2->GetPoint(i23);
668
669
3/3
✓ Branch 1 taken 6930 times.
✓ Branch 3 taken 1862 times.
✓ Branch 4 taken 5068 times.
6930 if (!IsConvex(p1, p2, p3)) {
670 1862 continue;
671 }
672
673 5068 p2 = poly1->GetPoint(i12);
674
2/2
✓ Branch 1 taken 1074 times.
✓ Branch 2 taken 3994 times.
5068 if (i12 == (poly1->GetNumPoints() - 1)) {
675 1074 i13 = 0;
676 } else {
677 3994 i13 = i12 + 1;
678 }
679 5068 p3 = poly1->GetPoint(i13);
680
2/2
✓ Branch 0 taken 2961 times.
✓ Branch 1 taken 2107 times.
5068 if (i21 == 0) {
681 2961 i23 = poly2->GetNumPoints() - 1;
682 } else {
683 2107 i23 = i21 - 1;
684 }
685 5068 p1 = poly2->GetPoint(i23);
686
687
3/3
✓ Branch 1 taken 5068 times.
✓ Branch 3 taken 2156 times.
✓ Branch 4 taken 2912 times.
5068 if (!IsConvex(p1, p2, p3)) {
688 2156 continue;
689 }
690
691
1/1
✓ Branch 3 taken 2912 times.
2912 newpoly.Init(poly1->GetNumPoints() + poly2->GetNumPoints() - 2);
692 2912 k = 0;
693
2/2
✓ Branch 0 taken 6102 times.
✓ Branch 1 taken 2912 times.
9014 for (j = i12; j != i11; j = (j + 1) % (poly1->GetNumPoints())) {
694 6102 newpoly[k] = poly1->GetPoint(j);
695 6102 k++;
696 }
697
2/2
✓ Branch 0 taken 5824 times.
✓ Branch 1 taken 2912 times.
8736 for (j = i22; j != i21; j = (j + 1) % (poly2->GetNumPoints())) {
698 5824 newpoly[k] = poly2->GetPoint(j);
699 5824 k++;
700 }
701
702 2912 triangles.erase(iter2);
703
1/1
✓ Branch 2 taken 2912 times.
2912 *iter1 = newpoly;
704 2912 poly1 = &(*iter1);
705 2912 i11 = -1;
706
707 2912 continue;
708 }
709 }
710
711
2/2
✓ Branch 4 taken 3925 times.
✓ Branch 5 taken 761 times.
4686 for (iter1 = triangles.begin(); iter1 != triangles.end(); iter1++) {
712
1/1
✓ Branch 2 taken 3925 times.
3925 parts->push_back(*iter1);
713 }
714
715 761 return 1;
716 872 }
717
718 872 int TPPLPartition::ConvexPartition_HM(TPPLPolyList* inpolys, TPPLPolyList* parts) {
719 872 TPPLPolyList outpolys;
720 872 TPPLPolyList::iterator iter;
721
722
2/3
✓ Branch 1 taken 872 times.
✗ Branch 3 not taken.
✓ Branch 4 taken 872 times.
872 if (RemoveHoles(inpolys, &outpolys) == 0) {
723 ✗ return 0;
724 }
725
2/2
✓ Branch 4 taken 872 times.
✓ Branch 5 taken 872 times.
1744 for (iter = outpolys.begin(); iter != outpolys.end(); iter++) {
726
2/3
✓ Branch 2 taken 872 times.
✗ Branch 4 not taken.
✓ Branch 5 taken 872 times.
872 if (ConvexPartition_HM(&(*iter), parts) == 0) {
727 ✗ return 0;
728 }
729 }
730 872 return 1;
731 872 }
732
733 //minimum-weight polygon triangulation by dynamic programming
734 //O(n^3) time complexity
735 //O(n^2) space complexity
736 ✗ int TPPLPartition::Triangulate_OPT(TPPLPoly* poly, TPPLPolyList* triangles) {
737 ✗ if (!poly->Valid()) {
738 ✗ return 0;
739 }
740
741 long i;
742 long j;
743 long k;
744 long gap;
745 long n;
746 ✗ DPState** dpstates = NULL;
747 TPPLPoint p1;
748 TPPLPoint p2;
749 TPPLPoint p3;
750 TPPLPoint p4;
751 long bestvertex;
752 tppl_float weight;
753 tppl_float minweight;
754 tppl_float d1;
755 tppl_float d2;
756 Diagonal diagonal;
757 Diagonal newdiagonal;
758 ✗ DiagonalList diagonals;
759 ✗ TPPLPoly triangle;
760 ✗ int ret = 1;
761
762 ✗ n = poly->GetNumPoints();
763 ✗ dpstates = new DPState*[n];
764 ✗ for (i = 1; i < n; i++) {
765 ✗ dpstates[i] = new DPState[i];
766 }
767
768 //init states and visibility
769 ✗ for (i = 0; i < (n - 1); i++) {
770 ✗ p1 = poly->GetPoint(i);
771 ✗ for (j = i + 1; j < n; j++) {
772 ✗ dpstates[j][i].visible = true;
773 ✗ dpstates[j][i].weight = 0;
774 ✗ dpstates[j][i].bestvertex = -1;
775 ✗ if (j != (i + 1)) {
776 ✗ p2 = poly->GetPoint(j);
777
778 //visibility check
779 ✗ if (i == 0) {
780 ✗ p3 = poly->GetPoint(n - 1);
781 } else {
782 ✗ p3 = poly->GetPoint(i - 1);
783 }
784 ✗ if (i == (n - 1)) {
785 ✗ p4 = poly->GetPoint(0);
786 } else {
787 ✗ p4 = poly->GetPoint(i + 1);
788 }
789 ✗ if (!InCone(p3, p1, p4, p2)) {
790 ✗ dpstates[j][i].visible = false;
791 ✗ continue;
792 }
793
794 ✗ if (j == 0) {
795 ✗ p3 = poly->GetPoint(n - 1);
796 } else {
797 ✗ p3 = poly->GetPoint(j - 1);
798 }
799 ✗ if (j == (n - 1)) {
800 ✗ p4 = poly->GetPoint(0);
801 } else {
802 ✗ p4 = poly->GetPoint(j + 1);
803 }
804 ✗ if (!InCone(p3, p2, p4, p1)) {
805 ✗ dpstates[j][i].visible = false;
806 ✗ continue;
807 }
808
809 ✗ for (k = 0; k < n; k++) {
810 ✗ p3 = poly->GetPoint(k);
811 ✗ if (k == (n - 1)) {
812 ✗ p4 = poly->GetPoint(0);
813 } else {
814 ✗ p4 = poly->GetPoint(k + 1);
815 }
816 ✗ if (Intersects(p1, p2, p3, p4) != 0) {
817 ✗ dpstates[j][i].visible = false;
818 ✗ break;
819 }
820 }
821 }
822 }
823 }
824 ✗ dpstates[n - 1][0].visible = true;
825 ✗ dpstates[n - 1][0].weight = 0;
826 ✗ dpstates[n - 1][0].bestvertex = -1;
827
828 ✗ for (gap = 2; gap < n; gap++) {
829 ✗ for (i = 0; i < (n - gap); i++) {
830 ✗ j = i + gap;
831 ✗ if (!dpstates[j][i].visible) {
832 ✗ continue;
833 }
834 ✗ bestvertex = -1;
835 ✗ for (k = (i + 1); k < j; k++) {
836 ✗ if (!dpstates[k][i].visible) {
837 ✗ continue;
838 }
839 ✗ if (!dpstates[j][k].visible) {
840 ✗ continue;
841 }
842
843 ✗ if (k <= (i + 1)) {
844 ✗ d1 = 0;
845 } else {
846 ✗ d1 = Distance(poly->GetPoint(i), poly->GetPoint(k));
847 }
848 ✗ if (j <= (k + 1)) {
849 ✗ d2 = 0;
850 } else {
851 ✗ d2 = Distance(poly->GetPoint(k), poly->GetPoint(j));
852 }
853
854 ✗ weight = dpstates[k][i].weight + dpstates[j][k].weight + d1 + d2;
855
856 ✗ if ((bestvertex == -1) || (weight < minweight)) {
857 ✗ bestvertex = k;
858 ✗ minweight = weight;
859 }
860 }
861 ✗ if (bestvertex == -1) {
862 ✗ for (i = 1; i < n; i++) {
863 ✗ delete[] dpstates[i];
864 }
865 ✗ delete[] dpstates;
866
867 ✗ return 0;
868 }
869
870 ✗ dpstates[j][i].bestvertex = bestvertex;
871 ✗ dpstates[j][i].weight = minweight;
872 }
873 }
874
875 ✗ newdiagonal.index1 = 0;
876 ✗ newdiagonal.index2 = n - 1;
877 ✗ diagonals.push_back(newdiagonal);
878 ✗ while (!diagonals.empty()) {
879 ✗ diagonal = *(diagonals.begin());
880 ✗ diagonals.pop_front();
881 ✗ bestvertex = dpstates[diagonal.index2][diagonal.index1].bestvertex;
882 ✗ if (bestvertex == -1) {
883 ✗ ret = 0;
884 ✗ break;
885 }
886 ✗ triangle.Triangle(poly->GetPoint(diagonal.index1), poly->GetPoint(bestvertex), poly->GetPoint(diagonal.index2));
887 ✗ triangles->push_back(triangle);
888 ✗ if (bestvertex > (diagonal.index1 + 1)) {
889 ✗ newdiagonal.index1 = diagonal.index1;
890 ✗ newdiagonal.index2 = bestvertex;
891 ✗ diagonals.push_back(newdiagonal);
892 }
893 ✗ if (diagonal.index2 > (bestvertex + 1)) {
894 ✗ newdiagonal.index1 = bestvertex;
895 ✗ newdiagonal.index2 = diagonal.index2;
896 ✗ diagonals.push_back(newdiagonal);
897 }
898 }
899
900 ✗ for (i = 1; i < n; i++) {
901 ✗ delete[] dpstates[i];
902 }
903 ✗ delete[] dpstates;
904
905 ✗ return ret;
906 ✗ }
907
908 ✗ void TPPLPartition::UpdateState(long a, long b, long w, long i, long j, DPState2** dpstates) {
909 Diagonal newdiagonal;
910 ✗ DiagonalList* pairs = NULL;
911 long w2;
912
913 ✗ w2 = dpstates[a][b].weight;
914 ✗ if (w > w2) {
915 ✗ return;
916 }
917
918 ✗ pairs = &(dpstates[a][b].pairs);
919 ✗ newdiagonal.index1 = i;
920 ✗ newdiagonal.index2 = j;
921
922 ✗ if (w < w2) {
923 ✗ pairs->clear();
924 ✗ pairs->push_front(newdiagonal);
925 ✗ dpstates[a][b].weight = w;
926 } else {
927 ✗ if ((!pairs->empty()) && (i <= pairs->begin()->index1)) {
928 ✗ return;
929 }
930 ✗ while ((!pairs->empty()) && (pairs->begin()->index2 >= j)) {
931 ✗ pairs->pop_front();
932 }
933 ✗ pairs->push_front(newdiagonal);
934 }
935 }
936
937 ✗ void TPPLPartition::TypeA(long i, long j, long k, PartitionVertex* vertices, DPState2** dpstates) {
938 ✗ DiagonalList* pairs = NULL;
939 ✗ DiagonalList::iterator iter;
940 ✗ DiagonalList::iterator lastiter;
941 long top;
942 long w;
943
944 ✗ if (!dpstates[i][j].visible) {
945 ✗ return;
946 }
947 ✗ top = j;
948 ✗ w = dpstates[i][j].weight;
949 ✗ if (k - j > 1) {
950 ✗ if (!dpstates[j][k].visible) {
951 ✗ return;
952 }
953 ✗ w += dpstates[j][k].weight + 1;
954 }
955 ✗ if (j - i > 1) {
956 ✗ pairs = &(dpstates[i][j].pairs);
957 ✗ iter = pairs->end();
958 ✗ lastiter = pairs->end();
959 ✗ while (iter != pairs->begin()) {
960 ✗ iter--;
961 ✗ if (!IsReflex(vertices[iter->index2].p, vertices[j].p, vertices[k].p)) {
962 ✗ lastiter = iter;
963 } else {
964 ✗ break;
965 }
966 }
967 ✗ if (lastiter == pairs->end()) {
968 ✗ w++;
969 } else {
970 ✗ if (IsReflex(vertices[k].p, vertices[i].p, vertices[lastiter->index1].p)) {
971 ✗ w++;
972 } else {
973 ✗ top = lastiter->index1;
974 }
975 }
976 }
977 ✗ UpdateState(i, k, w, top, j, dpstates);
978 }
979
980 ✗ void TPPLPartition::TypeB(long i, long j, long k, PartitionVertex* vertices, DPState2** dpstates) {
981 ✗ DiagonalList* pairs = NULL;
982 ✗ DiagonalList::iterator iter;
983 ✗ DiagonalList::iterator lastiter;
984 long top;
985 long w;
986
987 ✗ if (!dpstates[j][k].visible) {
988 ✗ return;
989 }
990 ✗ top = j;
991 ✗ w = dpstates[j][k].weight;
992
993 ✗ if (j - i > 1) {
994 ✗ if (!dpstates[i][j].visible) {
995 ✗ return;
996 }
997 ✗ w += dpstates[i][j].weight + 1;
998 }
999 ✗ if (k - j > 1) {
1000 ✗ pairs = &(dpstates[j][k].pairs);
1001
1002 ✗ iter = pairs->begin();
1003 ✗ if ((!pairs->empty()) && (!IsReflex(vertices[i].p, vertices[j].p, vertices[iter->index1].p))) {
1004 ✗ lastiter = iter;
1005 ✗ while (iter != pairs->end()) {
1006 ✗ if (!IsReflex(vertices[i].p, vertices[j].p, vertices[iter->index1].p)) {
1007 ✗ lastiter = iter;
1008 ✗ iter++;
1009 } else {
1010 ✗ break;
1011 }
1012 }
1013 ✗ if (IsReflex(vertices[lastiter->index2].p, vertices[k].p, vertices[i].p)) {
1014 ✗ w++;
1015 } else {
1016 ✗ top = lastiter->index2;
1017 }
1018 } else {
1019 ✗ w++;
1020 }
1021 }
1022 ✗ UpdateState(i, k, w, j, top, dpstates);
1023 }
1024
1025 ✗ int TPPLPartition::ConvexPartition_OPT(TPPLPoly* poly, TPPLPolyList* parts) {
1026 ✗ if (!poly->Valid()) {
1027 ✗ return 0;
1028 }
1029
1030 TPPLPoint p1;
1031 TPPLPoint p2;
1032 TPPLPoint p3;
1033 TPPLPoint p4;
1034 ✗ PartitionVertex* vertices = NULL;
1035 ✗ DPState2** dpstates = NULL;
1036 long i;
1037 long j;
1038 long k;
1039 long n;
1040 long gap;
1041 ✗ DiagonalList diagonals;
1042 ✗ DiagonalList diagonals2;
1043 Diagonal diagonal;
1044 Diagonal newdiagonal;
1045 ✗ DiagonalList* pairs = NULL;
1046 ✗ DiagonalList* pairs2 = NULL;
1047 ✗ DiagonalList::iterator iter;
1048 ✗ DiagonalList::iterator iter2;
1049 int ret;
1050 ✗ TPPLPoly newpoly;
1051 ✗ vector<long> indices;
1052 ✗ vector<long>::iterator iiter;
1053 bool ijreal;
1054 bool jkreal;
1055
1056 ✗ n = poly->GetNumPoints();
1057 ✗ vertices = new PartitionVertex[n];
1058
1059 ✗ dpstates = new DPState2*[n];
1060 ✗ for (i = 0; i < n; i++) {
1061 ✗ dpstates[i] = new DPState2[n];
1062 }
1063
1064 //init vertex information
1065 ✗ for (i = 0; i < n; i++) {
1066 ✗ vertices[i].p = poly->GetPoint(i);
1067 ✗ vertices[i].isActive = true;
1068 ✗ if (i == 0) {
1069 ✗ vertices[i].previous = &(vertices[n - 1]);
1070 } else {
1071 ✗ vertices[i].previous = &(vertices[i - 1]);
1072 }
1073 ✗ if (i == (poly->GetNumPoints() - 1)) {
1074 ✗ vertices[i].next = &(vertices[0]);
1075 } else {
1076 ✗ vertices[i].next = &(vertices[i + 1]);
1077 }
1078 }
1079 ✗ for (i = 1; i < n; i++) {
1080 ✗ UpdateVertexReflexity(&(vertices[i]));
1081 }
1082
1083 //init states and visibility
1084 ✗ for (i = 0; i < (n - 1); i++) {
1085 ✗ p1 = poly->GetPoint(i);
1086 ✗ for (j = i + 1; j < n; j++) {
1087 ✗ dpstates[i][j].visible = true;
1088 ✗ if (j == i + 1) {
1089 ✗ dpstates[i][j].weight = 0;
1090 } else {
1091 ✗ dpstates[i][j].weight = 2147483647;
1092 }
1093 ✗ if (j != (i + 1)) {
1094 ✗ p2 = poly->GetPoint(j);
1095
1096 //visibility check
1097 ✗ if (!InCone(&vertices[i], p2)) {
1098 ✗ dpstates[i][j].visible = false;
1099 ✗ continue;
1100 }
1101 ✗ if (!InCone(&vertices[j], p1)) {
1102 ✗ dpstates[i][j].visible = false;
1103 ✗ continue;
1104 }
1105
1106 ✗ for (k = 0; k < n; k++) {
1107 ✗ p3 = poly->GetPoint(k);
1108 ✗ if (k == (n - 1)) {
1109 ✗ p4 = poly->GetPoint(0);
1110 } else {
1111 ✗ p4 = poly->GetPoint(k + 1);
1112 }
1113 ✗ if (Intersects(p1, p2, p3, p4) != 0) {
1114 ✗ dpstates[i][j].visible = false;
1115 ✗ break;
1116 }
1117 }
1118 }
1119 }
1120 }
1121 ✗ for (i = 0; i < (n - 2); i++) {
1122 ✗ j = i + 2;
1123 ✗ if (dpstates[i][j].visible) {
1124 ✗ dpstates[i][j].weight = 0;
1125 ✗ newdiagonal.index1 = i + 1;
1126 ✗ newdiagonal.index2 = i + 1;
1127 ✗ dpstates[i][j].pairs.push_back(newdiagonal);
1128 }
1129 }
1130
1131 ✗ dpstates[0][n - 1].visible = true;
1132 ✗ vertices[0].isConvex = false; //by convention
1133
1134 ✗ for (gap = 3; gap < n; gap++) {
1135 ✗ for (i = 0; i < n - gap; i++) {
1136 ✗ if (vertices[i].isConvex) {
1137 ✗ continue;
1138 }
1139 ✗ k = i + gap;
1140 ✗ if (dpstates[i][k].visible) {
1141 ✗ if (!vertices[k].isConvex) {
1142 ✗ for (j = i + 1; j < k; j++) {
1143 ✗ TypeA(i, j, k, vertices, dpstates);
1144 }
1145 } else {
1146 ✗ for (j = i + 1; j < (k - 1); j++) {
1147 ✗ if (vertices[j].isConvex) {
1148 ✗ continue;
1149 }
1150 ✗ TypeA(i, j, k, vertices, dpstates);
1151 }
1152 ✗ TypeA(i, k - 1, k, vertices, dpstates);
1153 }
1154 }
1155 }
1156 ✗ for (k = gap; k < n; k++) {
1157 ✗ if (vertices[k].isConvex) {
1158 ✗ continue;
1159 }
1160 ✗ i = k - gap;
1161 ✗ if ((vertices[i].isConvex) && (dpstates[i][k].visible)) {
1162 ✗ TypeB(i, i + 1, k, vertices, dpstates);
1163 ✗ for (j = i + 2; j < k; j++) {
1164 ✗ if (vertices[j].isConvex) {
1165 ✗ continue;
1166 }
1167 ✗ TypeB(i, j, k, vertices, dpstates);
1168 }
1169 }
1170 }
1171 }
1172
1173 //recover solution
1174 ✗ ret = 1;
1175 ✗ newdiagonal.index1 = 0;
1176 ✗ newdiagonal.index2 = n - 1;
1177 ✗ diagonals.push_front(newdiagonal);
1178 ✗ while (!diagonals.empty()) {
1179 ✗ diagonal = *(diagonals.begin());
1180 ✗ diagonals.pop_front();
1181 ✗ if ((diagonal.index2 - diagonal.index1) <= 1) {
1182 ✗ continue;
1183 }
1184 ✗ pairs = &(dpstates[diagonal.index1][diagonal.index2].pairs);
1185 ✗ if (pairs->empty()) {
1186 ✗ ret = 0;
1187 ✗ break;
1188 }
1189 ✗ if (!vertices[diagonal.index1].isConvex) {
1190 ✗ iter = pairs->end();
1191 ✗ iter--;
1192 ✗ j = iter->index2;
1193 ✗ newdiagonal.index1 = j;
1194 ✗ newdiagonal.index2 = diagonal.index2;
1195 ✗ diagonals.push_front(newdiagonal);
1196 ✗ if ((j - diagonal.index1) > 1) {
1197 ✗ if (iter->index1 != iter->index2) {
1198 ✗ pairs2 = &(dpstates[diagonal.index1][j].pairs);
1199 while (true) {
1200 ✗ if (pairs2->empty()) {
1201 ✗ ret = 0;
1202 ✗ break;
1203 }
1204 ✗ iter2 = pairs2->end();
1205 ✗ iter2--;
1206 ✗ if (iter->index1 != iter2->index1) {
1207 ✗ pairs2->pop_back();
1208 } else {
1209 ✗ break;
1210 }
1211 }
1212 ✗ if (ret == 0) {
1213 ✗ break;
1214 }
1215 }
1216 ✗ newdiagonal.index1 = diagonal.index1;
1217 ✗ newdiagonal.index2 = j;
1218 ✗ diagonals.push_front(newdiagonal);
1219 }
1220 } else {
1221 ✗ iter = pairs->begin();
1222 ✗ j = iter->index1;
1223 ✗ newdiagonal.index1 = diagonal.index1;
1224 ✗ newdiagonal.index2 = j;
1225 ✗ diagonals.push_front(newdiagonal);
1226 ✗ if ((diagonal.index2 - j) > 1) {
1227 ✗ if (iter->index1 != iter->index2) {
1228 ✗ pairs2 = &(dpstates[j][diagonal.index2].pairs);
1229 while (true) {
1230 ✗ if (pairs2->empty()) {
1231 ✗ ret = 0;
1232 ✗ break;
1233 }
1234 ✗ iter2 = pairs2->begin();
1235 ✗ if (iter->index2 != iter2->index2) {
1236 ✗ pairs2->pop_front();
1237 } else {
1238 ✗ break;
1239 }
1240 }
1241 ✗ if (ret == 0) {
1242 ✗ break;
1243 }
1244 }
1245 ✗ newdiagonal.index1 = j;
1246 ✗ newdiagonal.index2 = diagonal.index2;
1247 ✗ diagonals.push_front(newdiagonal);
1248 }
1249 }
1250 }
1251
1252 ✗ if (ret == 0) {
1253 ✗ for (i = 0; i < n; i++) {
1254 ✗ delete[] dpstates[i];
1255 }
1256 ✗ delete[] dpstates;
1257 ✗ delete[] vertices;
1258
1259 ✗ return ret;
1260 }
1261
1262 ✗ newdiagonal.index1 = 0;
1263 ✗ newdiagonal.index2 = n - 1;
1264 ✗ diagonals.push_front(newdiagonal);
1265 ✗ while (!diagonals.empty()) {
1266 ✗ diagonal = *(diagonals.begin());
1267 ✗ diagonals.pop_front();
1268 ✗ if ((diagonal.index2 - diagonal.index1) <= 1) {
1269 ✗ continue;
1270 }
1271
1272 ✗ indices.clear();
1273 ✗ diagonals2.clear();
1274 ✗ indices.push_back(diagonal.index1);
1275 ✗ indices.push_back(diagonal.index2);
1276 ✗ diagonals2.push_front(diagonal);
1277
1278 ✗ while (!diagonals2.empty()) {
1279 ✗ diagonal = *(diagonals2.begin());
1280 ✗ diagonals2.pop_front();
1281 ✗ if ((diagonal.index2 - diagonal.index1) <= 1) {
1282 ✗ continue;
1283 }
1284 ✗ ijreal = true;
1285 ✗ jkreal = true;
1286 ✗ pairs = &(dpstates[diagonal.index1][diagonal.index2].pairs);
1287 ✗ if (!vertices[diagonal.index1].isConvex) {
1288 ✗ iter = pairs->end();
1289 ✗ iter--;
1290 ✗ j = iter->index2;
1291 ✗ if (iter->index1 != iter->index2) {
1292 ✗ ijreal = false;
1293 }
1294 } else {
1295 ✗ iter = pairs->begin();
1296 ✗ j = iter->index1;
1297 ✗ if (iter->index1 != iter->index2) {
1298 ✗ jkreal = false;
1299 }
1300 }
1301
1302 ✗ newdiagonal.index1 = diagonal.index1;
1303 ✗ newdiagonal.index2 = j;
1304 ✗ if (ijreal) {
1305 ✗ diagonals.push_back(newdiagonal);
1306 } else {
1307 ✗ diagonals2.push_back(newdiagonal);
1308 }
1309
1310 ✗ newdiagonal.index1 = j;
1311 ✗ newdiagonal.index2 = diagonal.index2;
1312 ✗ if (jkreal) {
1313 ✗ diagonals.push_back(newdiagonal);
1314 } else {
1315 ✗ diagonals2.push_back(newdiagonal);
1316 }
1317
1318 ✗ indices.push_back(j);
1319 }
1320
1321 ✗ std::sort(indices.begin(), indices.end());
1322 ✗ newpoly.Init((long)indices.size());
1323 ✗ k = 0;
1324 ✗ for (iiter = indices.begin(); iiter != indices.end(); iiter++) {
1325 ✗ newpoly[k] = vertices[*iiter].p;
1326 ✗ k++;
1327 }
1328 ✗ parts->push_back(newpoly);
1329 }
1330
1331 ✗ for (i = 0; i < n; i++) {
1332 ✗ delete[] dpstates[i];
1333 }
1334 ✗ delete[] dpstates;
1335 ✗ delete[] vertices;
1336
1337 ✗ return ret;
1338 ✗ }
1339
1340 //triangulates a set of polygons by first partitioning them into monotone polygons
1341 //O(n*std::log(n)) time complexity, O(n) space complexity
1342 //the algorithm used here is outlined in the book
1343 //"Computational Geometry: Algorithms and Applications"
1344 //by Mark de Berg, Otfried Cheong, Marc van Kreveld and Mark Overmars
1345 ✗ int TPPLPartition::MonotonePartition(TPPLPolyList* inpolys, TPPLPolyList* monotonePolys) {
1346 ✗ TPPLPolyList::iterator iter;
1347 ✗ MonotoneVertex* vertices = NULL;
1348 long i;
1349 long numvertices;
1350 long vindex;
1351 long vindex2;
1352 long newnumvertices;
1353 long maxnumvertices;
1354 long polystartindex;
1355 long polyendindex;
1356 ✗ TPPLPoly* poly = NULL;
1357 ✗ MonotoneVertex* v = NULL;
1358 ✗ MonotoneVertex* v2 = NULL;
1359 ✗ MonotoneVertex* vprev = NULL;
1360 ✗ MonotoneVertex* vnext = NULL;
1361 ScanLineEdge newedge;
1362 ✗ bool error = false;
1363
1364 ✗ numvertices = 0;
1365 ✗ for (iter = inpolys->begin(); iter != inpolys->end(); iter++) {
1366 ✗ if (!iter->Valid()) {
1367 ✗ return 0;
1368 }
1369 ✗ numvertices += iter->GetNumPoints();
1370 }
1371
1372 ✗ maxnumvertices = numvertices * 3;
1373 ✗ vertices = new MonotoneVertex[maxnumvertices];
1374 ✗ newnumvertices = numvertices;
1375
1376 ✗ polystartindex = 0;
1377 ✗ for (iter = inpolys->begin(); iter != inpolys->end(); iter++) {
1378 ✗ poly = &(*iter);
1379 ✗ polyendindex = polystartindex + poly->GetNumPoints() - 1;
1380 ✗ for (i = 0; i < poly->GetNumPoints(); i++) {
1381 ✗ vertices[i + polystartindex].p = poly->GetPoint(i);
1382 ✗ if (i == 0) {
1383 ✗ vertices[i + polystartindex].previous = polyendindex;
1384 } else {
1385 ✗ vertices[i + polystartindex].previous = i + polystartindex - 1;
1386 }
1387 ✗ if (i == (poly->GetNumPoints() - 1)) {
1388 ✗ vertices[i + polystartindex].next = polystartindex;
1389 } else {
1390 ✗ vertices[i + polystartindex].next = i + polystartindex + 1;
1391 }
1392 }
1393 ✗ polystartindex = polyendindex + 1;
1394 }
1395
1396 //construct the priority queue
1397 ✗ long* priority = new long[numvertices];
1398 ✗ for (i = 0; i < numvertices; i++) {
1399 ✗ priority[i] = i;
1400 }
1401 ✗ std::sort(priority, &(priority[numvertices]), VertexSorter(vertices));
1402
1403 //determine vertex types
1404 ✗ char* vertextypes = new char[maxnumvertices];
1405 ✗ for (i = 0; i < numvertices; i++) {
1406 ✗ v = &(vertices[i]);
1407 ✗ vprev = &(vertices[v->previous]);
1408 ✗ vnext = &(vertices[v->next]);
1409
1410 ✗ if (Below(vprev->p, v->p) && Below(vnext->p, v->p)) {
1411 ✗ if (IsConvex(vnext->p, vprev->p, v->p)) {
1412 ✗ vertextypes[i] = TPPL_VERTEXTYPE_START;
1413 } else {
1414 ✗ vertextypes[i] = TPPL_VERTEXTYPE_SPLIT;
1415 }
1416 ✗ } else if (Below(v->p, vprev->p) && Below(v->p, vnext->p)) {
1417 ✗ if (IsConvex(vnext->p, vprev->p, v->p)) {
1418 ✗ vertextypes[i] = TPPL_VERTEXTYPE_END;
1419 } else {
1420 ✗ vertextypes[i] = TPPL_VERTEXTYPE_MERGE;
1421 }
1422 } else {
1423 ✗ vertextypes[i] = TPPL_VERTEXTYPE_REGULAR;
1424 }
1425 }
1426
1427 //helpers
1428 ✗ long* helpers = new long[maxnumvertices];
1429
1430 //binary search tree that holds edges intersecting the scanline
1431 //note that while set doesn't actually have to be implemented as a tree
1432 //complexity requirements for operations are the same as for the balanced binary search tree
1433 ✗ set<ScanLineEdge> edgeTree;
1434 //store iterators to the edge tree elements
1435 //this makes deleting existing edges much faster
1436 set<ScanLineEdge>::iterator* edgeTreeIterators;
1437 ✗ set<ScanLineEdge>::iterator edgeIter;
1438 ✗ edgeTreeIterators = new set<ScanLineEdge>::iterator[maxnumvertices];
1439 ✗ pair<set<ScanLineEdge>::iterator, bool> edgeTreeRet;
1440 ✗ for (i = 0; i < numvertices; i++) {
1441 ✗ edgeTreeIterators[i] = edgeTree.end();
1442 }
1443
1444 //for each vertex
1445 ✗ for (i = 0; i < numvertices; i++) {
1446 ✗ vindex = priority[i];
1447 ✗ v = &(vertices[vindex]);
1448 ✗ vindex2 = vindex;
1449 ✗ v2 = v;
1450
1451 //depending on the vertex type, do the appropriate action
1452 //comments in the following sections are copied from "Computational Geometry: Algorithms and Applications"
1453 ✗ switch (vertextypes[vindex]) {
1454 ✗ case TPPL_VERTEXTYPE_START:
1455 //Insert ei in T and set helper(ei) to vi.
1456 ✗ newedge.p1 = v->p;
1457 ✗ newedge.p2 = vertices[v->next].p;
1458 ✗ newedge.index = vindex;
1459 ✗ edgeTreeRet = edgeTree.insert(newedge);
1460 ✗ edgeTreeIterators[vindex] = edgeTreeRet.first;
1461 ✗ helpers[vindex] = vindex;
1462 ✗ break;
1463
1464 ✗ case TPPL_VERTEXTYPE_END:
1465 ✗ if (edgeTreeIterators[v->previous] == edgeTree.end()) {
1466 ✗ error = true;
1467 ✗ break;
1468 }
1469 //if helper(ei-1) is a merge vertex
1470 ✗ if (vertextypes[helpers[v->previous]] == TPPL_VERTEXTYPE_MERGE) {
1471 //Insert the diagonal connecting vi to helper(ei-1) in D.
1472 ✗ AddDiagonal(vertices, &newnumvertices, vindex, helpers[v->previous], vertextypes, edgeTreeIterators, &edgeTree, helpers);
1473 }
1474 //Delete ei-1 from T
1475 ✗ edgeTree.erase(edgeTreeIterators[v->previous]);
1476 ✗ break;
1477
1478 ✗ case TPPL_VERTEXTYPE_SPLIT:
1479 //Search in T to find the edge e j directly left of vi.
1480 ✗ newedge.p1 = v->p;
1481 ✗ newedge.p2 = v->p;
1482 ✗ edgeIter = edgeTree.lower_bound(newedge);
1483 ✗ if (edgeIter == edgeTree.begin()) {
1484 ✗ error = true;
1485 ✗ break;
1486 }
1487 ✗ edgeIter--;
1488 //Insert the diagonal connecting vi to helper(ej) in D.
1489 ✗ AddDiagonal(vertices, &newnumvertices, vindex, helpers[edgeIter->index], vertextypes, edgeTreeIterators, &edgeTree, helpers);
1490 ✗ vindex2 = newnumvertices - 2;
1491 ✗ v2 = &(vertices[vindex2]);
1492 //helper(e j)�vi
1493 ✗ helpers[edgeIter->index] = vindex;
1494 //Insert ei in T and set helper(ei) to vi.
1495 ✗ newedge.p1 = v2->p;
1496 ✗ newedge.p2 = vertices[v2->next].p;
1497 ✗ newedge.index = vindex2;
1498 ✗ edgeTreeRet = edgeTree.insert(newedge);
1499 ✗ edgeTreeIterators[vindex2] = edgeTreeRet.first;
1500 ✗ helpers[vindex2] = vindex2;
1501 ✗ break;
1502
1503 ✗ case TPPL_VERTEXTYPE_MERGE:
1504 ✗ if (edgeTreeIterators[v->previous] == edgeTree.end()) {
1505 ✗ error = true;
1506 ✗ break;
1507 }
1508 //if helper(ei-1) is a merge vertex
1509 ✗ if (vertextypes[helpers[v->previous]] == TPPL_VERTEXTYPE_MERGE) {
1510 //Insert the diagonal connecting vi to helper(ei-1) in D.
1511 ✗ AddDiagonal(vertices, &newnumvertices, vindex, helpers[v->previous], vertextypes, edgeTreeIterators, &edgeTree, helpers);
1512 ✗ vindex2 = newnumvertices - 2;
1513 ✗ v2 = &(vertices[vindex2]);
1514 }
1515 //Delete ei-1 from T.
1516 ✗ edgeTree.erase(edgeTreeIterators[v->previous]);
1517 //Search in T to find the edge e j directly left of vi.
1518 ✗ newedge.p1 = v->p;
1519 ✗ newedge.p2 = v->p;
1520 ✗ edgeIter = edgeTree.lower_bound(newedge);
1521 ✗ if (edgeIter == edgeTree.begin()) {
1522 ✗ error = true;
1523 ✗ break;
1524 }
1525 ✗ edgeIter--;
1526 //if helper(ej) is a merge vertex
1527 ✗ if (vertextypes[helpers[edgeIter->index]] == TPPL_VERTEXTYPE_MERGE) {
1528 //Insert the diagonal connecting vi to helper(e j) in D.
1529 ✗ AddDiagonal(vertices, &newnumvertices, vindex2, helpers[edgeIter->index], vertextypes, edgeTreeIterators, &edgeTree, helpers);
1530 }
1531 //helper(e j)�vi
1532 ✗ helpers[edgeIter->index] = vindex2;
1533 ✗ break;
1534
1535 ✗ case TPPL_VERTEXTYPE_REGULAR:
1536 //if the interior of P lies to the right of vi
1537 ✗ if (Below(v->p, vertices[v->previous].p)) {
1538 ✗ if (edgeTreeIterators[v->previous] == edgeTree.end()) {
1539 ✗ error = true;
1540 ✗ break;
1541 }
1542 //if helper(ei-1) is a merge vertex
1543 ✗ if (vertextypes[helpers[v->previous]] == TPPL_VERTEXTYPE_MERGE) {
1544 //Insert the diagonal connecting vi to helper(ei-1) in D.
1545 ✗ AddDiagonal(vertices, &newnumvertices, vindex, helpers[v->previous], vertextypes, edgeTreeIterators, &edgeTree, helpers);
1546 ✗ vindex2 = newnumvertices - 2;
1547 ✗ v2 = &(vertices[vindex2]);
1548 }
1549 //Delete ei-1 from T.
1550 ✗ edgeTree.erase(edgeTreeIterators[v->previous]);
1551 //Insert ei in T and set helper(ei) to vi.
1552 ✗ newedge.p1 = v2->p;
1553 ✗ newedge.p2 = vertices[v2->next].p;
1554 ✗ newedge.index = vindex2;
1555 ✗ edgeTreeRet = edgeTree.insert(newedge);
1556 ✗ edgeTreeIterators[vindex2] = edgeTreeRet.first;
1557 ✗ helpers[vindex2] = vindex;
1558 } else {
1559 //Search in T to find the edge ej directly left of vi.
1560 ✗ newedge.p1 = v->p;
1561 ✗ newedge.p2 = v->p;
1562 ✗ edgeIter = edgeTree.lower_bound(newedge);
1563 ✗ if (edgeIter == edgeTree.begin()) {
1564 ✗ error = true;
1565 ✗ break;
1566 }
1567 ✗ edgeIter--;
1568 //if helper(ej) is a merge vertex
1569 ✗ if (vertextypes[helpers[edgeIter->index]] == TPPL_VERTEXTYPE_MERGE) {
1570 //Insert the diagonal connecting vi to helper(e j) in D.
1571 ✗ AddDiagonal(vertices, &newnumvertices, vindex, helpers[edgeIter->index], vertextypes, edgeTreeIterators, &edgeTree, helpers);
1572 }
1573 //helper(e j)�vi
1574 ✗ helpers[edgeIter->index] = vindex;
1575 }
1576 ✗ break;
1577 }
1578
1579 ✗ if (error) {
1580 ✗ break;
1581 }
1582 }
1583
1584 ✗ char* used = new char[newnumvertices];
1585 ✗ memset(used, 0, newnumvertices * sizeof(char));
1586
1587 ✗ if (!error) {
1588 //return result
1589 long size;
1590 ✗ TPPLPoly mpoly;
1591 ✗ for (i = 0; i < newnumvertices; i++) {
1592 ✗ if (used[i] != 0) {
1593 ✗ continue;
1594 }
1595 ✗ v = &(vertices[i]);
1596 ✗ vnext = &(vertices[v->next]);
1597 ✗ size = 1;
1598 ✗ while (vnext != v) {
1599 ✗ vnext = &(vertices[vnext->next]);
1600 ✗ size++;
1601 }
1602 ✗ mpoly.Init(size);
1603 ✗ v = &(vertices[i]);
1604 ✗ mpoly[0] = v->p;
1605 ✗ vnext = &(vertices[v->next]);
1606 ✗ size = 1;
1607 ✗ used[i] = 1;
1608 ✗ used[v->next] = 1;
1609 ✗ while (vnext != v) {
1610 ✗ mpoly[size] = vnext->p;
1611 ✗ used[vnext->next] = 1;
1612 ✗ vnext = &(vertices[vnext->next]);
1613 ✗ size++;
1614 }
1615 ✗ monotonePolys->push_back(mpoly);
1616 }
1617 ✗ }
1618
1619 //cleanup
1620 ✗ delete[] vertices;
1621 ✗ delete[] priority;
1622 ✗ delete[] vertextypes;
1623 ✗ delete[] edgeTreeIterators;
1624 ✗ delete[] helpers;
1625 ✗ delete[] used;
1626
1627 ✗ if (error) {
1628 ✗ return 0;
1629 } else {
1630 ✗ return 1;
1631 }
1632 ✗ }
1633
1634 //adds a diagonal to the doubly-connected list of vertices
1635 ✗ void TPPLPartition::AddDiagonal(MonotoneVertex* vertices, long* numvertices, long index1, long index2, char* vertextypes,
1636 set<ScanLineEdge>::iterator* edgeTreeIterators, set<ScanLineEdge>* edgeTree, long* helpers) {
1637 long newindex1;
1638 long newindex2;
1639
1640 ✗ newindex1 = *numvertices;
1641 ✗ (*numvertices)++;
1642 ✗ newindex2 = *numvertices;
1643 ✗ (*numvertices)++;
1644
1645 ✗ vertices[newindex1].p = vertices[index1].p;
1646 ✗ vertices[newindex2].p = vertices[index2].p;
1647
1648 ✗ vertices[newindex2].next = vertices[index2].next;
1649 ✗ vertices[newindex1].next = vertices[index1].next;
1650
1651 ✗ vertices[vertices[index2].next].previous = newindex2;
1652 ✗ vertices[vertices[index1].next].previous = newindex1;
1653
1654 ✗ vertices[index1].next = newindex2;
1655 ✗ vertices[newindex2].previous = index1;
1656
1657 ✗ vertices[index2].next = newindex1;
1658 ✗ vertices[newindex1].previous = index2;
1659
1660 //update all relevant structures
1661 ✗ vertextypes[newindex1] = vertextypes[index1];
1662 ✗ edgeTreeIterators[newindex1] = edgeTreeIterators[index1];
1663 ✗ helpers[newindex1] = helpers[index1];
1664 ✗ if (edgeTreeIterators[newindex1] != edgeTree->end()) {
1665 ✗ edgeTreeIterators[newindex1]->index = newindex1;
1666 }
1667 ✗ vertextypes[newindex2] = vertextypes[index2];
1668 ✗ edgeTreeIterators[newindex2] = edgeTreeIterators[index2];
1669 ✗ helpers[newindex2] = helpers[index2];
1670 ✗ if (edgeTreeIterators[newindex2] != edgeTree->end()) {
1671 ✗ edgeTreeIterators[newindex2]->index = newindex2;
1672 }
1673 ✗ }
1674
1675 ✗ bool TPPLPartition::Below(TPPLPoint& p1, TPPLPoint& p2) {
1676 ✗ if (p1.y < p2.y) {
1677 ✗ return true;
1678 ✗ } else if (p1.y == p2.y) {
1679 ✗ if (p1.x < p2.x) {
1680 ✗ return true;
1681 }
1682 }
1683 ✗ return false;
1684 }
1685
1686 //sorts in the falling order of y values, if y is equal, x is used instead
1687 ✗ bool TPPLPartition::VertexSorter::operator()(long index1, long index2) {
1688 ✗ if (vertices[index1].p.y > vertices[index2].p.y) {
1689 ✗ return true;
1690 ✗ } else if (vertices[index1].p.y == vertices[index2].p.y) {
1691 ✗ if (vertices[index1].p.x > vertices[index2].p.x) {
1692 ✗ return true;
1693 }
1694 }
1695 ✗ return false;
1696 }
1697
1698 ✗ bool TPPLPartition::ScanLineEdge::IsConvex(const TPPLPoint& p1, const TPPLPoint& p2, const TPPLPoint& p3) const {
1699 tppl_float tmp;
1700 ✗ tmp = (p3.y - p1.y) * (p2.x - p1.x) - (p3.x - p1.x) * (p2.y - p1.y);
1701 ✗ if (tmp > 0) {
1702 ✗ return true;
1703 } else {
1704 ✗ return false;
1705 }
1706 }
1707
1708 ✗ bool TPPLPartition::ScanLineEdge::operator<(const ScanLineEdge& other) const {
1709 ✗ if (other.p1.y == other.p2.y) {
1710 ✗ if (p1.y == p2.y) {
1711 ✗ if (p1.y < other.p1.y) {
1712 ✗ return true;
1713 } else {
1714 ✗ return false;
1715 }
1716 }
1717 ✗ if (IsConvex(p1, p2, other.p1)) {
1718 ✗ return true;
1719 } else {
1720 ✗ return false;
1721 }
1722 ✗ } else if (p1.y == p2.y) {
1723 ✗ if (IsConvex(other.p1, other.p2, p1)) {
1724 ✗ return false;
1725 } else {
1726 ✗ return true;
1727 }
1728 ✗ } else if (p1.y < other.p1.y) {
1729 ✗ if (IsConvex(other.p1, other.p2, p1)) {
1730 ✗ return false;
1731 } else {
1732 ✗ return true;
1733 }
1734 } else {
1735 ✗ if (IsConvex(p1, p2, other.p1)) {
1736 ✗ return true;
1737 } else {
1738 ✗ return false;
1739 }
1740 }
1741 }
1742
1743 //triangulates monotone polygon
1744 //O(n) time, O(n) space complexity
1745 ✗ int TPPLPartition::TriangulateMonotone(TPPLPoly* inPoly, TPPLPolyList* triangles) {
1746 ✗ if (!inPoly->Valid()) {
1747 ✗ return 0;
1748 }
1749
1750 long i;
1751 long i2;
1752 long j;
1753 long topindex;
1754 long bottomindex;
1755 long leftindex;
1756 long rightindex;
1757 long vindex;
1758 ✗ TPPLPoint* points = NULL;
1759 long numpoints;
1760 ✗ TPPLPoly triangle;
1761
1762 ✗ numpoints = inPoly->GetNumPoints();
1763 ✗ points = inPoly->GetPoints();
1764
1765 //trivial case
1766 ✗ if (numpoints == 3) {
1767 ✗ triangles->push_back(*inPoly);
1768 ✗ return 1;
1769 }
1770
1771 ✗ topindex = 0;
1772 ✗ bottomindex = 0;
1773 ✗ for (i = 1; i < numpoints; i++) {
1774 ✗ if (Below(points[i], points[bottomindex])) {
1775 ✗ bottomindex = i;
1776 }
1777 ✗ if (Below(points[topindex], points[i])) {
1778 ✗ topindex = i;
1779 }
1780 }
1781
1782 //check if the poly is really monotone
1783 ✗ i = topindex;
1784 ✗ while (i != bottomindex) {
1785 ✗ i2 = i + 1;
1786 ✗ if (i2 >= numpoints) {
1787 ✗ i2 = 0;
1788 }
1789 ✗ if (!Below(points[i2], points[i])) {
1790 ✗ return 0;
1791 }
1792 ✗ i = i2;
1793 }
1794 ✗ i = bottomindex;
1795 ✗ while (i != topindex) {
1796 ✗ i2 = i + 1;
1797 ✗ if (i2 >= numpoints) {
1798 ✗ i2 = 0;
1799 }
1800 ✗ if (!Below(points[i], points[i2])) {
1801 ✗ return 0;
1802 }
1803 ✗ i = i2;
1804 }
1805
1806 ✗ char* vertextypes = new char[numpoints];
1807 ✗ long* priority = new long[numpoints];
1808
1809 //merge left and right vertex chains
1810 ✗ priority[0] = topindex;
1811 ✗ vertextypes[topindex] = 0;
1812 ✗ leftindex = topindex + 1;
1813 ✗ if (leftindex >= numpoints) {
1814 ✗ leftindex = 0;
1815 }
1816 ✗ rightindex = topindex - 1;
1817 ✗ if (rightindex < 0) {
1818 ✗ rightindex = numpoints - 1;
1819 }
1820 ✗ for (i = 1; i < (numpoints - 1); i++) {
1821 ✗ if (leftindex == bottomindex) {
1822 ✗ priority[i] = rightindex;
1823 ✗ rightindex--;
1824 ✗ if (rightindex < 0) {
1825 ✗ rightindex = numpoints - 1;
1826 }
1827 ✗ vertextypes[priority[i]] = -1;
1828 ✗ } else if (rightindex == bottomindex) {
1829 ✗ priority[i] = leftindex;
1830 ✗ leftindex++;
1831 ✗ if (leftindex >= numpoints) {
1832 ✗ leftindex = 0;
1833 }
1834 ✗ vertextypes[priority[i]] = 1;
1835 } else {
1836 ✗ if (Below(points[leftindex], points[rightindex])) {
1837 ✗ priority[i] = rightindex;
1838 ✗ rightindex--;
1839 ✗ if (rightindex < 0) {
1840 ✗ rightindex = numpoints - 1;
1841 }
1842 ✗ vertextypes[priority[i]] = -1;
1843 } else {
1844 ✗ priority[i] = leftindex;
1845 ✗ leftindex++;
1846 ✗ if (leftindex >= numpoints) {
1847 ✗ leftindex = 0;
1848 }
1849 ✗ vertextypes[priority[i]] = 1;
1850 }
1851 }
1852 }
1853 ✗ priority[i] = bottomindex;
1854 ✗ vertextypes[bottomindex] = 0;
1855
1856 ✗ long* stack = new long[numpoints];
1857 ✗ long stackptr = 0;
1858
1859 ✗ stack[0] = priority[0];
1860 ✗ stack[1] = priority[1];
1861 ✗ stackptr = 2;
1862
1863 //for each vertex from top to bottom trim as many triangles as possible
1864 ✗ for (i = 2; i < (numpoints - 1); i++) {
1865 ✗ vindex = priority[i];
1866 ✗ if (vertextypes[vindex] != vertextypes[stack[stackptr - 1]]) {
1867 ✗ for (j = 0; j < (stackptr - 1); j++) {
1868 ✗ if (vertextypes[vindex] == 1) {
1869 ✗ triangle.Triangle(points[stack[j + 1]], points[stack[j]], points[vindex]);
1870 } else {
1871 ✗ triangle.Triangle(points[stack[j]], points[stack[j + 1]], points[vindex]);
1872 }
1873 ✗ triangles->push_back(triangle);
1874 }
1875 ✗ stack[0] = priority[i - 1];
1876 ✗ stack[1] = priority[i];
1877 ✗ stackptr = 2;
1878 } else {
1879 ✗ stackptr--;
1880 ✗ while (stackptr > 0) {
1881 ✗ if (vertextypes[vindex] == 1) {
1882 ✗ if (IsConvex(points[vindex], points[stack[stackptr - 1]], points[stack[stackptr]])) {
1883 ✗ triangle.Triangle(points[vindex], points[stack[stackptr - 1]], points[stack[stackptr]]);
1884 ✗ triangles->push_back(triangle);
1885 ✗ stackptr--;
1886 } else {
1887 ✗ break;
1888 }
1889 } else {
1890 ✗ if (IsConvex(points[vindex], points[stack[stackptr]], points[stack[stackptr - 1]])) {
1891 ✗ triangle.Triangle(points[vindex], points[stack[stackptr]], points[stack[stackptr - 1]]);
1892 ✗ triangles->push_back(triangle);
1893 ✗ stackptr--;
1894 } else {
1895 ✗ break;
1896 }
1897 }
1898 }
1899 ✗ stackptr++;
1900 ✗ stack[stackptr] = vindex;
1901 ✗ stackptr++;
1902 }
1903 }
1904 ✗ vindex = priority[i];
1905 ✗ for (j = 0; j < (stackptr - 1); j++) {
1906 ✗ if (vertextypes[stack[j + 1]] == 1) {
1907 ✗ triangle.Triangle(points[stack[j]], points[stack[j + 1]], points[vindex]);
1908 } else {
1909 ✗ triangle.Triangle(points[stack[j + 1]], points[stack[j]], points[vindex]);
1910 }
1911 ✗ triangles->push_back(triangle);
1912 }
1913
1914 ✗ delete[] priority;
1915 ✗ delete[] vertextypes;
1916 ✗ delete[] stack;
1917
1918 ✗ return 1;
1919 ✗ }
1920
1921 ✗ int TPPLPartition::Triangulate_MONO(TPPLPolyList* inpolys, TPPLPolyList* triangles) {
1922 ✗ TPPLPolyList monotone;
1923 ✗ TPPLPolyList::iterator iter;
1924
1925 ✗ if (MonotonePartition(inpolys, &monotone) == 0) {
1926 ✗ return 0;
1927 }
1928 ✗ for (iter = monotone.begin(); iter != monotone.end(); iter++) {
1929 ✗ if (TriangulateMonotone(&(*iter), triangles) == 0) {
1930 ✗ return 0;
1931 }
1932 }
1933 ✗ return 1;
1934 ✗ }
1935
1936 ✗ int TPPLPartition::Triangulate_MONO(TPPLPoly* poly, TPPLPolyList* triangles) {
1937 ✗ TPPLPolyList polys;
1938 ✗ polys.push_back(*poly);
1939
1940 ✗ return Triangulate_MONO(&polys, triangles);
1941 ✗ }
1942