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