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: b2dmultirange.cxx,v $
10  * $Revision: 1.8 $
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 <basegfx/tools/b2dclipstate.hxx>
34 
35 #include <basegfx/range/b2drange.hxx>
36 #include <basegfx/range/b2dpolyrange.hxx>
37 #include <basegfx/range/b2drangeclipper.hxx>
38 #include <basegfx/polygon/b2dpolygon.hxx>
39 #include <basegfx/polygon/b2dpolygontools.hxx>
40 #include <basegfx/polygon/b2dpolypolygon.hxx>
41 #include <basegfx/polygon/b2dpolypolygontools.hxx>
42 #include <basegfx/polygon/b2dpolypolygoncutter.hxx>
43 
44 namespace basegfx
45 {
46 namespace tools
47 {
48     struct ImplB2DClipState
49     {
50     public:
51         enum Operation {UNION, INTERSECT, XOR, SUBTRACT};
52 
53         ImplB2DClipState() :
54             maPendingPolygons(),
55             maPendingRanges(),
56             maClipPoly(),
57             mePendingOps(UNION)
58         {}
59 
60         explicit ImplB2DClipState( const B2DRange& rRange ) :
61             maPendingPolygons(),
62             maPendingRanges(),
63             maClipPoly(
64                 tools::createPolygonFromRect(rRange)),
65             mePendingOps(UNION)
66         {}
67 
68         explicit ImplB2DClipState( const B2DPolygon& rPoly ) :
69             maPendingPolygons(),
70             maPendingRanges(),
71             maClipPoly(rPoly),
72             mePendingOps(UNION)
73         {}
74 
75         explicit ImplB2DClipState( const B2DPolyPolygon& rPoly ) :
76             maPendingPolygons(),
77             maPendingRanges(),
78             maClipPoly(rPoly),
79             mePendingOps(UNION)
80         {}
81 
82         bool isCleared() const
83         {
84             return !maClipPoly.count()
85                 && !maPendingPolygons.count()
86                 && !maPendingRanges.count();
87         }
88 
89         void makeClear()
90         {
91             maPendingPolygons.clear();
92             maPendingRanges.clear();
93             maClipPoly.clear();
94             mePendingOps = UNION;
95         }
96 
97         bool isNullClipPoly() const
98         {
99             return maClipPoly.count() == 1
100                 && !maClipPoly.getB2DPolygon(0).count();
101         }
102 
103         bool isNull() const
104         {
105             return !maPendingPolygons.count()
106                 && !maPendingRanges.count()
107                 && isNullClipPoly();
108         }
109 
110         void makeNull()
111         {
112             maPendingPolygons.clear();
113             maPendingRanges.clear();
114             maClipPoly.clear();
115             maClipPoly.append(B2DPolygon());
116             mePendingOps = UNION;
117         }
118 
119         bool operator==(const ImplB2DClipState& rRHS) const
120         {
121             return maPendingPolygons == rRHS.maPendingPolygons
122                 && maPendingRanges == rRHS.maPendingRanges
123                 && maClipPoly == rRHS.maClipPoly
124                 && mePendingOps == rRHS.mePendingOps;
125         }
126 
127         void addRange(const B2DRange& rRange, Operation eOp)
128         {
129             if( rRange.isEmpty() )
130                 return;
131 
132             commitPendingPolygons();
133             if( mePendingOps != eOp )
134                 commitPendingRanges();
135 
136             mePendingOps = eOp;
137             maPendingRanges.appendElement(
138                 rRange,
139                 ORIENTATION_POSITIVE);
140         }
141 
142         void addPolygon(B2DPolygon aPoly, Operation eOp)
143         {
144             commitPendingRanges();
145             if( mePendingOps != eOp )
146                 commitPendingPolygons();
147 
148             mePendingOps = eOp;
149             maPendingPolygons.append(aPoly);
150         }
151 
152         void addPolyPolygon(B2DPolyPolygon aPoly, Operation eOp)
153         {
154             commitPendingRanges();
155             if( mePendingOps != eOp )
156                 commitPendingPolygons();
157 
158             mePendingOps = eOp;
159             maPendingPolygons.append(aPoly);
160         }
161 
162         void addClipState(const ImplB2DClipState& rOther, Operation eOp)
163         {
164             if( rOther.mePendingOps == mePendingOps
165                 && !rOther.maClipPoly.count()
166                 && !rOther.maPendingPolygons.count() )
167             {
168                 maPendingRanges.appendPolyRange( rOther.maPendingRanges );
169             }
170             else
171             {
172                 commitPendingRanges();
173                 commitPendingPolygons();
174                 rOther.commitPendingRanges();
175                 rOther.commitPendingPolygons();
176 
177                 maPendingPolygons = rOther.maClipPoly;
178                 mePendingOps = eOp;
179             }
180         }
181 
182         void unionRange(const B2DRange& rRange)
183         {
184             if( isCleared() )
185                 return;
186 
187             addRange(rRange,UNION);
188         }
189 
190         void unionPolygon(const B2DPolygon& rPoly)
191         {
192             if( isCleared() )
193                 return;
194 
195             addPolygon(rPoly,UNION);
196         }
197 
198         void unionPolyPolygon(const B2DPolyPolygon& rPolyPoly)
199         {
200             if( isCleared() )
201                 return;
202 
203             addPolyPolygon(rPolyPoly,UNION);
204         }
205 
206         void unionClipState(const ImplB2DClipState& rOther)
207         {
208             if( isCleared() )
209                 return;
210 
211             addClipState(rOther, UNION);
212         }
213 
214         void intersectRange(const B2DRange& rRange)
215         {
216             if( isNull() )
217                 return;
218 
219             addRange(rRange,INTERSECT);
220         }
221 
222         void intersectPolygon(const B2DPolygon& rPoly)
223         {
224             if( isNull() )
225                 return;
226 
227             addPolygon(rPoly,INTERSECT);
228         }
229 
230         void intersectPolyPolygon(const B2DPolyPolygon& rPolyPoly)
231         {
232             if( isNull() )
233                 return;
234 
235             addPolyPolygon(rPolyPoly,INTERSECT);
236         }
237 
238         void intersectClipState(const ImplB2DClipState& rOther)
239         {
240             if( isNull() )
241                 return;
242 
243             addClipState(rOther, INTERSECT);
244         }
245 
246         void subtractRange(const B2DRange& rRange )
247         {
248             if( isNull() )
249                 return;
250 
251             addRange(rRange,SUBTRACT);
252         }
253 
254         void subtractPolygon(const B2DPolygon& rPoly)
255         {
256             if( isNull() )
257                 return;
258 
259             addPolygon(rPoly,SUBTRACT);
260         }
261 
262         void subtractPolyPolygon(const B2DPolyPolygon& rPolyPoly)
263         {
264             if( isNull() )
265                 return;
266 
267             addPolyPolygon(rPolyPoly,SUBTRACT);
268         }
269 
270         void subtractClipState(const ImplB2DClipState& rOther)
271         {
272             if( isNull() )
273                 return;
274 
275             addClipState(rOther, SUBTRACT);
276         }
277 
278         void xorRange(const B2DRange& rRange)
279         {
280             addRange(rRange,XOR);
281         }
282 
283         void xorPolygon(const B2DPolygon& rPoly)
284         {
285             addPolygon(rPoly,XOR);
286         }
287 
288         void xorPolyPolygon(const B2DPolyPolygon& rPolyPoly)
289         {
290             addPolyPolygon(rPolyPoly,XOR);
291         }
292 
293         void xorClipState(const ImplB2DClipState& rOther)
294         {
295             addClipState(rOther, XOR);
296         }
297 
298         B2DPolyPolygon getClipPoly() const
299         {
300             commitPendingRanges();
301             commitPendingPolygons();
302 
303             return maClipPoly;
304         }
305 
306     private:
307         void commitPendingPolygons() const
308         {
309             if( !maPendingPolygons.count() )
310                 return;
311 
312             // assumption: maClipPoly has kept polygons prepared for
313             // clipping; i.e. no neutral polygons & correct
314             // orientation
315             maPendingPolygons = tools::prepareForPolygonOperation(maPendingPolygons);
316             const bool bIsEmpty=isNullClipPoly();
317             const bool bIsCleared=!maClipPoly.count();
318             switch(mePendingOps)
319             {
320                 case UNION:
321                     OSL_ASSERT( !bIsCleared );
322 
323                     if( bIsEmpty )
324                         maClipPoly = maPendingPolygons;
325                     else
326                         maClipPoly = tools::solvePolygonOperationOr(
327                             maClipPoly,
328                             maPendingPolygons);
329                     break;
330                 case INTERSECT:
331                     OSL_ASSERT( !bIsEmpty );
332 
333                     if( bIsCleared )
334                         maClipPoly = maPendingPolygons;
335                     else
336                         maClipPoly = tools::solvePolygonOperationAnd(
337                             maClipPoly,
338                             maPendingPolygons);
339                     break;
340                 case XOR:
341                     if( bIsEmpty )
342                         maClipPoly = maPendingPolygons;
343                     else if( bIsCleared )
344                     {
345                         // not representable, strictly speaking,
346                         // using polygons with the common even/odd
347                         // or nonzero winding number fill rule. If
348                         // we'd want to represent it, fill rule
349                         // would need to be "non-negative winding
350                         // number" (and we then would return
351                         // 'holes' here)
352 
353                         // going for an ugly hack meanwhile
354                         maClipPoly = tools::solvePolygonOperationXor(
355                             B2DPolyPolygon(
356                                 tools::createPolygonFromRect(B2DRange(-1E20,-1E20,1E20,1E20))),
357                             maPendingPolygons);
358                     }
359                     else
360                         maClipPoly = tools::solvePolygonOperationXor(
361                             maClipPoly,
362                             maPendingPolygons);
363                     break;
364                 case SUBTRACT:
365                     OSL_ASSERT( !bIsEmpty );
366 
367                     // first union all pending ones, subtract en bloc then
368                     maPendingPolygons = solveCrossovers(maPendingPolygons);
369                     maPendingPolygons = stripNeutralPolygons(maPendingPolygons);
370                     maPendingPolygons = stripDispensablePolygons(maPendingPolygons, false);
371 
372                     if( bIsCleared )
373                     {
374                         // not representable, strictly speaking,
375                         // using polygons with the common even/odd
376                         // or nonzero winding number fill rule. If
377                         // we'd want to represent it, fill rule
378                         // would need to be "non-negative winding
379                         // number" (and we then would return
380                         // 'holes' here)
381 
382                         // going for an ugly hack meanwhile
383                         maClipPoly = tools::solvePolygonOperationDiff(
384                             B2DPolyPolygon(
385                                 tools::createPolygonFromRect(B2DRange(-1E20,-1E20,1E20,1E20))),
386                             maPendingPolygons);
387                     }
388                     else
389                         maClipPoly = tools::solvePolygonOperationDiff(
390                             maClipPoly,
391                             maPendingPolygons);
392                     break;
393             }
394 
395             maPendingPolygons.clear();
396             mePendingOps = UNION;
397         }
398 
399         void commitPendingRanges() const
400         {
401             if( !maPendingRanges.count() )
402                 return;
403 
404             // use the specialized range clipper for the win
405             B2DPolyPolygon aCollectedRanges;
406             const bool bIsEmpty=isNullClipPoly();
407             const bool bIsCleared=!maClipPoly.count();
408             switch(mePendingOps)
409             {
410                 case UNION:
411                     OSL_ASSERT( !bIsCleared );
412 
413                     aCollectedRanges = maPendingRanges.solveCrossovers();
414                     aCollectedRanges = stripNeutralPolygons(aCollectedRanges);
415                     aCollectedRanges = stripDispensablePolygons(aCollectedRanges, false);
416                     if( bIsEmpty )
417                         maClipPoly = aCollectedRanges;
418                     else
419                         maClipPoly = tools::solvePolygonOperationOr(
420                             maClipPoly,
421                             aCollectedRanges);
422                     break;
423                 case INTERSECT:
424                     OSL_ASSERT( !bIsEmpty );
425 
426                     aCollectedRanges = maPendingRanges.solveCrossovers();
427                     aCollectedRanges = stripNeutralPolygons(aCollectedRanges);
428                     if( maPendingRanges.count() > 1 )
429                         aCollectedRanges = stripDispensablePolygons(aCollectedRanges, true);
430 
431                     if( bIsCleared )
432                         maClipPoly = aCollectedRanges;
433                     else
434                         maClipPoly = tools::solvePolygonOperationAnd(
435                             maClipPoly,
436                             aCollectedRanges);
437                     break;
438                 case XOR:
439                     aCollectedRanges = maPendingRanges.solveCrossovers();
440                     aCollectedRanges = stripNeutralPolygons(aCollectedRanges);
441                     aCollectedRanges = correctOrientations(aCollectedRanges);
442 
443                     if( bIsEmpty )
444                         maClipPoly = aCollectedRanges;
445                     else if( bIsCleared )
446                     {
447                         // not representable, strictly speaking,
448                         // using polygons with the common even/odd
449                         // or nonzero winding number fill rule. If
450                         // we'd want to represent it, fill rule
451                         // would need to be "non-negative winding
452                         // number" (and we then would return
453                         // 'holes' here)
454 
455                         // going for an ugly hack meanwhile
456                         maClipPoly = tools::solvePolygonOperationXor(
457                             B2DPolyPolygon(
458                                 tools::createPolygonFromRect(B2DRange(-1E20,-1E20,1E20,1E20))),
459                             aCollectedRanges);
460                     }
461                     else
462                         maClipPoly = tools::solvePolygonOperationXor(
463                             maClipPoly,
464                             aCollectedRanges);
465                     break;
466                 case SUBTRACT:
467                     OSL_ASSERT( !bIsEmpty );
468 
469                     // first union all pending ranges, subtract en bloc then
470                     aCollectedRanges = maPendingRanges.solveCrossovers();
471                     aCollectedRanges = stripNeutralPolygons(aCollectedRanges);
472                     aCollectedRanges = stripDispensablePolygons(aCollectedRanges, false);
473 
474                     if( bIsCleared )
475                     {
476                         // not representable, strictly speaking,
477                         // using polygons with the common even/odd
478                         // or nonzero winding number fill rule. If
479                         // we'd want to represent it, fill rule
480                         // would need to be "non-negative winding
481                         // number" (and we then would return
482                         // 'holes' here)
483 
484                         // going for an ugly hack meanwhile
485                         maClipPoly = tools::solvePolygonOperationDiff(
486                             B2DPolyPolygon(
487                                 tools::createPolygonFromRect(B2DRange(-1E20,-1E20,1E20,1E20))),
488                             aCollectedRanges);
489                     }
490                     else
491                         maClipPoly = tools::solvePolygonOperationDiff(
492                             maClipPoly,
493                             aCollectedRanges);
494                     break;
495             }
496 
497             maPendingRanges.clear();
498             mePendingOps = UNION;
499         }
500 
501         mutable B2DPolyPolygon maPendingPolygons;
502         mutable B2DPolyRange   maPendingRanges;
503         mutable B2DPolyPolygon maClipPoly;
504         mutable Operation      mePendingOps;
505     };
506 
507     B2DClipState::B2DClipState() :
508         mpImpl()
509     {}
510 
511     B2DClipState::~B2DClipState()
512     {}
513 
514     B2DClipState::B2DClipState( const B2DClipState& rOrig ) :
515         mpImpl(rOrig.mpImpl)
516     {}
517 
518     B2DClipState::B2DClipState( const B2DRange& rRange ) :
519         mpImpl( ImplB2DClipState(rRange) )
520     {}
521 
522     B2DClipState::B2DClipState( const B2DPolygon& rPoly ) :
523         mpImpl( ImplB2DClipState(rPoly) )
524     {}
525 
526     B2DClipState::B2DClipState( const B2DPolyPolygon& rPolyPoly ) :
527         mpImpl( ImplB2DClipState(rPolyPoly) )
528     {}
529 
530     B2DClipState& B2DClipState::operator=( const B2DClipState& rRHS )
531     {
532         mpImpl = rRHS.mpImpl;
533         return *this;
534     }
535 
536     void B2DClipState::makeUnique()
537     {
538         mpImpl.make_unique();
539     }
540 
541     void B2DClipState::makeNull()
542     {
543         mpImpl->makeNull();
544     }
545 
546     bool B2DClipState::isNull() const
547     {
548         return mpImpl->isNull();
549     }
550 
551     void B2DClipState::makeClear()
552     {
553         mpImpl->makeClear();
554     }
555 
556     bool B2DClipState::isCleared() const
557     {
558         return mpImpl->isCleared();
559     }
560 
561     bool B2DClipState::operator==(const B2DClipState& rRHS) const
562     {
563         if(mpImpl.same_object(rRHS.mpImpl))
564             return true;
565 
566         return ((*mpImpl) == (*rRHS.mpImpl));
567     }
568 
569     bool B2DClipState::operator!=(const B2DClipState& rRHS) const
570     {
571         return !(*this == rRHS);
572     }
573 
574     void B2DClipState::unionRange(const B2DRange& rRange)
575     {
576         mpImpl->unionRange(rRange);
577     }
578 
579     void B2DClipState::unionPolygon(const B2DPolygon& rPoly)
580     {
581         mpImpl->unionPolygon(rPoly);
582     }
583 
584     void B2DClipState::unionPolyPolygon(const B2DPolyPolygon& rPolyPoly)
585     {
586         mpImpl->unionPolyPolygon(rPolyPoly);
587     }
588 
589     void B2DClipState::unionClipState(const B2DClipState& rState)
590     {
591         mpImpl->unionClipState(*rState.mpImpl);
592     }
593 
594     void B2DClipState::intersectRange(const B2DRange& rRange)
595     {
596         mpImpl->intersectRange(rRange);
597     }
598 
599     void B2DClipState::intersectPolygon(const B2DPolygon& rPoly)
600     {
601         mpImpl->intersectPolygon(rPoly);
602     }
603 
604     void B2DClipState::intersectPolyPolygon(const B2DPolyPolygon& rPolyPoly)
605     {
606         mpImpl->intersectPolyPolygon(rPolyPoly);
607     }
608 
609     void B2DClipState::intersectClipState(const B2DClipState& rState)
610     {
611         mpImpl->intersectClipState(*rState.mpImpl);
612     }
613 
614     void B2DClipState::subtractRange(const B2DRange& rRange)
615     {
616         mpImpl->subtractRange(rRange);
617     }
618 
619     void B2DClipState::subtractPolygon(const B2DPolygon& rPoly)
620     {
621         mpImpl->subtractPolygon(rPoly);
622     }
623 
624     void B2DClipState::subtractPolyPolygon(const B2DPolyPolygon& rPolyPoly)
625     {
626         mpImpl->subtractPolyPolygon(rPolyPoly);
627     }
628 
629     void B2DClipState::subtractClipState(const B2DClipState& rState)
630     {
631         mpImpl->subtractClipState(*rState.mpImpl);
632     }
633 
634     void B2DClipState::xorRange(const B2DRange& rRange)
635     {
636         mpImpl->xorRange(rRange);
637     }
638 
639     void B2DClipState::xorPolygon(const B2DPolygon& rPoly)
640     {
641         mpImpl->xorPolygon(rPoly);
642     }
643 
644     void B2DClipState::xorPolyPolygon(const B2DPolyPolygon& rPolyPoly)
645     {
646         mpImpl->xorPolyPolygon(rPolyPoly);
647     }
648 
649     void B2DClipState::xorClipState(const B2DClipState& rState)
650     {
651         mpImpl->xorClipState(*rState.mpImpl);
652     }
653 
654     B2DPolyPolygon B2DClipState::getClipPoly() const
655     {
656         return mpImpl->getClipPoly();
657     }
658 
659 } // end of namespace tools
660 } // end of namespace basegfx
661 
662 // eof
663