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