?  search:
summary | log | graphiclog1 | graphiclog2 | commit | commitdiff | tree | refs | edit | fork
blame | history | raw | HEAD
Update ooo320-m1
[ooovba.git] / basegfx / source / polygon / b2dpolypolygoncutter.cxx
blob83e92edd75bed24d2bc39149cceeb43c14466d38
1 /*************************************************************************
2 *
3 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
4 *
5 * Copyright 2008 by Sun Microsystems, Inc.
6 *
7 * OpenOffice.org - a multi-platform office productivity suite
8 *
9 * $RCSfile: b2dpolypolygoncutter.cxx,v $
10 * $Revision: 1.17 $
11 *
12 * This file is part of OpenOffice.org.
13 *
14 * OpenOffice.org is free software: you can redistribute it and/or modify
15 * it under the terms of the GNU Lesser General Public License version 3
16 * only, as published by the Free Software Foundation.
17 *
18 * OpenOffice.org is distributed in the hope that it will be useful,
19 * but WITHOUT ANY WARRANTY; without even the implied warranty of
20 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
21 * GNU Lesser General Public License version 3 for more details
22 * (a copy is included in the LICENSE file that accompanied this code).
23 *
24 * You should have received a copy of the GNU Lesser General Public License
25 * version 3 along with OpenOffice.org. If not, see
26 * <http://www.openoffice.org/license.html>
27 * for a copy of the LGPLv3 License.
28 *
29 ************************************************************************/
30
31 // MARKER(update_precomp.py): autogen include statement, do not remove
32 #include "precompiled_basegfx.hxx"
33 #include <osl/diagnose.h>
34 #include <basegfx/numeric/ftools.hxx>
35 #include <basegfx/polygon/b2dpolypolygoncutter.hxx>
36 #include <basegfx/point/b2dpoint.hxx>
37 #include <basegfx/vector/b2dvector.hxx>
38 #include <basegfx/polygon/b2dpolygon.hxx>
39 #include <basegfx/polygon/b2dpolygontools.hxx>
40 #include <basegfx/polygon/b2dpolygoncutandtouch.hxx>
41 #include <basegfx/range/b2drange.hxx>
42 #include <basegfx/polygon/b2dpolypolygontools.hxx>
43 #include <basegfx/curve/b2dcubicbezier.hxx>
44 #include <vector>
45 #include <algorithm>
46
47 //////////////////////////////////////////////////////////////////////////////
48
49 namespace basegfx
50 {
51 namespace
52 {
53 //////////////////////////////////////////////////////////////////////////////
54
55 struct StripHelper
56 {
57 B2DRange maRange;
58 sal_Int32 mnDepth;
59 B2VectorOrientation meOrinetation;
60 };
61
62 //////////////////////////////////////////////////////////////////////////////
63
64 struct PN
65 {
66 public:
67 B2DPoint maPoint;
68 sal_uInt32 mnI;
69 sal_uInt32 mnIP;
70 sal_uInt32 mnIN;
71 };
72
73 //////////////////////////////////////////////////////////////////////////////
74
75 struct VN
76 {
77 public:
78 B2DVector maPrev;
79 B2DVector maNext;
80
81 // to have the correct curve segments in the crossover checks,
82 // it is necessary to keep the original next vectors, too. Else,
83 // it may happen to use a already switched next vector which
84 // would interpolate the wrong comparison point
85 B2DVector maOriginalNext;
86 };
87
88 //////////////////////////////////////////////////////////////////////////////
89
90 struct SN
91 {
92 public:
93 PN* mpPN;
94
95 bool operator<(const SN& rComp) const
96 {
97 if(fTools::equal(mpPN->maPoint.getX(), rComp.mpPN->maPoint.getX()))
98 {
99 if(fTools::equal(mpPN->maPoint.getY(), rComp.mpPN->maPoint.getY()))
100 {
101 return (mpPN->mnI < rComp.mpPN->mnI);
102 }
103 else
104 {
105 return fTools::less(mpPN->maPoint.getY(), rComp.mpPN->maPoint.getY());
106 }
107 }
108 else
109 {
110 return fTools::less(mpPN->maPoint.getX(), rComp.mpPN->maPoint.getX());
111 }
112 }
113 };
114
115 //////////////////////////////////////////////////////////////////////////////
116
117 typedef ::std::vector< PN > PNV;
118 typedef ::std::vector< VN > VNV;
119 typedef ::std::vector< SN > SNV;
120
121 //////////////////////////////////////////////////////////////////////////////
122
123 class solver
124 {
125 private:
126 const B2DPolyPolygon maOriginal;
127 PNV maPNV;
128 VNV maVNV;
129 SNV maSNV;
130
131 unsigned mbIsCurve : 1;
132 unsigned mbChanged : 1;
133
134 void impAddPolygon(const sal_uInt32 aPos, const B2DPolygon& rGeometry)
135 {
136 const sal_uInt32 nCount(rGeometry.count());
137 PN aNewPN;
138 VN aNewVN;
139 SN aNewSN;
140
141 for(sal_uInt32 a(0); a < nCount; a++)
142 {
143 const B2DPoint aPoint(rGeometry.getB2DPoint(a));
144 aNewPN.maPoint = aPoint;
145 aNewPN.mnI = aPos + a;
146 aNewPN.mnIP = aPos + ((a != 0) ? a - 1 : nCount - 1);
147 aNewPN.mnIN = aPos + ((a + 1 == nCount) ? 0 : a + 1);
148 maPNV.push_back(aNewPN);
149
150 if(mbIsCurve)
151 {
152 aNewVN.maPrev = rGeometry.getPrevControlPoint(a) - aPoint;
153 aNewVN.maNext = rGeometry.getNextControlPoint(a) - aPoint;
154 aNewVN.maOriginalNext = aNewVN.maNext;
155 maVNV.push_back(aNewVN);
156 }
157
158 aNewSN.mpPN = &maPNV[maPNV.size() - 1];
159 maSNV.push_back(aNewSN);
160 }
161 }
162
163 bool impLeftOfEdges(const B2DVector& rVecA, const B2DVector& rVecB, const B2DVector& rTest)
164 {
165 // tests if rTest is left of both directed line segments along the line -rVecA, rVecB. Test is
166 // with border.
167 if(rVecA.cross(rVecB) > 0.0)
168 {
169 // b is left turn seen from a, test if Test is left of both and so inside (left is seeen as inside)
170 const bool bBoolA(fTools::moreOrEqual(rVecA.cross(rTest), 0.0));
171 const bool bBoolB(fTools::lessOrEqual(rVecB.cross(rTest), 0.0));
172
173 return (bBoolA && bBoolB);
174 }
175 else
176 {
177 // b is right turn seen from a, test if Test is right of both and so outside (left is seeen as inside)
178 const bool bBoolA(fTools::lessOrEqual(rVecA.cross(rTest), 0.0));
179 const bool bBoolB(fTools::moreOrEqual(rVecB.cross(rTest), 0.0));
180
181 return (!(bBoolA && bBoolB));
182 }
183 }
184
185 void impSwitchNext(PN& rPNa, PN& rPNb)
186 {
187 ::std::swap(rPNa.mnIN, rPNb.mnIN);
188
189 if(mbIsCurve)
190 {
191 VN& rVNa = maVNV[rPNa.mnI];
192 VN& rVNb = maVNV[rPNb.mnI];
193
194 ::std::swap(rVNa.maNext, rVNb.maNext);
195 }
196
197 if(!mbChanged)
198 {
199 mbChanged = true;
200 }
201 }
202
203 B2DCubicBezier createSegment(const PN& rPN, bool bPrev) const
204 {
205 const B2DPoint& rStart(rPN.maPoint);
206 const B2DPoint& rEnd(maPNV[bPrev ? rPN.mnIP : rPN.mnIN].maPoint);
207 const B2DVector& rCPA(bPrev ? maVNV[rPN.mnI].maPrev : maVNV[rPN.mnI].maNext);
208 // Use maOriginalNext, not maNext to create the original (yet unchanged)
209 // curve segment. Otherwise, this segment would NOT ne correct.
210 const B2DVector& rCPB(bPrev ? maVNV[maPNV[rPN.mnIP].mnI].maOriginalNext : maVNV[maPNV[rPN.mnIN].mnI].maPrev);
211
212 return B2DCubicBezier(rStart, rStart + rCPA, rEnd + rCPB, rEnd);
213 }
214
215 void impHandleCommon(PN& rPNa, PN& rPNb)
216 {
217 if(mbIsCurve)
218 {
219 const B2DCubicBezier aNextA(createSegment(rPNa, false));
220 const B2DCubicBezier aPrevA(createSegment(rPNa, true));
221
222 if(aNextA.equal(aPrevA))
223 {
224 // deadend on A (identical edge)
225 return;
226 }
227
228 const B2DCubicBezier aNextB(createSegment(rPNb, false));
229 const B2DCubicBezier aPrevB(createSegment(rPNb, true));
230
231 if(aNextB.equal(aPrevB))
232 {
233 // deadend on B (identical edge)
234 return;
235 }
236
237 if(aPrevA.equal(aPrevB))
238 {
239 // common edge in same direction
240 if(aNextA.equal(aNextB))
241 {
242 // common edge in same direction continues
243 return;
244 }
245 else
246 {
247 // common edge in same direction leave
248 // action is done on enter
249 return;
250 }
251 }
252 else if(aPrevA.equal(aNextB))
253 {
254 // common edge in opposite direction
255 if(aNextA.equal(aPrevB))
256 {
257 // common edge in opposite direction continues
258 return;
259 }
260 else
261 {
262 // common edge in opposite direction leave
263 impSwitchNext(rPNa, rPNb);
264 }
265 }
266 else if(aNextA.equal(aNextB))
267 {
268 // common edge in same direction enter
269 // search leave edge
270 PN* pPNa2 = &maPNV[rPNa.mnIN];
271 PN* pPNb2 = &maPNV[rPNb.mnIN];
272 bool bOnEdge(true);
273
274 do
275 {
276 const B2DCubicBezier aNextA2(createSegment(*pPNa2, false));
277 const B2DCubicBezier aNextB2(createSegment(*pPNb2, false));
278
279 if(aNextA2.equal(aNextB2))
280 {
281 pPNa2 = &maPNV[pPNa2->mnIN];
282 pPNb2 = &maPNV[pPNb2->mnIN];
283 }
284 else
285 {
286 bOnEdge = false;
287 }
288 }
289 while(bOnEdge && pPNa2 != &rPNa && pPNa2 != &rPNa);
290
291 if(bOnEdge)
292 {
293 // loop over two identical polygon paths
294 return;
295 }
296 else
297 {
298 // enter at rPNa, rPNb; leave at pPNa2, pPNb2. No common edges
299 // at enter/leave. Check for crossover.
300 const B2DVector aPrevCA(aPrevA.interpolatePoint(0.5) - aPrevA.getStartPoint());
301 const B2DVector aNextCA(aNextA.interpolatePoint(0.5) - aNextA.getStartPoint());
302 const B2DVector aPrevCB(aPrevB.interpolatePoint(0.5) - aPrevB.getStartPoint());
303 const bool bEnter(impLeftOfEdges(aPrevCA, aNextCA, aPrevCB));
304
305 const B2DCubicBezier aNextA2(createSegment(*pPNa2, false));
306 const B2DCubicBezier aPrevA2(createSegment(*pPNa2, true));
307 const B2DCubicBezier aNextB2(createSegment(*pPNb2, false));
308 const B2DVector aPrevCA2(aPrevA2.interpolatePoint(0.5) - aPrevA2.getStartPoint());
309 const B2DVector aNextCA2(aNextA2.interpolatePoint(0.5) - aNextA2.getStartPoint());
310 const B2DVector aNextCB2(aNextB2.interpolatePoint(0.5) - aNextB2.getStartPoint());
311 const bool bLeave(impLeftOfEdges(aPrevCA2, aNextCA2, aNextCB2));
312
313 if(bEnter != bLeave)
314 {
315 // crossover
316 impSwitchNext(rPNa, rPNb);
317 }
318 }
319 }
320 else if(aNextA.equal(aPrevB))
321 {
322 // common edge in opposite direction enter
323 impSwitchNext(rPNa, rPNb);
324 }
325 else
326 {
327 // no common edges, check for crossover
328 const B2DVector aPrevCA(aPrevA.interpolatePoint(0.5) - aPrevA.getStartPoint());
329 const B2DVector aNextCA(aNextA.interpolatePoint(0.5) - aNextA.getStartPoint());
330 const B2DVector aPrevCB(aPrevB.interpolatePoint(0.5) - aPrevB.getStartPoint());
331 const B2DVector aNextCB(aNextB.interpolatePoint(0.5) - aNextB.getStartPoint());
332
333 const bool bEnter(impLeftOfEdges(aPrevCA, aNextCA, aPrevCB));
334 const bool bLeave(impLeftOfEdges(aPrevCA, aNextCA, aNextCB));
335
336 if(bEnter != bLeave)
337 {
338 // crossover
339 impSwitchNext(rPNa, rPNb);
340 }
341 }
342 }
343 else
344 {
345 const B2DPoint& rNextA(maPNV[rPNa.mnIN].maPoint);
346 const B2DPoint& rPrevA(maPNV[rPNa.mnIP].maPoint);
347
348 if(rNextA.equal(rPrevA))
349 {
350 // deadend on A
351 return;
352 }
353
354 const B2DPoint& rNextB(maPNV[rPNb.mnIN].maPoint);
355 const B2DPoint& rPrevB(maPNV[rPNb.mnIP].maPoint);
356
357 if(rNextB.equal(rPrevB))
358 {
359 // deadend on B
360 return;
361 }
362
363 if(rPrevA.equal(rPrevB))
364 {
365 // common edge in same direction
366 if(rNextA.equal(rNextB))
367 {
368 // common edge in same direction continues
369 return;
370 }
371 else
372 {
373 // common edge in same direction leave
374 // action is done on enter
375 return;
376 }
377 }
378 else if(rPrevA.equal(rNextB))
379 {
380 // common edge in opposite direction
381 if(rNextA.equal(rPrevB))
382 {
383 // common edge in opposite direction continues
384 return;
385 }
386 else
387 {
388 // common edge in opposite direction leave
389 impSwitchNext(rPNa, rPNb);
390 }
391 }
392 else if(rNextA.equal(rNextB))
393 {
394 // common edge in same direction enter
395 // search leave edge
396 PN* pPNa2 = &maPNV[rPNa.mnIN];
397 PN* pPNb2 = &maPNV[rPNb.mnIN];
398 bool bOnEdge(true);
399
400 do
401 {
402 const B2DPoint& rNextA2(maPNV[pPNa2->mnIN].maPoint);
403 const B2DPoint& rNextB2(maPNV[pPNb2->mnIN].maPoint);
404
405 if(rNextA2.equal(rNextB2))
406 {
407 pPNa2 = &maPNV[pPNa2->mnIN];
408 pPNb2 = &maPNV[pPNb2->mnIN];
409 }
410 else
411 {
412 bOnEdge = false;
413 }
414 }
415 while(bOnEdge && pPNa2 != &rPNa && pPNa2 != &rPNa);
416
417 if(bOnEdge)
418 {
419 // loop over two identical polygon paths
420 return;
421 }
422 else
423 {
424 // enter at rPNa, rPNb; leave at pPNa2, pPNb2. No common edges
425 // at enter/leave. Check for crossover.
426 const B2DPoint& aPointE(rPNa.maPoint);
427 const B2DVector aPrevAE(rPrevA - aPointE);
428 const B2DVector aNextAE(rNextA - aPointE);
429 const B2DVector aPrevBE(rPrevB - aPointE);
430
431 const B2DPoint& aPointL(pPNa2->maPoint);
432 const B2DVector aPrevAL(maPNV[pPNa2->mnIP].maPoint - aPointL);
433 const B2DVector aNextAL(maPNV[pPNa2->mnIN].maPoint - aPointL);
434 const B2DVector aNextBL(maPNV[pPNb2->mnIN].maPoint - aPointL);
435
436 const bool bEnter(impLeftOfEdges(aPrevAE, aNextAE, aPrevBE));
437 const bool bLeave(impLeftOfEdges(aPrevAL, aNextAL, aNextBL));
438
439 if(bEnter != bLeave)
440 {
441 // crossover; switch start or end
442 impSwitchNext(rPNa, rPNb);
443 }
444 }
445 }
446 else if(rNextA.equal(rPrevB))
447 {
448 // common edge in opposite direction enter
449 impSwitchNext(rPNa, rPNb);
450 }
451 else
452 {
453 // no common edges, check for crossover
454 const B2DPoint& aPoint(rPNa.maPoint);
455 const B2DVector aPrevA(rPrevA - aPoint);
456 const B2DVector aNextA(rNextA - aPoint);
457 const B2DVector aPrevB(rPrevB - aPoint);
458 const B2DVector aNextB(rNextB - aPoint);
459
460 const bool bEnter(impLeftOfEdges(aPrevA, aNextA, aPrevB));
461 const bool bLeave(impLeftOfEdges(aPrevA, aNextA, aNextB));
462
463 if(bEnter != bLeave)
464 {
465 // crossover
466 impSwitchNext(rPNa, rPNb);
467 }
468 }
469 }
470 }
471
472 void impSolve()
473 {
474 // sort by point to identify common nodes
475 ::std::sort(maSNV.begin(), maSNV.end());
476
477 // handle common nodes
478 const sal_uInt32 nNodeCount(maSNV.size());
479
480 for(sal_uInt32 a(0); a < nNodeCount - 1; a++)
481 {
482 // test a before using it, not after. Also use nPointCount instead of aSortNodes.size()
483 PN& rPNb = *(maSNV[a].mpPN);
484
485 for(sal_uInt32 b(a + 1); b < nNodeCount && rPNb.maPoint.equal(maSNV[b].mpPN->maPoint); b++)
486 {
487 impHandleCommon(rPNb, *maSNV[b].mpPN);
488 }
489 }
490 }
491
492 public:
493 solver(const B2DPolygon& rOriginal)
494 : maOriginal(B2DPolyPolygon(rOriginal)),
495 mbIsCurve(false),
496 mbChanged(false)
497 {
498 const sal_uInt32 nOriginalCount(rOriginal.count());
499
500 if(nOriginalCount)
501 {
502 B2DPolygon aGeometry(tools::addPointsAtCutsAndTouches(rOriginal));
503 aGeometry.removeDoublePoints();
504 aGeometry = tools::simplifyCurveSegments(aGeometry);
505 mbIsCurve = aGeometry.areControlPointsUsed();
506
507 const sal_uInt32 nPointCount(aGeometry.count());
508
509 // If it's not a pezier polygon, at least four points are needed to create
510 // a self-intersection. If it's a bezier polygon, the minimum point number
511 // is two, since with a single point You get a curve, but no self-intersection
512 if(nPointCount > 3 || (nPointCount > 1 && mbIsCurve))
513 {
514 // reserve space in point, control and sort vector.
515 maSNV.reserve(nPointCount);
516 maPNV.reserve(nPointCount);
517 maVNV.reserve(mbIsCurve ? nPointCount : 0);
518
519 // fill data
520 impAddPolygon(0, aGeometry);
521
522 // solve common nodes
523 impSolve();
524 }
525 }
526 }
527
528 solver(const B2DPolyPolygon& rOriginal)
529 : maOriginal(rOriginal),
530 mbIsCurve(false),
531 mbChanged(false)
532 {
533 sal_uInt32 nOriginalCount(maOriginal.count());
534
535 if(nOriginalCount)
536 {
537 B2DPolyPolygon aGeometry(tools::addPointsAtCutsAndTouches(maOriginal, true));
538 aGeometry.removeDoublePoints();
539 aGeometry = tools::simplifyCurveSegments(aGeometry);
540 mbIsCurve = aGeometry.areControlPointsUsed();
541 nOriginalCount = aGeometry.count();
542
543 if(nOriginalCount)
544 {
545 sal_uInt32 nPointCount(0);
546 sal_uInt32 a(0);
547
548 // count points
549 for(a = 0; a < nOriginalCount; a++)
550 {
551 const B2DPolygon aCandidate(aGeometry.getB2DPolygon(a));
552 const sal_uInt32 nCandCount(aCandidate.count());
553
554 // If it's not a bezier curve, at least three points would be needed to have a
555 // topological relevant (not empty) polygon. Since its not known here if trivial
556 // edges (dead ends) will be kept or sorted out, add non-bezier polygons with
557 // more than one point.
558 // For bezier curves, the minimum for defining an area is also one.
559 if(nCandCount)
560 {
561 nPointCount += nCandCount;
562 }
563 }
564
565 if(nPointCount)
566 {
567 // reserve space in point, control and sort vector.
568 maSNV.reserve(nPointCount);
569 maPNV.reserve(nPointCount);
570 maVNV.reserve(mbIsCurve ? nPointCount : 0);
571
572 // fill data
573 sal_uInt32 nInsertIndex(0);
574
575 for(a = 0; a < nOriginalCount; a++)
576 {
577 const B2DPolygon aCandidate(aGeometry.getB2DPolygon(a));
578 const sal_uInt32 nCandCount(aCandidate.count());
579
580 // use same condition as above, the data vector is
581 // pre-allocated
582 if(nCandCount)
583 {
584 impAddPolygon(nInsertIndex, aCandidate);
585 nInsertIndex += nCandCount;
586 }
587 }
588
589 // solve common nodes
590 impSolve();
591 }
592 }
593 }
594 }
595
596 B2DPolyPolygon getB2DPolyPolygon()
597 {
598 if(mbChanged)
599 {
600 B2DPolyPolygon aRetval;
601 const sal_uInt32 nCount(maPNV.size());
602 sal_uInt32 nCountdown(nCount);
603
604 for(sal_uInt32 a(0); nCountdown && a < nCount; a++)
605 {
606 PN& rPN = maPNV[a];
607
608 if(SAL_MAX_UINT32 != rPN.mnI)
609 {
610 // unused node, start new part polygon
611 B2DPolygon aNewPart;
612 PN* pPNCurr = &rPN;
613
614 do
615 {
616 const B2DPoint& rPoint = pPNCurr->maPoint;
617 aNewPart.append(rPoint);
618
619 if(mbIsCurve)
620 {
621 const VN& rVNCurr = maVNV[pPNCurr->mnI];
622
623 if(!rVNCurr.maPrev.equalZero())
624 {
625 aNewPart.setPrevControlPoint(aNewPart.count() - 1, rPoint + rVNCurr.maPrev);
626 }
627
628 if(!rVNCurr.maNext.equalZero())
629 {
630 aNewPart.setNextControlPoint(aNewPart.count() - 1, rPoint + rVNCurr.maNext);
631 }
632 }
633
634 pPNCurr->mnI = SAL_MAX_UINT32;
635 nCountdown--;
636 pPNCurr = &(maPNV[pPNCurr->mnIN]);
637 }
638 while(pPNCurr != &rPN && SAL_MAX_UINT32 != pPNCurr->mnI);
639
640 // close and add
641 aNewPart.setClosed(true);
642 aRetval.append(aNewPart);
643 }
644 }
645
646 return aRetval;
647 }
648 else
649 {
650 // no change, return original
651 return maOriginal;
652 }
653 }
654 };
655
656 //////////////////////////////////////////////////////////////////////////////
657
658 } // end of anonymous namespace
659 } // end of namespace basegfx
660
661 //////////////////////////////////////////////////////////////////////////////
662
663 namespace basegfx
664 {
665 namespace tools
666 {
667 //////////////////////////////////////////////////////////////////////////////
668
669 B2DPolyPolygon solveCrossovers(const B2DPolyPolygon& rCandidate)
670 {
671 if(rCandidate.count() > 1L)
672 {
673 solver aSolver(rCandidate);
674 return aSolver.getB2DPolyPolygon();
675 }
676 else
677 {
678 return rCandidate;
679 }
680 }
681
682 //////////////////////////////////////////////////////////////////////////////
683
684 B2DPolyPolygon solveCrossovers(const B2DPolygon& rCandidate)
685 {
686 solver aSolver(rCandidate);
687 return aSolver.getB2DPolyPolygon();
688 }
689
690 //////////////////////////////////////////////////////////////////////////////
691
692 B2DPolyPolygon stripNeutralPolygons(const B2DPolyPolygon& rCandidate)
693 {
694 B2DPolyPolygon aRetval;
695
696 for(sal_uInt32 a(0L); a < rCandidate.count(); a++)
697 {
698 const B2DPolygon aCandidate(rCandidate.getB2DPolygon(a));
699
700 if(ORIENTATION_NEUTRAL != tools::getOrientation(aCandidate))
701 {
702 aRetval.append(aCandidate);
703 }
704 }
705
706 return aRetval;
707 }
708
709 //////////////////////////////////////////////////////////////////////////////
710
711 B2DPolyPolygon stripDispensablePolygons(const B2DPolyPolygon& rCandidate, bool bKeepAboveZero)
712 {
713 const sal_uInt32 nCount(rCandidate.count());
714 B2DPolyPolygon aRetval;
715
716 if(nCount)
717 {
718 if(nCount == 1L)
719 {
720 if(!bKeepAboveZero && ORIENTATION_POSITIVE == tools::getOrientation(rCandidate.getB2DPolygon(0L)))
721 {
722 aRetval = rCandidate;
723 }
724 }
725 else
726 {
727 sal_uInt32 a, b;
728 ::std::vector< StripHelper > aHelpers;
729 aHelpers.resize(nCount);
730
731 for(a = 0L; a < nCount; a++)
732 {
733 const B2DPolygon aCandidate(rCandidate.getB2DPolygon(a));
734 StripHelper* pNewHelper = &(aHelpers[a]);
735 pNewHelper->maRange = tools::getRange(aCandidate);
736 pNewHelper->meOrinetation = tools::getOrientation(aCandidate);
737 pNewHelper->mnDepth = (ORIENTATION_NEGATIVE == pNewHelper->meOrinetation ? -1L : 0L);
738 }
739
740 for(a = 0L; a < nCount - 1L; a++)
741 {
742 const B2DPolygon aCandA(rCandidate.getB2DPolygon(a));
743 StripHelper& rHelperA = aHelpers[a];
744
745 for(b = a + 1L; b < nCount; b++)
746 {
747 const B2DPolygon aCandB(rCandidate.getB2DPolygon(b));
748 StripHelper& rHelperB = aHelpers[b];
749 const bool bAInB(rHelperB.maRange.isInside(rHelperA.maRange) && tools::isInside(aCandB, aCandA, true));
750 const bool bBInA(rHelperA.maRange.isInside(rHelperB.maRange) && tools::isInside(aCandA, aCandB, true));
751
752 if(bAInB && bBInA)
753 {
754 // congruent
755 if(rHelperA.meOrinetation == rHelperB.meOrinetation)
756 {
757 // two polys or two holes. Lower one of them to get one of them out of the way.
758 // Since each will be contained in the other one, both will be increased, too.
759 // So, for lowering, increase only one of them
760 rHelperA.mnDepth++;
761 }
762 else
763 {
764 // poly and hole. They neutralize, so get rid of both. Move securely below zero.
765 rHelperA.mnDepth = -((sal_Int32)nCount);
766 rHelperB.mnDepth = -((sal_Int32)nCount);
767 }
768 }
769 else
770 {
771 if(bAInB)
772 {
773 if(ORIENTATION_NEGATIVE == rHelperB.meOrinetation)
774 {
775 rHelperA.mnDepth--;
776 }
777 else
778 {
779 rHelperA.mnDepth++;
780 }
781 }
782 else if(bBInA)
783 {
784 if(ORIENTATION_NEGATIVE == rHelperA.meOrinetation)
785 {
786 rHelperB.mnDepth--;
787 }
788 else
789 {
790 rHelperB.mnDepth++;
791 }
792 }
793 }
794 }
795 }
796
797 for(a = 0L; a < nCount; a++)
798 {
799 const StripHelper& rHelper = aHelpers[a];
800 bool bAcceptEntry(bKeepAboveZero ? 1L <= rHelper.mnDepth : 0L == rHelper.mnDepth);
801
802 if(bAcceptEntry)
803 {
804 aRetval.append(rCandidate.getB2DPolygon(a));
805 }
806 }
807 }
808 }
809
810 return aRetval;
811 }
812
813 //////////////////////////////////////////////////////////////////////////////
814
815 B2DPolyPolygon prepareForPolygonOperation(const B2DPolygon& rCandidate)
816 {
817 solver aSolver(rCandidate);
818 B2DPolyPolygon aRetval(stripNeutralPolygons(aSolver.getB2DPolyPolygon()));
819
820 return correctOrientations(aRetval);
821 }
822
823 B2DPolyPolygon prepareForPolygonOperation(const B2DPolyPolygon& rCandidate)
824 {
825 solver aSolver(rCandidate);
826 B2DPolyPolygon aRetval(stripNeutralPolygons(aSolver.getB2DPolyPolygon()));
827
828 return correctOrientations(aRetval);
829 }
830
831 B2DPolyPolygon solvePolygonOperationOr(const B2DPolyPolygon& rCandidateA, const B2DPolyPolygon& rCandidateB)
832 {
833 if(!rCandidateA.count())
834 {
835 return rCandidateB;
836 }
837 else if(!rCandidateB.count())
838 {
839 return rCandidateA;
840 }
841 else
842 {
843 // concatenate polygons, solve crossovers and throw away all sub-polygons
844 // which have a depth other than 0.
845 B2DPolyPolygon aRetval(rCandidateA);
846
847 aRetval.append(rCandidateB);
848 aRetval = solveCrossovers(aRetval);
849 aRetval = stripNeutralPolygons(aRetval);
850
851 return stripDispensablePolygons(aRetval, false);
852 }
853 }
854
855 B2DPolyPolygon solvePolygonOperationXor(const B2DPolyPolygon& rCandidateA, const B2DPolyPolygon& rCandidateB)
856 {
857 if(!rCandidateA.count())
858 {
859 return rCandidateB;
860 }
861 else if(!rCandidateB.count())
862 {
863 return rCandidateA;
864 }
865 else
866 {
867 // XOR is pretty simple: By definition it is the simple concatenation of
868 // the single polygons since we imply XOR fill rule. Make it intersection-free
869 // and correct orientations
870 B2DPolyPolygon aRetval(rCandidateA);
871
872 aRetval.append(rCandidateB);
873 aRetval = solveCrossovers(aRetval);
874 aRetval = stripNeutralPolygons(aRetval);
875
876 return correctOrientations(aRetval);
877 }
878 }
879
880 B2DPolyPolygon solvePolygonOperationAnd(const B2DPolyPolygon& rCandidateA, const B2DPolyPolygon& rCandidateB)
881 {
882 if(!rCandidateA.count())
883 {
884 return B2DPolyPolygon();
885 }
886 else if(!rCandidateB.count())
887 {
888 return B2DPolyPolygon();
889 }
890 else
891 {
892 // concatenate polygons, solve crossovers and throw away all sub-polygons
893 // with a depth of < 1. This means to keep all polygons where at least two
894 // polygons do overlap.
895 B2DPolyPolygon aRetval(rCandidateA);
896
897 aRetval.append(rCandidateB);
898 aRetval = solveCrossovers(aRetval);
899 aRetval = stripNeutralPolygons(aRetval);
900
901 return stripDispensablePolygons(aRetval, true);
902 }
903 }
904
905 B2DPolyPolygon solvePolygonOperationDiff(const B2DPolyPolygon& rCandidateA, const B2DPolyPolygon& rCandidateB)
906 {
907 if(!rCandidateA.count())
908 {
909 return B2DPolyPolygon();
910 }
911 else if(!rCandidateB.count())
912 {
913 return rCandidateA;
914 }
915 else
916 {
917 // Make B topologically to holes and append to A
918 B2DPolyPolygon aRetval(rCandidateB);
919
920 aRetval.flip();
921 aRetval.append(rCandidateA);
922
923 // solve crossovers and throw away all sub-polygons which have a
924 // depth other than 0.
925 aRetval = basegfx::tools::solveCrossovers(aRetval);
926 aRetval = basegfx::tools::stripNeutralPolygons(aRetval);
927
928 return basegfx::tools::stripDispensablePolygons(aRetval, false);
929 }
930 }
931
932 B2DPolyPolygon mergeToSinglePolyPolygon(const std::vector< basegfx::B2DPolyPolygon >& rInput)
933 {
934 std::vector< basegfx::B2DPolyPolygon > aInput(rInput);
935
936 // first step: prepareForPolygonOperation and simple merge of non-overlapping
937 // PolyPolygons for speedup; this is possible for the wanted OR-operation
938 if(aInput.size())
939 {
940 std::vector< basegfx::B2DPolyPolygon > aResult;
941 aResult.reserve(aInput.size());
942
943 for(sal_uInt32 a(0); a < aInput.size(); a++)
944 {
945 const basegfx::B2DPolyPolygon aCandidate(prepareForPolygonOperation(aInput[a]));
946
947 if(aResult.size())
948 {
949 const B2DRange aCandidateRange(aCandidate.getB2DRange());
950 bool bCouldMergeSimple(false);
951
952 for(sal_uInt32 b(0); !bCouldMergeSimple && b < aResult.size(); b++)
953 {
954 basegfx::B2DPolyPolygon aTarget(aResult[b]);
955 const B2DRange aTargetRange(aTarget.getB2DRange());
956
957 if(!aCandidateRange.overlaps(aTargetRange))
958 {
959 aTarget.append(aCandidate);
960 aResult[b] = aTarget;
961 bCouldMergeSimple = true;
962 }
963 }
964
965 if(!bCouldMergeSimple)
966 {
967 aResult.push_back(aCandidate);
968 }
969 }
970 else
971 {
972 aResult.push_back(aCandidate);
973 }
974 }
975
976 aInput = aResult;
977 }
978
979 // second step: melt pairwise to a single PolyPolygon
980 while(aInput.size() > 1)
981 {
982 std::vector< basegfx::B2DPolyPolygon > aResult;
983 aResult.reserve((aInput.size() / 2) + 1);
984
985 for(sal_uInt32 a(0); a < aInput.size(); a += 2)
986 {
987 if(a + 1 < aInput.size())
988 {
989 // a pair for processing
990 aResult.push_back(solvePolygonOperationOr(aInput[a], aInput[a + 1]));
991 }
992 else
993 {
994 // last single PolyPolygon; copy to target to not lose it
995 aResult.push_back(aInput[a]);
996 }
997 }
998
999 aInput = aResult;
1000 }
1001
1002 // third step: get result
1003 if(1 == aInput.size())
1004 {
1005 return aInput[0];
1006 }
1007
1008 return B2DPolyPolygon();
1009 }
1010
1011 //////////////////////////////////////////////////////////////////////////////
1012
1013 } // end of namespace tools
1014 } // end of namespace basegfx
1015
1016 //////////////////////////////////////////////////////////////////////////////
1017 // eof
vba interoperability for OOo