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