xref: /AOO41X/main/basegfx/source/polygon/b2dpolypolygontools.cxx (revision ff0525f24f03981d56b7579b645949f111420994) 
1 /**************************************************************
2  *
3  * Licensed to the Apache Software Foundation (ASF) under one
4  * or more contributor license agreements.  See the NOTICE file
5  * distributed with this work for additional information
6  * regarding copyright ownership.  The ASF licenses this file
7  * to you under the Apache License, Version 2.0 (the
8  * "License"); you may not use this file except in compliance
9  * with the License.  You may obtain a copy of the License at
10  *
11  *   http://www.apache.org/licenses/LICENSE-2.0
12  *
13  * Unless required by applicable law or agreed to in writing,
14  * software distributed under the License is distributed on an
15  * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
16  * KIND, either express or implied.  See the License for the
17  * specific language governing permissions and limitations
18  * under the License.
19  *
20  *************************************************************/
21 
22 
23 
24 // MARKER(update_precomp.py): autogen include statement, do not remove
25 #include "precompiled_basegfx.hxx"
26 #include <basegfx/polygon/b2dpolypolygontools.hxx>
27 #include <osl/diagnose.h>
28 #include <basegfx/polygon/b2dpolypolygon.hxx>
29 #include <basegfx/polygon/b2dpolygon.hxx>
30 #include <basegfx/polygon/b2dpolygontools.hxx>
31 #include <basegfx/numeric/ftools.hxx>
32 #include <basegfx/polygon/b2dpolypolygoncutter.hxx>
33 
34 #include <numeric>
35 
36 //////////////////////////////////////////////////////////////////////////////
37 
38 namespace basegfx
39 {
40     namespace tools
41     {
42         B2DPolyPolygon correctOrientations(const B2DPolyPolygon& rCandidate)
43         {
44             B2DPolyPolygon aRetval(rCandidate);
45             const sal_uInt32 nCount(aRetval.count());
46 
47             for(sal_uInt32 a(0L); a < nCount; a++)
48             {
49                 const B2DPolygon aCandidate(rCandidate.getB2DPolygon(a));
50                 const B2VectorOrientation aOrientation(tools::getOrientation(aCandidate));
51                 sal_uInt32 nDepth(0L);
52 
53                 for(sal_uInt32 b(0L); b < nCount; b++)
54                 {
55                     if(b != a)
56                     {
57                         const B2DPolygon aCompare(rCandidate.getB2DPolygon(b));
58 
59                         if(tools::isInside(aCompare, aCandidate, true))
60                         {
61                             nDepth++;
62                         }
63                     }
64                 }
65 
66                 const bool bShallBeHole(1L == (nDepth & 0x00000001));
67                 const bool bIsHole(ORIENTATION_NEGATIVE == aOrientation);
68 
69                 if(bShallBeHole != bIsHole && ORIENTATION_NEUTRAL != aOrientation)
70                 {
71                     B2DPolygon aFlipped(aCandidate);
72                     aFlipped.flip();
73                     aRetval.setB2DPolygon(a, aFlipped);
74                 }
75             }
76 
77             return aRetval;
78         }
79 
80         B2DPolyPolygon correctOutmostPolygon(const B2DPolyPolygon& rCandidate)
81         {
82             const sal_uInt32 nCount(rCandidate.count());
83 
84             if(nCount > 1L)
85             {
86                 for(sal_uInt32 a(0L); a < nCount; a++)
87                 {
88                     const B2DPolygon aCandidate(rCandidate.getB2DPolygon(a));
89                     sal_uInt32 nDepth(0L);
90 
91                     for(sal_uInt32 b(0L); b < nCount; b++)
92                     {
93                         if(b != a)
94                         {
95                             const B2DPolygon aCompare(rCandidate.getB2DPolygon(b));
96 
97                             if(tools::isInside(aCompare, aCandidate, true))
98                             {
99                                 nDepth++;
100                             }
101                         }
102                     }
103 
104                     if(!nDepth)
105                     {
106                         B2DPolyPolygon aRetval(rCandidate);
107 
108                         if(a != 0L)
109                         {
110                             // exchange polygon a and polygon 0L
111                             aRetval.setB2DPolygon(0L, aCandidate);
112                             aRetval.setB2DPolygon(a, rCandidate.getB2DPolygon(0L));
113                         }
114 
115                         // exit
116                         return aRetval;
117                     }
118                 }
119             }
120 
121             return rCandidate;
122         }
123 
124         B2DPolyPolygon adaptiveSubdivideByDistance(const B2DPolyPolygon& rCandidate, double fDistanceBound)
125         {
126             if(rCandidate.areControlPointsUsed())
127             {
128                 const sal_uInt32 nPolygonCount(rCandidate.count());
129                 B2DPolyPolygon aRetval;
130 
131                 for(sal_uInt32 a(0L); a < nPolygonCount; a++)
132                 {
133                     const B2DPolygon aCandidate(rCandidate.getB2DPolygon(a));
134 
135                     if(aCandidate.areControlPointsUsed())
136                     {
137                         aRetval.append(tools::adaptiveSubdivideByDistance(aCandidate, fDistanceBound));
138                     }
139                     else
140                     {
141                         aRetval.append(aCandidate);
142                     }
143                 }
144 
145                 return aRetval;
146             }
147             else
148             {
149                 return rCandidate;
150             }
151         }
152 
153         B2DPolyPolygon adaptiveSubdivideByAngle(const B2DPolyPolygon& rCandidate, double fAngleBound)
154         {
155             if(rCandidate.areControlPointsUsed())
156             {
157                 const sal_uInt32 nPolygonCount(rCandidate.count());
158                 B2DPolyPolygon aRetval;
159 
160                 for(sal_uInt32 a(0L); a < nPolygonCount; a++)
161                 {
162                     const B2DPolygon aCandidate(rCandidate.getB2DPolygon(a));
163 
164                     if(aCandidate.areControlPointsUsed())
165                     {
166                         aRetval.append(tools::adaptiveSubdivideByAngle(aCandidate, fAngleBound));
167                     }
168                     else
169                     {
170                         aRetval.append(aCandidate);
171                     }
172                 }
173 
174                 return aRetval;
175             }
176             else
177             {
178                 return rCandidate;
179             }
180         }
181 
182         B2DPolyPolygon adaptiveSubdivideByCount(const B2DPolyPolygon& rCandidate, sal_uInt32 nCount)
183         {
184             if(rCandidate.areControlPointsUsed())
185             {
186                 const sal_uInt32 nPolygonCount(rCandidate.count());
187                 B2DPolyPolygon aRetval;
188 
189                 for(sal_uInt32 a(0L); a < nPolygonCount; a++)
190                 {
191                     const B2DPolygon aCandidate(rCandidate.getB2DPolygon(a));
192 
193                     if(aCandidate.areControlPointsUsed())
194                     {
195                         aRetval.append(tools::adaptiveSubdivideByCount(aCandidate, nCount));
196                     }
197                     else
198                     {
199                         aRetval.append(aCandidate);
200                     }
201                 }
202 
203                 return aRetval;
204             }
205             else
206             {
207                 return rCandidate;
208             }
209         }
210 
211         bool isInside(const B2DPolyPolygon& rCandidate, const B2DPoint& rPoint, bool bWithBorder)
212         {
213             const sal_uInt32 nPolygonCount(rCandidate.count());
214 
215             if(1L == nPolygonCount)
216             {
217                 return isInside(rCandidate.getB2DPolygon(0L), rPoint, bWithBorder);
218             }
219             else
220             {
221                 sal_Int32 nInsideCount(0L);
222 
223                 for(sal_uInt32 a(0L); a < nPolygonCount; a++)
224                 {
225                     const B2DPolygon aPolygon(rCandidate.getB2DPolygon(a));
226                     const bool bInside(isInside(aPolygon, rPoint, bWithBorder));
227 
228                     if(bInside)
229                     {
230                         nInsideCount++;
231                     }
232                 }
233 
234                 return (nInsideCount % 2L);
235             }
236         }
237 
238         B2DRange getRangeWithControlPoints(const B2DPolyPolygon& rCandidate)
239         {
240             B2DRange aRetval;
241             const sal_uInt32 nPolygonCount(rCandidate.count());
242 
243             for(sal_uInt32 a(0L); a < nPolygonCount; a++)
244             {
245                 B2DPolygon aCandidate = rCandidate.getB2DPolygon(a);
246                 aRetval.expand(tools::getRangeWithControlPoints(aCandidate));
247             }
248 
249             return aRetval;
250         }
251 
252         B2DRange getRange(const B2DPolyPolygon& rCandidate)
253         {
254             B2DRange aRetval;
255             const sal_uInt32 nPolygonCount(rCandidate.count());
256 
257             for(sal_uInt32 a(0L); a < nPolygonCount; a++)
258             {
259                 B2DPolygon aCandidate = rCandidate.getB2DPolygon(a);
260                 aRetval.expand(tools::getRange(aCandidate));
261             }
262 
263             return aRetval;
264         }
265 
266         double getSignedArea(const B2DPolyPolygon& rCandidate)
267         {
268             double fRetval(0.0);
269             const sal_uInt32 nPolygonCount(rCandidate.count());
270 
271             for(sal_uInt32 a(0L); a < nPolygonCount; a++)
272             {
273                 const B2DPolygon aCandidate(rCandidate.getB2DPolygon(a));
274 
275                 fRetval += tools::getSignedArea(aCandidate);
276             }
277 
278             return fRetval;
279         }
280 
281         double getArea(const B2DPolyPolygon& rCandidate)
282         {
283             return fabs(getSignedArea(rCandidate));
284         }
285 
286         void applyLineDashing(const B2DPolyPolygon& rCandidate, const ::std::vector<double>& rDotDashArray, B2DPolyPolygon* pLineTarget, B2DPolyPolygon* pGapTarget, double fFullDashDotLen)
287         {
288             if(0.0 == fFullDashDotLen && rDotDashArray.size())
289             {
290                 // calculate fFullDashDotLen from rDotDashArray
291                 fFullDashDotLen = ::std::accumulate(rDotDashArray.begin(), rDotDashArray.end(), 0.0);
292             }
293 
294             if(rCandidate.count() && fFullDashDotLen > 0.0)
295             {
296                 B2DPolyPolygon aLineTarget, aGapTarget;
297 
298                 for(sal_uInt32 a(0L); a < rCandidate.count(); a++)
299                 {
300                     const B2DPolygon aCandidate(rCandidate.getB2DPolygon(a));
301 
302                     applyLineDashing(
303                         aCandidate,
304                         rDotDashArray,
305                         pLineTarget ? &aLineTarget : 0,
306                         pGapTarget ? &aGapTarget : 0,
307                         fFullDashDotLen);
308 
309                     if(pLineTarget)
310                     {
311                         pLineTarget->append(aLineTarget);
312                     }
313 
314                     if(pGapTarget)
315                     {
316                         pGapTarget->append(aGapTarget);
317                     }
318                 }
319             }
320         }
321 
322         bool isInEpsilonRange(const B2DPolyPolygon& rCandidate, const B2DPoint& rTestPosition, double fDistance)
323         {
324             const sal_uInt32 nPolygonCount(rCandidate.count());
325 
326             for(sal_uInt32 a(0L); a < nPolygonCount; a++)
327             {
328                 B2DPolygon aCandidate(rCandidate.getB2DPolygon(a));
329 
330                 if(isInEpsilonRange(aCandidate, rTestPosition, fDistance))
331                 {
332                     return true;
333                 }
334             }
335 
336             return false;
337         }
338 
339         B3DPolyPolygon createB3DPolyPolygonFromB2DPolyPolygon(const B2DPolyPolygon& rCandidate, double fZCoordinate)
340         {
341             const sal_uInt32 nPolygonCount(rCandidate.count());
342             B3DPolyPolygon aRetval;
343 
344             for(sal_uInt32 a(0L); a < nPolygonCount; a++)
345             {
346                 B2DPolygon aCandidate(rCandidate.getB2DPolygon(a));
347 
348                 aRetval.append(createB3DPolygonFromB2DPolygon(aCandidate, fZCoordinate));
349             }
350 
351             return aRetval;
352         }
353 
354         B2DPolyPolygon createB2DPolyPolygonFromB3DPolyPolygon(const B3DPolyPolygon& rCandidate, const B3DHomMatrix& rMat)
355         {
356             const sal_uInt32 nPolygonCount(rCandidate.count());
357             B2DPolyPolygon aRetval;
358 
359             for(sal_uInt32 a(0L); a < nPolygonCount; a++)
360             {
361                 B3DPolygon aCandidate(rCandidate.getB3DPolygon(a));
362 
363                 aRetval.append(createB2DPolygonFromB3DPolygon(aCandidate, rMat));
364             }
365 
366             return aRetval;
367         }
368 
369         double getSmallestDistancePointToPolyPolygon(const B2DPolyPolygon& rCandidate, const B2DPoint& rTestPoint, sal_uInt32& rPolygonIndex, sal_uInt32& rEdgeIndex, double& rCut)
370         {
371             double fRetval(DBL_MAX);
372             const double fZero(0.0);
373             const sal_uInt32 nPolygonCount(rCandidate.count());
374 
375             for(sal_uInt32 a(0L); a < nPolygonCount; a++)
376             {
377                 const B2DPolygon aCandidate(rCandidate.getB2DPolygon(a));
378                 sal_uInt32 nNewEdgeIndex;
379                 double fNewCut;
380                 const double fNewDistance(getSmallestDistancePointToPolygon(aCandidate, rTestPoint, nNewEdgeIndex, fNewCut));
381 
382                 if(DBL_MAX == fRetval || fNewDistance < fRetval)
383                 {
384                     fRetval = fNewDistance;
385                     rPolygonIndex = a;
386                     rEdgeIndex = nNewEdgeIndex;
387                     rCut = fNewCut;
388 
389                     if(fTools::equal(fRetval, fZero))
390                     {
391                         // already found zero distance, cannot get better. Ensure numerical zero value and end loop.
392                         fRetval = 0.0;
393                         break;
394                     }
395                 }
396             }
397 
398             return fRetval;
399         }
400 
401         B2DPolyPolygon distort(const B2DPolyPolygon& rCandidate, const B2DRange& rOriginal, const B2DPoint& rTopLeft, const B2DPoint& rTopRight, const B2DPoint& rBottomLeft, const B2DPoint& rBottomRight)
402         {
403             const sal_uInt32 nPolygonCount(rCandidate.count());
404             B2DPolyPolygon aRetval;
405 
406             for(sal_uInt32 a(0L); a < nPolygonCount; a++)
407             {
408                 const B2DPolygon aCandidate(rCandidate.getB2DPolygon(a));
409 
410                 aRetval.append(distort(aCandidate, rOriginal, rTopLeft, rTopRight, rBottomLeft, rBottomRight));
411             }
412 
413             return aRetval;
414         }
415 
416         B2DPolyPolygon rotateAroundPoint(const B2DPolyPolygon& rCandidate, const B2DPoint& rCenter, double fAngle)
417         {
418             const sal_uInt32 nPolygonCount(rCandidate.count());
419             B2DPolyPolygon aRetval;
420 
421             for(sal_uInt32 a(0L); a < nPolygonCount; a++)
422             {
423                 const B2DPolygon aCandidate(rCandidate.getB2DPolygon(a));
424 
425                 aRetval.append(rotateAroundPoint(aCandidate, rCenter, fAngle));
426             }
427 
428             return aRetval;
429         }
430 
431         B2DPolyPolygon expandToCurve(const B2DPolyPolygon& rCandidate)
432         {
433             const sal_uInt32 nPolygonCount(rCandidate.count());
434             B2DPolyPolygon aRetval;
435 
436             for(sal_uInt32 a(0L); a < nPolygonCount; a++)
437             {
438                 const B2DPolygon aCandidate(rCandidate.getB2DPolygon(a));
439 
440                 aRetval.append(expandToCurve(aCandidate));
441             }
442 
443             return aRetval;
444         }
445 
446         B2DPolyPolygon setContinuity(const B2DPolyPolygon& rCandidate, B2VectorContinuity eContinuity)
447         {
448             if(rCandidate.areControlPointsUsed())
449             {
450                 const sal_uInt32 nPolygonCount(rCandidate.count());
451                 B2DPolyPolygon aRetval;
452 
453                 for(sal_uInt32 a(0L); a < nPolygonCount; a++)
454                 {
455                     const B2DPolygon aCandidate(rCandidate.getB2DPolygon(a));
456 
457                     aRetval.append(setContinuity(aCandidate, eContinuity));
458                 }
459 
460                 return aRetval;
461             }
462             else
463             {
464                 return rCandidate;
465             }
466         }
467 
468         B2DPolyPolygon growInNormalDirection(const B2DPolyPolygon& rCandidate, double fValue)
469         {
470             if(0.0 != fValue)
471             {
472                 B2DPolyPolygon aRetval;
473 
474                 for(sal_uInt32 a(0L); a < rCandidate.count(); a++)
475                 {
476                     aRetval.append(growInNormalDirection(rCandidate.getB2DPolygon(a), fValue));
477                 }
478 
479                 return aRetval;
480             }
481             else
482             {
483                 return rCandidate;
484             }
485         }
486 
487         void correctGrowShrinkPolygonPair(B2DPolyPolygon& /*rOriginal*/, B2DPolyPolygon& /*rGrown*/)
488         {
489         }
490 
491         B2DPolyPolygon reSegmentPolyPolygon(const B2DPolyPolygon& rCandidate, sal_uInt32 nSegments)
492         {
493             B2DPolyPolygon aRetval;
494 
495             for(sal_uInt32 a(0L); a < rCandidate.count(); a++)
496             {
497                 aRetval.append(reSegmentPolygon(rCandidate.getB2DPolygon(a), nSegments));
498             }
499 
500             return aRetval;
501         }
502 
503         B2DPolyPolygon interpolate(const B2DPolyPolygon& rOld1, const B2DPolyPolygon& rOld2, double t)
504         {
505             OSL_ENSURE(rOld1.count() == rOld2.count(), "B2DPolyPolygon interpolate: Different geometry (!)");
506             B2DPolyPolygon aRetval;
507 
508             for(sal_uInt32 a(0L); a < rOld1.count(); a++)
509             {
510                 aRetval.append(interpolate(rOld1.getB2DPolygon(a), rOld2.getB2DPolygon(a), t));
511             }
512 
513             return aRetval;
514         }
515 
516         bool isRectangle( const B2DPolyPolygon& rPoly )
517         {
518             // exclude some cheap cases first
519             if( rPoly.count() != 1 )
520                 return false;
521 
522             return isRectangle( rPoly.getB2DPolygon(0) );
523         }
524 
525         // #i76891#
526         B2DPolyPolygon simplifyCurveSegments(const B2DPolyPolygon& rCandidate)
527         {
528             if(rCandidate.areControlPointsUsed())
529             {
530                 B2DPolyPolygon aRetval;
531 
532                 for(sal_uInt32 a(0L); a < rCandidate.count(); a++)
533                 {
534                     aRetval.append(simplifyCurveSegments(rCandidate.getB2DPolygon(a)));
535                 }
536 
537                 return aRetval;
538             }
539             else
540             {
541                 return rCandidate;
542             }
543         }
544 
545         B2DPolyPolygon reSegmentPolyPolygonEdges(const B2DPolyPolygon& rCandidate, sal_uInt32 nSubEdges, bool bHandleCurvedEdges, bool bHandleStraightEdges)
546         {
547             B2DPolyPolygon aRetval;
548 
549             for(sal_uInt32 a(0L); a < rCandidate.count(); a++)
550             {
551                 aRetval.append(reSegmentPolygonEdges(rCandidate.getB2DPolygon(a), nSubEdges, bHandleCurvedEdges, bHandleStraightEdges));
552             }
553 
554             return aRetval;
555         }
556 
557         //////////////////////////////////////////////////////////////////////
558         // comparators with tolerance for 2D PolyPolygons
559 
560         bool equal(const B2DPolyPolygon& rCandidateA, const B2DPolyPolygon& rCandidateB, const double& rfSmallValue)
561         {
562             const sal_uInt32 nPolygonCount(rCandidateA.count());
563 
564             if(nPolygonCount != rCandidateB.count())
565                 return false;
566 
567             for(sal_uInt32 a(0); a < nPolygonCount; a++)
568             {
569                 const B2DPolygon aCandidate(rCandidateA.getB2DPolygon(a));
570 
571                 if(!equal(aCandidate, rCandidateB.getB2DPolygon(a), rfSmallValue))
572                     return false;
573             }
574 
575             return true;
576         }
577 
578         bool equal(const B2DPolyPolygon& rCandidateA, const B2DPolyPolygon& rCandidateB)
579         {
580             const double fSmallValue(fTools::getSmallValue());
581 
582             return equal(rCandidateA, rCandidateB, fSmallValue);
583         }
584 
585         B2DPolyPolygon snapPointsOfHorizontalOrVerticalEdges(const B2DPolyPolygon& rCandidate)
586         {
587             B2DPolyPolygon aRetval;
588 
589             for(sal_uInt32 a(0L); a < rCandidate.count(); a++)
590             {
591                 aRetval.append(snapPointsOfHorizontalOrVerticalEdges(rCandidate.getB2DPolygon(a)));
592             }
593 
594             return aRetval;
595         }
596 
597     } // end of namespace tools
598 } // end of namespace basegfx
599 
600 //////////////////////////////////////////////////////////////////////////////
601 // eof
602