basegfx/source/polygon/b2dpolypolygontools.cxx

   1 /* -*- Mode: C++; tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 4 -*- */
   2 /*
   3  * This file is part of the LibreOffice project.
   4  *
   5  * This Source Code Form is subject to the terms of the Mozilla Public
   6  * License, v. 2.0. If a copy of the MPL was not distributed with this
   7  * file, You can obtain one at http://mozilla.org/MPL/2.0/.
   8  *
   9  * This file incorporates work covered by the following license notice:
  10  *
  11  *   Licensed to the Apache Software Foundation (ASF) under one or more
  12  *   contributor license agreements. See the NOTICE file distributed
  13  *   with this work for additional information regarding copyright
  14  *   ownership. The ASF licenses this file to you under the Apache
  15  *   License, Version 2.0 (the "License"); you may not use this file
  16  *   except in compliance with the License. You may obtain a copy of
  17  *   the License at http://www.apache.org/licenses/LICENSE-2.0 .
  18  */
  19
  20 #include <basegfx/polygon/b2dpolypolygontools.hxx>
  21 #include <osl/diagnose.h>
  22 #include <basegfx/polygon/b2dpolypolygon.hxx>
  23 #include <basegfx/polygon/b2dpolygon.hxx>
  24 #include <basegfx/polygon/b2dpolygontools.hxx>
  25 #include <basegfx/numeric/ftools.hxx>
  26 #include <basegfx/polygon/b2dpolypolygoncutter.hxx>
  27
  28 #include <numeric>
  29
  30 //////////////////////////////////////////////////////////////////////////////
  31
  32 namespace basegfx
  33 {
  34     namespace tools
  35     {
  36         B2DPolyPolygon correctOrientations(const B2DPolyPolygon& rCandidate)
  37         {
  38             B2DPolyPolygon aRetval(rCandidate);
  39             const sal_uInt32 nCount(aRetval.count());
  40
  41             for(sal_uInt32 a(0L); a < nCount; a++)
  42             {
  43                 const B2DPolygon aCandidate(rCandidate.getB2DPolygon(a));
  44                 const B2VectorOrientation aOrientation(tools::getOrientation(aCandidate));
  45                 sal_uInt32 nDepth(0L);
  46
  47                 for(sal_uInt32 b(0L); b < nCount; b++)
  48                 {
  49                     if(b != a)
  50                     {
  51                         const B2DPolygon aCompare(rCandidate.getB2DPolygon(b));
  52
  53                         if(tools::isInside(aCompare, aCandidate, true))
  54                         {
  55                             nDepth++;
  56                         }
  57                     }
  58                 }
  59
  60                 const bool bShallBeHole(1L == (nDepth & 0x00000001));
  61                 const bool bIsHole(ORIENTATION_NEGATIVE == aOrientation);
  62
  63                 if(bShallBeHole != bIsHole && ORIENTATION_NEUTRAL != aOrientation)
  64                 {
  65                     B2DPolygon aFlipped(aCandidate);
  66                     aFlipped.flip();
  67                     aRetval.setB2DPolygon(a, aFlipped);
  68                 }
  69             }
  70
  71             return aRetval;
  72         }
  73
  74         B2DPolyPolygon correctOutmostPolygon(const B2DPolyPolygon& rCandidate)
  75         {
  76             const sal_uInt32 nCount(rCandidate.count());
  77
  78             if(nCount > 1L)
  79             {
  80                 for(sal_uInt32 a(0L); a < nCount; a++)
  81                 {
  82                     const B2DPolygon aCandidate(rCandidate.getB2DPolygon(a));
  83                     sal_uInt32 nDepth(0L);
  84
  85                     for(sal_uInt32 b(0L); b < nCount; b++)
  86                     {
  87                         if(b != a)
  88                         {
  89                             const B2DPolygon aCompare(rCandidate.getB2DPolygon(b));
  90
  91                             if(tools::isInside(aCompare, aCandidate, true))
  92                             {
  93                                 nDepth++;
  94                             }
  95                         }
  96                     }
  97
  98                     if(!nDepth)
  99                     {
 100                         B2DPolyPolygon aRetval(rCandidate);
 101
 102                         if(a != 0L)
 103                         {
 104                             // exchange polygon a and polygon 0L
 105                             aRetval.setB2DPolygon(0L, aCandidate);
 106                             aRetval.setB2DPolygon(a, rCandidate.getB2DPolygon(0L));
 107                         }
 108
 109                         // exit
 110                         return aRetval;
 111                     }
 112                 }
 113             }
 114
 115             return rCandidate;
 116         }
 117
 118         B2DPolyPolygon adaptiveSubdivideByDistance(const B2DPolyPolygon& rCandidate, double fDistanceBound)
 119         {
 120             if(rCandidate.areControlPointsUsed())
 121             {
 122                 const sal_uInt32 nPolygonCount(rCandidate.count());
 123                 B2DPolyPolygon aRetval;
 124
 125                 for(sal_uInt32 a(0L); a < nPolygonCount; a++)
 126                 {
 127                     const B2DPolygon aCandidate(rCandidate.getB2DPolygon(a));
 128
 129                     if(aCandidate.areControlPointsUsed())
 130                     {
 131                         aRetval.append(tools::adaptiveSubdivideByDistance(aCandidate, fDistanceBound));
 132                     }
 133                     else
 134                     {
 135                         aRetval.append(aCandidate);
 136                     }
 137                 }
 138
 139                 return aRetval;
 140             }
 141             else
 142             {
 143                 return rCandidate;
 144             }
 145         }
 146
 147         B2DPolyPolygon adaptiveSubdivideByAngle(const B2DPolyPolygon& rCandidate, double fAngleBound)
 148         {
 149             if(rCandidate.areControlPointsUsed())
 150             {
 151                 const sal_uInt32 nPolygonCount(rCandidate.count());
 152                 B2DPolyPolygon aRetval;
 153
 154                 for(sal_uInt32 a(0L); a < nPolygonCount; a++)
 155                 {
 156                     const B2DPolygon aCandidate(rCandidate.getB2DPolygon(a));
 157
 158                     if(aCandidate.areControlPointsUsed())
 159                     {
 160                         aRetval.append(tools::adaptiveSubdivideByAngle(aCandidate, fAngleBound));
 161                     }
 162                     else
 163                     {
 164                         aRetval.append(aCandidate);
 165                     }
 166                 }
 167
 168                 return aRetval;
 169             }
 170             else
 171             {
 172                 return rCandidate;
 173             }
 174         }
 175
 176         B2DPolyPolygon adaptiveSubdivideByCount(const B2DPolyPolygon& rCandidate, sal_uInt32 nCount)
 177         {
 178             if(rCandidate.areControlPointsUsed())
 179             {
 180                 const sal_uInt32 nPolygonCount(rCandidate.count());
 181                 B2DPolyPolygon aRetval;
 182
 183                 for(sal_uInt32 a(0L); a < nPolygonCount; a++)
 184                 {
 185                     const B2DPolygon aCandidate(rCandidate.getB2DPolygon(a));
 186
 187                     if(aCandidate.areControlPointsUsed())
 188                     {
 189                         aRetval.append(tools::adaptiveSubdivideByCount(aCandidate, nCount));
 190                     }
 191                     else
 192                     {
 193                         aRetval.append(aCandidate);
 194                     }
 195                 }
 196
 197                 return aRetval;
 198             }
 199             else
 200             {
 201                 return rCandidate;
 202             }
 203         }
 204
 205         bool isInside(const B2DPolyPolygon& rCandidate, const B2DPoint& rPoint, bool bWithBorder)
 206         {
 207             const sal_uInt32 nPolygonCount(rCandidate.count());
 208
 209             if(1L == nPolygonCount)
 210             {
 211                 return isInside(rCandidate.getB2DPolygon(0L), rPoint, bWithBorder);
 212             }
 213             else
 214             {
 215                 sal_Int32 nInsideCount(0L);
 216
 217                 for(sal_uInt32 a(0L); a < nPolygonCount; a++)
 218                 {
 219                     const B2DPolygon aPolygon(rCandidate.getB2DPolygon(a));
 220                     const bool bInside(isInside(aPolygon, rPoint, bWithBorder));
 221
 222                     if(bInside)
 223                     {
 224                         nInsideCount++;
 225                     }
 226                 }
 227
 228                 return (nInsideCount % 2L);
 229             }
 230         }
 231
 232         B2DRange getRange(const B2DPolyPolygon& rCandidate)
 233         {
 234             B2DRange aRetval;
 235             const sal_uInt32 nPolygonCount(rCandidate.count());
 236
 237             for(sal_uInt32 a(0L); a < nPolygonCount; a++)
 238             {
 239                 B2DPolygon aCandidate = rCandidate.getB2DPolygon(a);
 240                 aRetval.expand(tools::getRange(aCandidate));
 241             }
 242
 243             return aRetval;
 244         }
 245
 246         void applyLineDashing(const B2DPolyPolygon& rCandidate, const ::std::vector<double>& rDotDashArray, B2DPolyPolygon* pLineTarget, B2DPolyPolygon* pGapTarget, double fFullDashDotLen)
 247         {
 248             if(0.0 == fFullDashDotLen && rDotDashArray.size())
 249             {
 250                 // calculate fFullDashDotLen from rDotDashArray
 251                 fFullDashDotLen = ::std::accumulate(rDotDashArray.begin(), rDotDashArray.end(), 0.0);
 252             }
 253
 254             if(rCandidate.count() && fFullDashDotLen > 0.0)
 255             {
 256                 B2DPolyPolygon aLineTarget, aGapTarget;
 257
 258                 for(sal_uInt32 a(0L); a < rCandidate.count(); a++)
 259                 {
 260                     const B2DPolygon aCandidate(rCandidate.getB2DPolygon(a));
 261
 262                     applyLineDashing(
 263                         aCandidate,
 264                         rDotDashArray,
 265                         pLineTarget ? &aLineTarget : 0,
 266                         pGapTarget ? &aGapTarget : 0,
 267                         fFullDashDotLen);
 268
 269                     if(pLineTarget)
 270                     {
 271                         pLineTarget->append(aLineTarget);
 272                     }
 273
 274                     if(pGapTarget)
 275                     {
 276                         pGapTarget->append(aGapTarget);
 277                     }
 278                 }
 279             }
 280         }
 281
 282         bool isInEpsilonRange(const B2DPolyPolygon& rCandidate, const B2DPoint& rTestPosition, double fDistance)
 283         {
 284             const sal_uInt32 nPolygonCount(rCandidate.count());
 285
 286             for(sal_uInt32 a(0L); a < nPolygonCount; a++)
 287             {
 288                 B2DPolygon aCandidate(rCandidate.getB2DPolygon(a));
 289
 290                 if(isInEpsilonRange(aCandidate, rTestPosition, fDistance))
 291                 {
 292                     return true;
 293                 }
 294             }
 295
 296             return false;
 297         }
 298
 299         B3DPolyPolygon createB3DPolyPolygonFromB2DPolyPolygon(const B2DPolyPolygon& rCandidate, double fZCoordinate)
 300         {
 301             const sal_uInt32 nPolygonCount(rCandidate.count());
 302             B3DPolyPolygon aRetval;
 303
 304             for(sal_uInt32 a(0L); a < nPolygonCount; a++)
 305             {
 306                 B2DPolygon aCandidate(rCandidate.getB2DPolygon(a));
 307
 308                 aRetval.append(createB3DPolygonFromB2DPolygon(aCandidate, fZCoordinate));
 309             }
 310
 311             return aRetval;
 312         }
 313
 314         B2DPolyPolygon createB2DPolyPolygonFromB3DPolyPolygon(const B3DPolyPolygon& rCandidate, const B3DHomMatrix& rMat)
 315         {
 316             const sal_uInt32 nPolygonCount(rCandidate.count());
 317             B2DPolyPolygon aRetval;
 318
 319             for(sal_uInt32 a(0L); a < nPolygonCount; a++)
 320             {
 321                 B3DPolygon aCandidate(rCandidate.getB3DPolygon(a));
 322
 323                 aRetval.append(createB2DPolygonFromB3DPolygon(aCandidate, rMat));
 324             }
 325
 326             return aRetval;
 327         }
 328
 329         double getSmallestDistancePointToPolyPolygon(const B2DPolyPolygon& rCandidate, const B2DPoint& rTestPoint, sal_uInt32& rPolygonIndex, sal_uInt32& rEdgeIndex, double& rCut)
 330         {
 331             double fRetval(DBL_MAX);
 332             const double fZero(0.0);
 333             const sal_uInt32 nPolygonCount(rCandidate.count());
 334
 335             for(sal_uInt32 a(0L); a < nPolygonCount; a++)
 336             {
 337                 const B2DPolygon aCandidate(rCandidate.getB2DPolygon(a));
 338                 sal_uInt32 nNewEdgeIndex;
 339                 double fNewCut;
 340                 const double fNewDistance(getSmallestDistancePointToPolygon(aCandidate, rTestPoint, nNewEdgeIndex, fNewCut));
 341
 342                 if(DBL_MAX == fRetval || fNewDistance < fRetval)
 343                 {
 344                     fRetval = fNewDistance;
 345                     rPolygonIndex = a;
 346                     rEdgeIndex = nNewEdgeIndex;
 347                     rCut = fNewCut;
 348
 349                     if(fTools::equal(fRetval, fZero))
 350                     {
 351                         // already found zero distance, cannot get better. Ensure numerical zero value and end loop.
 352                         fRetval = 0.0;
 353                         break;
 354                     }
 355                 }
 356             }
 357
 358             return fRetval;
 359         }
 360
 361         B2DPolyPolygon distort(const B2DPolyPolygon& rCandidate, const B2DRange& rOriginal, const B2DPoint& rTopLeft, const B2DPoint& rTopRight, const B2DPoint& rBottomLeft, const B2DPoint& rBottomRight)
 362         {
 363             const sal_uInt32 nPolygonCount(rCandidate.count());
 364             B2DPolyPolygon aRetval;
 365
 366             for(sal_uInt32 a(0L); a < nPolygonCount; a++)
 367             {
 368                 const B2DPolygon aCandidate(rCandidate.getB2DPolygon(a));
 369
 370                 aRetval.append(distort(aCandidate, rOriginal, rTopLeft, rTopRight, rBottomLeft, rBottomRight));
 371             }
 372
 373             return aRetval;
 374         }
 375
 376         B2DPolyPolygon expandToCurve(const B2DPolyPolygon& rCandidate)
 377         {
 378             const sal_uInt32 nPolygonCount(rCandidate.count());
 379             B2DPolyPolygon aRetval;
 380
 381             for(sal_uInt32 a(0L); a < nPolygonCount; a++)
 382             {
 383                 const B2DPolygon aCandidate(rCandidate.getB2DPolygon(a));
 384
 385                 aRetval.append(expandToCurve(aCandidate));
 386             }
 387
 388             return aRetval;
 389         }
 390
 391         B2DPolyPolygon growInNormalDirection(const B2DPolyPolygon& rCandidate, double fValue)
 392         {
 393             if(0.0 != fValue)
 394             {
 395                 B2DPolyPolygon aRetval;
 396
 397                 for(sal_uInt32 a(0L); a < rCandidate.count(); a++)
 398                 {
 399                     aRetval.append(growInNormalDirection(rCandidate.getB2DPolygon(a), fValue));
 400                 }
 401
 402                 return aRetval;
 403             }
 404             else
 405             {
 406                 return rCandidate;
 407             }
 408         }
 409
 410         void correctGrowShrinkPolygonPair(SAL_UNUSED_PARAMETER B2DPolyPolygon& /*rOriginal*/, SAL_UNUSED_PARAMETER B2DPolyPolygon& /*rGrown*/)
 411         {
 412             //TODO!
 413         }
 414
 415         B2DPolyPolygon reSegmentPolyPolygon(const B2DPolyPolygon& rCandidate, sal_uInt32 nSegments)
 416         {
 417             B2DPolyPolygon aRetval;
 418
 419             for(sal_uInt32 a(0L); a < rCandidate.count(); a++)
 420             {
 421                 aRetval.append(reSegmentPolygon(rCandidate.getB2DPolygon(a), nSegments));
 422             }
 423
 424             return aRetval;
 425         }
 426
 427         B2DPolyPolygon interpolate(const B2DPolyPolygon& rOld1, const B2DPolyPolygon& rOld2, double t)
 428         {
 429             OSL_ENSURE(rOld1.count() == rOld2.count(), "B2DPolyPolygon interpolate: Different geometry (!)");
 430             B2DPolyPolygon aRetval;
 431
 432             for(sal_uInt32 a(0L); a < rOld1.count(); a++)
 433             {
 434                 aRetval.append(interpolate(rOld1.getB2DPolygon(a), rOld2.getB2DPolygon(a), t));
 435             }
 436
 437             return aRetval;
 438         }
 439
 440         bool isRectangle( const B2DPolyPolygon& rPoly )
 441         {
 442             // exclude some cheap cases first
 443             if( rPoly.count() != 1 )
 444                 return false;
 445
 446             return isRectangle( rPoly.getB2DPolygon(0) );
 447         }
 448
 449         // #i76891#
 450         B2DPolyPolygon simplifyCurveSegments(const B2DPolyPolygon& rCandidate)
 451         {
 452             if(rCandidate.areControlPointsUsed())
 453             {
 454                 B2DPolyPolygon aRetval;
 455
 456                 for(sal_uInt32 a(0L); a < rCandidate.count(); a++)
 457                 {
 458                     aRetval.append(simplifyCurveSegments(rCandidate.getB2DPolygon(a)));
 459                 }
 460
 461                 return aRetval;
 462             }
 463             else
 464             {
 465                 return rCandidate;
 466             }
 467         }
 468
 469         B2DPolyPolygon snapPointsOfHorizontalOrVerticalEdges(const B2DPolyPolygon& rCandidate)
 470         {
 471             B2DPolyPolygon aRetval;
 472
 473             for(sal_uInt32 a(0L); a < rCandidate.count(); a++)
 474             {
 475                 aRetval.append(snapPointsOfHorizontalOrVerticalEdges(rCandidate.getB2DPolygon(a)));
 476             }
 477
 478             return aRetval;
 479         }
 480
 481     } // end of namespace tools
 482 } // end of namespace basegfx
 483
 484 /* vim:set shiftwidth=4 softtabstop=4 expandtab: */