basegfx/source/polygon/b2dpolypolygontools.cxx

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