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