basegfx/source/polygon/b2dpolypolygontools.cxx

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