1 /**************************************************************
2  *
3  * Licensed to the Apache Software Foundation (ASF) under one
4  * or more contributor license agreements.  See the NOTICE file
5  * distributed with this work for additional information
6  * regarding copyright ownership.  The ASF licenses this file
7  * to you under the Apache License, Version 2.0 (the
8  * "License"); you may not use this file except in compliance
9  * with the License.  You may obtain a copy of the License at
10  *
11  *   http://www.apache.org/licenses/LICENSE-2.0
12  *
13  * Unless required by applicable law or agreed to in writing,
14  * software distributed under the License is distributed on an
15  * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
16  * KIND, either express or implied.  See the License for the
17  * specific language governing permissions and limitations
18  * under the License.
19  *
20  *************************************************************/
21 
22 
23 
24 // MARKER(update_precomp.py): autogen include statement, do not remove
25 #include "precompiled_basegfx.hxx"
26 #include <basegfx/tools/b2dclipstate.hxx>
27 
28 #include <basegfx/range/b2drange.hxx>
29 #include <basegfx/range/b2dpolyrange.hxx>
30 #include <basegfx/range/b2drangeclipper.hxx>
31 #include <basegfx/polygon/b2dpolygon.hxx>
32 #include <basegfx/polygon/b2dpolygontools.hxx>
33 #include <basegfx/polygon/b2dpolypolygon.hxx>
34 #include <basegfx/polygon/b2dpolypolygontools.hxx>
35 #include <basegfx/polygon/b2dpolypolygoncutter.hxx>
36 
37 namespace basegfx
38 {
39 namespace tools
40 {
41     struct ImplB2DClipState
42     {
43     public:
44         enum Operation {UNION, INTERSECT, XOR, SUBTRACT};
45 
ImplB2DClipStatebasegfx::tools::ImplB2DClipState46         ImplB2DClipState() :
47             maPendingPolygons(),
48             maPendingRanges(),
49             maClipPoly(),
50             mePendingOps(UNION)
51         {}
52 
ImplB2DClipStatebasegfx::tools::ImplB2DClipState53         explicit ImplB2DClipState( const B2DRange& rRange ) :
54             maPendingPolygons(),
55             maPendingRanges(),
56             maClipPoly(
57                 tools::createPolygonFromRect(rRange)),
58             mePendingOps(UNION)
59         {}
60 
ImplB2DClipStatebasegfx::tools::ImplB2DClipState61         explicit ImplB2DClipState( const B2DPolygon& rPoly ) :
62             maPendingPolygons(),
63             maPendingRanges(),
64             maClipPoly(rPoly),
65             mePendingOps(UNION)
66         {}
67 
ImplB2DClipStatebasegfx::tools::ImplB2DClipState68         explicit ImplB2DClipState( const B2DPolyPolygon& rPoly ) :
69             maPendingPolygons(),
70             maPendingRanges(),
71             maClipPoly(rPoly),
72             mePendingOps(UNION)
73         {}
74 
isClearedbasegfx::tools::ImplB2DClipState75         bool isCleared() const
76         {
77             return !maClipPoly.count()
78                 && !maPendingPolygons.count()
79                 && !maPendingRanges.count();
80         }
81 
makeClearbasegfx::tools::ImplB2DClipState82         void makeClear()
83         {
84             maPendingPolygons.clear();
85             maPendingRanges.clear();
86             maClipPoly.clear();
87             mePendingOps = UNION;
88         }
89 
isNullClipPolybasegfx::tools::ImplB2DClipState90         bool isNullClipPoly() const
91         {
92             return maClipPoly.count() == 1
93                 && !maClipPoly.getB2DPolygon(0).count();
94         }
95 
isNullbasegfx::tools::ImplB2DClipState96         bool isNull() const
97         {
98             return !maPendingPolygons.count()
99                 && !maPendingRanges.count()
100                 && isNullClipPoly();
101         }
102 
makeNullbasegfx::tools::ImplB2DClipState103         void makeNull()
104         {
105             maPendingPolygons.clear();
106             maPendingRanges.clear();
107             maClipPoly.clear();
108             maClipPoly.append(B2DPolygon());
109             mePendingOps = UNION;
110         }
111 
operator ==basegfx::tools::ImplB2DClipState112         bool operator==(const ImplB2DClipState& rRHS) const
113         {
114             return maPendingPolygons == rRHS.maPendingPolygons
115                 && maPendingRanges == rRHS.maPendingRanges
116                 && maClipPoly == rRHS.maClipPoly
117                 && mePendingOps == rRHS.mePendingOps;
118         }
119 
addRangebasegfx::tools::ImplB2DClipState120         void addRange(const B2DRange& rRange, Operation eOp)
121         {
122             if( rRange.isEmpty() )
123                 return;
124 
125             commitPendingPolygons();
126             if( mePendingOps != eOp )
127                 commitPendingRanges();
128 
129             mePendingOps = eOp;
130             maPendingRanges.appendElement(
131                 rRange,
132                 ORIENTATION_POSITIVE);
133         }
134 
addPolygonbasegfx::tools::ImplB2DClipState135         void addPolygon(B2DPolygon aPoly, Operation eOp)
136         {
137             commitPendingRanges();
138             if( mePendingOps != eOp )
139                 commitPendingPolygons();
140 
141             mePendingOps = eOp;
142             maPendingPolygons.append(aPoly);
143         }
144 
addPolyPolygonbasegfx::tools::ImplB2DClipState145         void addPolyPolygon(B2DPolyPolygon aPoly, Operation eOp)
146         {
147             commitPendingRanges();
148             if( mePendingOps != eOp )
149                 commitPendingPolygons();
150 
151             mePendingOps = eOp;
152             maPendingPolygons.append(aPoly);
153         }
154 
addClipStatebasegfx::tools::ImplB2DClipState155         void addClipState(const ImplB2DClipState& rOther, Operation eOp)
156         {
157             if( rOther.mePendingOps == mePendingOps
158                 && !rOther.maClipPoly.count()
159                 && !rOther.maPendingPolygons.count() )
160             {
161                 maPendingRanges.appendPolyRange( rOther.maPendingRanges );
162             }
163             else
164             {
165                 commitPendingRanges();
166                 commitPendingPolygons();
167                 rOther.commitPendingRanges();
168                 rOther.commitPendingPolygons();
169 
170                 maPendingPolygons = rOther.maClipPoly;
171                 mePendingOps = eOp;
172             }
173         }
174 
unionRangebasegfx::tools::ImplB2DClipState175         void unionRange(const B2DRange& rRange)
176         {
177             if( isCleared() )
178                 return;
179 
180             addRange(rRange,UNION);
181         }
182 
unionPolygonbasegfx::tools::ImplB2DClipState183         void unionPolygon(const B2DPolygon& rPoly)
184         {
185             if( isCleared() )
186                 return;
187 
188             addPolygon(rPoly,UNION);
189         }
190 
unionPolyPolygonbasegfx::tools::ImplB2DClipState191         void unionPolyPolygon(const B2DPolyPolygon& rPolyPoly)
192         {
193             if( isCleared() )
194                 return;
195 
196             addPolyPolygon(rPolyPoly,UNION);
197         }
198 
unionClipStatebasegfx::tools::ImplB2DClipState199         void unionClipState(const ImplB2DClipState& rOther)
200         {
201             if( isCleared() )
202                 return;
203 
204             addClipState(rOther, UNION);
205         }
206 
intersectRangebasegfx::tools::ImplB2DClipState207         void intersectRange(const B2DRange& rRange)
208         {
209             if( isNull() )
210                 return;
211 
212             addRange(rRange,INTERSECT);
213         }
214 
intersectPolygonbasegfx::tools::ImplB2DClipState215         void intersectPolygon(const B2DPolygon& rPoly)
216         {
217             if( isNull() )
218                 return;
219 
220             addPolygon(rPoly,INTERSECT);
221         }
222 
intersectPolyPolygonbasegfx::tools::ImplB2DClipState223         void intersectPolyPolygon(const B2DPolyPolygon& rPolyPoly)
224         {
225             if( isNull() )
226                 return;
227 
228             addPolyPolygon(rPolyPoly,INTERSECT);
229         }
230 
intersectClipStatebasegfx::tools::ImplB2DClipState231         void intersectClipState(const ImplB2DClipState& rOther)
232         {
233             if( isNull() )
234                 return;
235 
236             addClipState(rOther, INTERSECT);
237         }
238 
subtractRangebasegfx::tools::ImplB2DClipState239         void subtractRange(const B2DRange& rRange )
240         {
241             if( isNull() )
242                 return;
243 
244             addRange(rRange,SUBTRACT);
245         }
246 
subtractPolygonbasegfx::tools::ImplB2DClipState247         void subtractPolygon(const B2DPolygon& rPoly)
248         {
249             if( isNull() )
250                 return;
251 
252             addPolygon(rPoly,SUBTRACT);
253         }
254 
subtractPolyPolygonbasegfx::tools::ImplB2DClipState255         void subtractPolyPolygon(const B2DPolyPolygon& rPolyPoly)
256         {
257             if( isNull() )
258                 return;
259 
260             addPolyPolygon(rPolyPoly,SUBTRACT);
261         }
262 
subtractClipStatebasegfx::tools::ImplB2DClipState263         void subtractClipState(const ImplB2DClipState& rOther)
264         {
265             if( isNull() )
266                 return;
267 
268             addClipState(rOther, SUBTRACT);
269         }
270 
xorRangebasegfx::tools::ImplB2DClipState271         void xorRange(const B2DRange& rRange)
272         {
273             addRange(rRange,XOR);
274         }
275 
xorPolygonbasegfx::tools::ImplB2DClipState276         void xorPolygon(const B2DPolygon& rPoly)
277         {
278             addPolygon(rPoly,XOR);
279         }
280 
xorPolyPolygonbasegfx::tools::ImplB2DClipState281         void xorPolyPolygon(const B2DPolyPolygon& rPolyPoly)
282         {
283             addPolyPolygon(rPolyPoly,XOR);
284         }
285 
xorClipStatebasegfx::tools::ImplB2DClipState286         void xorClipState(const ImplB2DClipState& rOther)
287         {
288             addClipState(rOther, XOR);
289         }
290 
getClipPolybasegfx::tools::ImplB2DClipState291         B2DPolyPolygon getClipPoly() const
292         {
293             commitPendingRanges();
294             commitPendingPolygons();
295 
296             return maClipPoly;
297         }
298 
299     private:
commitPendingPolygonsbasegfx::tools::ImplB2DClipState300         void commitPendingPolygons() const
301         {
302             if( !maPendingPolygons.count() )
303                 return;
304 
305             // assumption: maClipPoly has kept polygons prepared for
306             // clipping; i.e. no neutral polygons & correct
307             // orientation
308             maPendingPolygons = tools::prepareForPolygonOperation(maPendingPolygons);
309             const bool bIsEmpty=isNullClipPoly();
310             const bool bIsCleared=!maClipPoly.count();
311             switch(mePendingOps)
312             {
313                 case UNION:
314                     OSL_ASSERT( !bIsCleared );
315 
316                     if( bIsEmpty )
317                         maClipPoly = maPendingPolygons;
318                     else
319                         maClipPoly = tools::solvePolygonOperationOr(
320                             maClipPoly,
321                             maPendingPolygons);
322                     break;
323                 case INTERSECT:
324                     OSL_ASSERT( !bIsEmpty );
325 
326                     if( bIsCleared )
327                         maClipPoly = maPendingPolygons;
328                     else
329                         maClipPoly = tools::solvePolygonOperationAnd(
330                             maClipPoly,
331                             maPendingPolygons);
332                     break;
333                 case XOR:
334                     if( bIsEmpty )
335                         maClipPoly = maPendingPolygons;
336                     else if( bIsCleared )
337                     {
338                         // not representable, strictly speaking,
339                         // using polygons with the common even/odd
340                         // or nonzero winding number fill rule. If
341                         // we'd want to represent it, fill rule
342                         // would need to be "non-negative winding
343                         // number" (and we then would return
344                         // 'holes' here)
345 
346                         // going for an ugly hack meanwhile
347                         maClipPoly = tools::solvePolygonOperationXor(
348                             B2DPolyPolygon(
349                                 tools::createPolygonFromRect(B2DRange(-1E20,-1E20,1E20,1E20))),
350                             maPendingPolygons);
351                     }
352                     else
353                         maClipPoly = tools::solvePolygonOperationXor(
354                             maClipPoly,
355                             maPendingPolygons);
356                     break;
357                 case SUBTRACT:
358                     OSL_ASSERT( !bIsEmpty );
359 
360                     // first union all pending ones, subtract en bloc then
361                     maPendingPolygons = solveCrossovers(maPendingPolygons);
362                     maPendingPolygons = stripNeutralPolygons(maPendingPolygons);
363                     maPendingPolygons = stripDispensablePolygons(maPendingPolygons, false);
364 
365                     if( bIsCleared )
366                     {
367                         // not representable, strictly speaking,
368                         // using polygons with the common even/odd
369                         // or nonzero winding number fill rule. If
370                         // we'd want to represent it, fill rule
371                         // would need to be "non-negative winding
372                         // number" (and we then would return
373                         // 'holes' here)
374 
375                         // going for an ugly hack meanwhile
376                         maClipPoly = tools::solvePolygonOperationDiff(
377                             B2DPolyPolygon(
378                                 tools::createPolygonFromRect(B2DRange(-1E20,-1E20,1E20,1E20))),
379                             maPendingPolygons);
380                     }
381                     else
382                         maClipPoly = tools::solvePolygonOperationDiff(
383                             maClipPoly,
384                             maPendingPolygons);
385                     break;
386             }
387 
388             maPendingPolygons.clear();
389             mePendingOps = UNION;
390         }
391 
commitPendingRangesbasegfx::tools::ImplB2DClipState392         void commitPendingRanges() const
393         {
394             if( !maPendingRanges.count() )
395                 return;
396 
397             // use the specialized range clipper for the win
398             B2DPolyPolygon aCollectedRanges;
399             const bool bIsEmpty=isNullClipPoly();
400             const bool bIsCleared=!maClipPoly.count();
401             switch(mePendingOps)
402             {
403                 case UNION:
404                     OSL_ASSERT( !bIsCleared );
405 
406                     aCollectedRanges = maPendingRanges.solveCrossovers();
407                     aCollectedRanges = stripNeutralPolygons(aCollectedRanges);
408                     aCollectedRanges = stripDispensablePolygons(aCollectedRanges, false);
409                     if( bIsEmpty )
410                         maClipPoly = aCollectedRanges;
411                     else
412                         maClipPoly = tools::solvePolygonOperationOr(
413                             maClipPoly,
414                             aCollectedRanges);
415                     break;
416                 case INTERSECT:
417                     OSL_ASSERT( !bIsEmpty );
418 
419                     aCollectedRanges = maPendingRanges.solveCrossovers();
420                     aCollectedRanges = stripNeutralPolygons(aCollectedRanges);
421                     if( maPendingRanges.count() > 1 )
422                         aCollectedRanges = stripDispensablePolygons(aCollectedRanges, true);
423 
424                     if( bIsCleared )
425                         maClipPoly = aCollectedRanges;
426                     else
427                         maClipPoly = tools::solvePolygonOperationAnd(
428                             maClipPoly,
429                             aCollectedRanges);
430                     break;
431                 case XOR:
432                     aCollectedRanges = maPendingRanges.solveCrossovers();
433                     aCollectedRanges = stripNeutralPolygons(aCollectedRanges);
434                     aCollectedRanges = correctOrientations(aCollectedRanges);
435 
436                     if( bIsEmpty )
437                         maClipPoly = aCollectedRanges;
438                     else if( bIsCleared )
439                     {
440                         // not representable, strictly speaking,
441                         // using polygons with the common even/odd
442                         // or nonzero winding number fill rule. If
443                         // we'd want to represent it, fill rule
444                         // would need to be "non-negative winding
445                         // number" (and we then would return
446                         // 'holes' here)
447 
448                         // going for an ugly hack meanwhile
449                         maClipPoly = tools::solvePolygonOperationXor(
450                             B2DPolyPolygon(
451                                 tools::createPolygonFromRect(B2DRange(-1E20,-1E20,1E20,1E20))),
452                             aCollectedRanges);
453                     }
454                     else
455                         maClipPoly = tools::solvePolygonOperationXor(
456                             maClipPoly,
457                             aCollectedRanges);
458                     break;
459                 case SUBTRACT:
460                     OSL_ASSERT( !bIsEmpty );
461 
462                     // first union all pending ranges, subtract en bloc then
463                     aCollectedRanges = maPendingRanges.solveCrossovers();
464                     aCollectedRanges = stripNeutralPolygons(aCollectedRanges);
465                     aCollectedRanges = stripDispensablePolygons(aCollectedRanges, false);
466 
467                     if( bIsCleared )
468                     {
469                         // not representable, strictly speaking,
470                         // using polygons with the common even/odd
471                         // or nonzero winding number fill rule. If
472                         // we'd want to represent it, fill rule
473                         // would need to be "non-negative winding
474                         // number" (and we then would return
475                         // 'holes' here)
476 
477                         // going for an ugly hack meanwhile
478                         maClipPoly = tools::solvePolygonOperationDiff(
479                             B2DPolyPolygon(
480                                 tools::createPolygonFromRect(B2DRange(-1E20,-1E20,1E20,1E20))),
481                             aCollectedRanges);
482                     }
483                     else
484                         maClipPoly = tools::solvePolygonOperationDiff(
485                             maClipPoly,
486                             aCollectedRanges);
487                     break;
488             }
489 
490             maPendingRanges.clear();
491             mePendingOps = UNION;
492         }
493 
494         mutable B2DPolyPolygon maPendingPolygons;
495         mutable B2DPolyRange   maPendingRanges;
496         mutable B2DPolyPolygon maClipPoly;
497         mutable Operation      mePendingOps;
498     };
499 
B2DClipState()500     B2DClipState::B2DClipState() :
501         mpImpl()
502     {}
503 
~B2DClipState()504     B2DClipState::~B2DClipState()
505     {}
506 
B2DClipState(const B2DClipState & rOrig)507     B2DClipState::B2DClipState( const B2DClipState& rOrig ) :
508         mpImpl(rOrig.mpImpl)
509     {}
510 
B2DClipState(const B2DRange & rRange)511     B2DClipState::B2DClipState( const B2DRange& rRange ) :
512         mpImpl( ImplB2DClipState(rRange) )
513     {}
514 
B2DClipState(const B2DPolygon & rPoly)515     B2DClipState::B2DClipState( const B2DPolygon& rPoly ) :
516         mpImpl( ImplB2DClipState(rPoly) )
517     {}
518 
B2DClipState(const B2DPolyPolygon & rPolyPoly)519     B2DClipState::B2DClipState( const B2DPolyPolygon& rPolyPoly ) :
520         mpImpl( ImplB2DClipState(rPolyPoly) )
521     {}
522 
operator =(const B2DClipState & rRHS)523     B2DClipState& B2DClipState::operator=( const B2DClipState& rRHS )
524     {
525         mpImpl = rRHS.mpImpl;
526         return *this;
527     }
528 
makeUnique()529     void B2DClipState::makeUnique()
530     {
531         mpImpl.make_unique();
532     }
533 
makeNull()534     void B2DClipState::makeNull()
535     {
536         mpImpl->makeNull();
537     }
538 
isNull() const539     bool B2DClipState::isNull() const
540     {
541         return mpImpl->isNull();
542     }
543 
makeClear()544     void B2DClipState::makeClear()
545     {
546         mpImpl->makeClear();
547     }
548 
isCleared() const549     bool B2DClipState::isCleared() const
550     {
551         return mpImpl->isCleared();
552     }
553 
operator ==(const B2DClipState & rRHS) const554     bool B2DClipState::operator==(const B2DClipState& rRHS) const
555     {
556         if(mpImpl.same_object(rRHS.mpImpl))
557             return true;
558 
559         return ((*mpImpl) == (*rRHS.mpImpl));
560     }
561 
operator !=(const B2DClipState & rRHS) const562     bool B2DClipState::operator!=(const B2DClipState& rRHS) const
563     {
564         return !(*this == rRHS);
565     }
566 
unionRange(const B2DRange & rRange)567     void B2DClipState::unionRange(const B2DRange& rRange)
568     {
569         mpImpl->unionRange(rRange);
570     }
571 
unionPolygon(const B2DPolygon & rPoly)572     void B2DClipState::unionPolygon(const B2DPolygon& rPoly)
573     {
574         mpImpl->unionPolygon(rPoly);
575     }
576 
unionPolyPolygon(const B2DPolyPolygon & rPolyPoly)577     void B2DClipState::unionPolyPolygon(const B2DPolyPolygon& rPolyPoly)
578     {
579         mpImpl->unionPolyPolygon(rPolyPoly);
580     }
581 
unionClipState(const B2DClipState & rState)582     void B2DClipState::unionClipState(const B2DClipState& rState)
583     {
584         mpImpl->unionClipState(*rState.mpImpl);
585     }
586 
intersectRange(const B2DRange & rRange)587     void B2DClipState::intersectRange(const B2DRange& rRange)
588     {
589         mpImpl->intersectRange(rRange);
590     }
591 
intersectPolygon(const B2DPolygon & rPoly)592     void B2DClipState::intersectPolygon(const B2DPolygon& rPoly)
593     {
594         mpImpl->intersectPolygon(rPoly);
595     }
596 
intersectPolyPolygon(const B2DPolyPolygon & rPolyPoly)597     void B2DClipState::intersectPolyPolygon(const B2DPolyPolygon& rPolyPoly)
598     {
599         mpImpl->intersectPolyPolygon(rPolyPoly);
600     }
601 
intersectClipState(const B2DClipState & rState)602     void B2DClipState::intersectClipState(const B2DClipState& rState)
603     {
604         mpImpl->intersectClipState(*rState.mpImpl);
605     }
606 
subtractRange(const B2DRange & rRange)607     void B2DClipState::subtractRange(const B2DRange& rRange)
608     {
609         mpImpl->subtractRange(rRange);
610     }
611 
subtractPolygon(const B2DPolygon & rPoly)612     void B2DClipState::subtractPolygon(const B2DPolygon& rPoly)
613     {
614         mpImpl->subtractPolygon(rPoly);
615     }
616 
subtractPolyPolygon(const B2DPolyPolygon & rPolyPoly)617     void B2DClipState::subtractPolyPolygon(const B2DPolyPolygon& rPolyPoly)
618     {
619         mpImpl->subtractPolyPolygon(rPolyPoly);
620     }
621 
subtractClipState(const B2DClipState & rState)622     void B2DClipState::subtractClipState(const B2DClipState& rState)
623     {
624         mpImpl->subtractClipState(*rState.mpImpl);
625     }
626 
xorRange(const B2DRange & rRange)627     void B2DClipState::xorRange(const B2DRange& rRange)
628     {
629         mpImpl->xorRange(rRange);
630     }
631 
xorPolygon(const B2DPolygon & rPoly)632     void B2DClipState::xorPolygon(const B2DPolygon& rPoly)
633     {
634         mpImpl->xorPolygon(rPoly);
635     }
636 
xorPolyPolygon(const B2DPolyPolygon & rPolyPoly)637     void B2DClipState::xorPolyPolygon(const B2DPolyPolygon& rPolyPoly)
638     {
639         mpImpl->xorPolyPolygon(rPolyPoly);
640     }
641 
xorClipState(const B2DClipState & rState)642     void B2DClipState::xorClipState(const B2DClipState& rState)
643     {
644         mpImpl->xorClipState(*rState.mpImpl);
645     }
646 
getClipPoly() const647     B2DPolyPolygon B2DClipState::getClipPoly() const
648     {
649         return mpImpl->getClipPoly();
650     }
651 
652 } // end of namespace tools
653 } // end of namespace basegfx
654 
655 // eof
656