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