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 <com/sun/star/drawing/PolyPolygonBezierCoords.hpp>
  23 #include <basegfx/polygon/b2dpolypolygon.hxx>
  24 #include <basegfx/polygon/b2dpolygon.hxx>
  25 #include <basegfx/polygon/b2dpolygontools.hxx>
  26 #include <basegfx/numeric/ftools.hxx>
  27
  28 #include <algorithm>
  29 #include <numeric>
  30
  31 namespace basegfx
  32 {
  33     namespace utils
  34     {
  35         B2DPolyPolygon correctOrientations(const B2DPolyPolygon& rCandidate)
  36         {
  37             B2DPolyPolygon aRetval(rCandidate);
  38             const sal_uInt32 nCount(aRetval.count());
  39
  40             for(sal_uInt32 a(0); a < nCount; a++)
  41             {
  42                 const B2DPolygon& aCandidate(rCandidate.getB2DPolygon(a));
  43                 const B2VectorOrientation aOrientation(utils::getOrientation(aCandidate));
  44                 sal_uInt32 nDepth(0);
  45
  46                 for(sal_uInt32 b(0); b < nCount; b++)
  47                 {
  48                     if(b != a)
  49                     {
  50                         const B2DPolygon& aCompare(rCandidate.getB2DPolygon(b));
  51
  52                         if(utils::isInside(aCompare, aCandidate, true))
  53                         {
  54                             nDepth++;
  55                         }
  56                     }
  57                 }
  58
  59                 const bool bShallBeHole((nDepth & 0x00000001) == 1);
  60                 const bool bIsHole(aOrientation == B2VectorOrientation::Negative);
  61
  62                 if(bShallBeHole != bIsHole && aOrientation != B2VectorOrientation::Neutral)
  63                 {
  64                     B2DPolygon aFlipped(aCandidate);
  65                     aFlipped.flip();
  66                     aRetval.setB2DPolygon(a, aFlipped);
  67                 }
  68             }
  69
  70             return aRetval;
  71         }
  72
  73         B2DPolyPolygon correctOutmostPolygon(const B2DPolyPolygon& rCandidate)
  74         {
  75             const sal_uInt32 nCount(rCandidate.count());
  76
  77             if(nCount > 1)
  78             {
  79                 for(sal_uInt32 a(0); a < nCount; a++)
  80                 {
  81                     const B2DPolygon& aCandidate(rCandidate.getB2DPolygon(a));
  82                     sal_uInt32 nDepth(0);
  83
  84                     for(sal_uInt32 b(0); b < nCount; b++)
  85                     {
  86                         if(b != a)
  87                         {
  88                             const B2DPolygon& aCompare(rCandidate.getB2DPolygon(b));
  89
  90                             if(utils::isInside(aCompare, aCandidate, true))
  91                             {
  92                                 nDepth++;
  93                             }
  94                         }
  95                     }
  96
  97                     if(!nDepth)
  98                     {
  99                         B2DPolyPolygon aRetval(rCandidate);
 100
 101                         if(a != 0)
 102                         {
 103                             // exchange polygon a and polygon 0
 104                             aRetval.setB2DPolygon(0, aCandidate);
 105                             aRetval.setB2DPolygon(a, rCandidate.getB2DPolygon(0));
 106                         }
 107
 108                         // exit
 109                         return aRetval;
 110                     }
 111                 }
 112             }
 113
 114             return rCandidate;
 115         }
 116
 117         B2DPolyPolygon adaptiveSubdivideByDistance(const B2DPolyPolygon& rCandidate, double fDistanceBound)
 118         {
 119             if(rCandidate.areControlPointsUsed())
 120             {
 121                 B2DPolyPolygon aRetval;
 122
 123                 for(auto const& rPolygon : rCandidate)
 124                 {
 125                     if(rPolygon.areControlPointsUsed())
 126                     {
 127                         aRetval.append(utils::adaptiveSubdivideByDistance(rPolygon, fDistanceBound));
 128                     }
 129                     else
 130                     {
 131                         aRetval.append(rPolygon);
 132                     }
 133                 }
 134
 135                 return aRetval;
 136             }
 137             else
 138             {
 139                 return rCandidate;
 140             }
 141         }
 142
 143         B2DPolyPolygon adaptiveSubdivideByAngle(const B2DPolyPolygon& rCandidate, double fAngleBound)
 144         {
 145             if(rCandidate.areControlPointsUsed())
 146             {
 147                 B2DPolyPolygon aRetval;
 148
 149                 for(auto const& rPolygon : rCandidate)
 150                 {
 151                     if(rPolygon.areControlPointsUsed())
 152                     {
 153                         aRetval.append(utils::adaptiveSubdivideByAngle(rPolygon, fAngleBound));
 154                     }
 155                     else
 156                     {
 157                         aRetval.append(rPolygon);
 158                     }
 159                 }
 160
 161                 return aRetval;
 162             }
 163             else
 164             {
 165                 return rCandidate;
 166             }
 167         }
 168
 169         bool isInside(const B2DPolyPolygon& rCandidate, const B2DPoint& rPoint, bool bWithBorder)
 170         {
 171             if(rCandidate.count() == 1)
 172             {
 173                 return isInside(rCandidate.getB2DPolygon(0), rPoint, bWithBorder);
 174             }
 175             else
 176             {
 177                 sal_Int32 nInsideCount = std::count_if(rCandidate.begin(), rCandidate.end(), [rPoint, bWithBorder](B2DPolygon polygon){ return isInside(polygon, rPoint, bWithBorder); });
 178
 179                 return (nInsideCount % 2);
 180             }
 181         }
 182
 183         B2DRange getRange(const B2DPolyPolygon& rCandidate)
 184         {
 185             B2DRange aRetval;
 186
 187             for(auto const& rPolygon : rCandidate)
 188             {
 189                 aRetval.expand(utils::getRange(rPolygon));
 190             }
 191
 192             return aRetval;
 193         }
 194
 195         double getSignedArea(const B2DPolyPolygon& rCandidate)
 196         {
 197             double fRetval(0.0);
 198
 199             for(auto const& rPolygon : rCandidate)
 200             {
 201                 fRetval += utils::getSignedArea(rPolygon);
 202             }
 203
 204             return fRetval;
 205         }
 206
 207         double getArea(const B2DPolyPolygon& rCandidate)
 208         {
 209             return fabs(getSignedArea(rCandidate));
 210         }
 211
 212         void applyLineDashing(const B2DPolyPolygon& rCandidate, const std::vector<double>& rDotDashArray, B2DPolyPolygon* pLineTarget, double fFullDashDotLen)
 213         {
 214             if(fFullDashDotLen == 0.0 && !rDotDashArray.empty())
 215             {
 216                 // calculate fFullDashDotLen from rDotDashArray
 217                 fFullDashDotLen = std::accumulate(rDotDashArray.begin(), rDotDashArray.end(), 0.0);
 218             }
 219
 220             if(rCandidate.count() && fFullDashDotLen > 0.0)
 221             {
 222                 B2DPolyPolygon aLineTarget;
 223
 224                 for(auto const& rPolygon : rCandidate)
 225                 {
 226                     applyLineDashing(
 227                         rPolygon,
 228                         rDotDashArray,
 229                         pLineTarget ? &aLineTarget : nullptr,
 230                         nullptr,
 231                         fFullDashDotLen);
 232
 233                     if(pLineTarget)
 234                     {
 235                         pLineTarget->append(aLineTarget);
 236                     }
 237                 }
 238             }
 239         }
 240
 241         bool isInEpsilonRange(const B2DPolyPolygon& rCandidate, const B2DPoint& rTestPosition, double fDistance)
 242         {
 243             for(auto const& rPolygon : rCandidate)
 244             {
 245                 if(isInEpsilonRange(rPolygon, rTestPosition, fDistance))
 246                 {
 247                     return true;
 248                 }
 249             }
 250
 251             return false;
 252         }
 253
 254         B3DPolyPolygon createB3DPolyPolygonFromB2DPolyPolygon(const B2DPolyPolygon& rCandidate, double fZCoordinate)
 255         {
 256             B3DPolyPolygon aRetval;
 257
 258             for(auto const& rPolygon : rCandidate)
 259             {
 260                 aRetval.append(createB3DPolygonFromB2DPolygon(rPolygon, fZCoordinate));
 261             }
 262
 263             return aRetval;
 264         }
 265
 266         B2DPolyPolygon createB2DPolyPolygonFromB3DPolyPolygon(const B3DPolyPolygon& rCandidate, const B3DHomMatrix& rMat)
 267         {
 268             B2DPolyPolygon aRetval;
 269
 270             for(auto const& rPolygon : rCandidate)
 271             {
 272                 aRetval.append(createB2DPolygonFromB3DPolygon(rPolygon, rMat));
 273             }
 274
 275             return aRetval;
 276         }
 277
 278         double getSmallestDistancePointToPolyPolygon(const B2DPolyPolygon& rCandidate, const B2DPoint& rTestPoint, sal_uInt32& rPolygonIndex, sal_uInt32& rEdgeIndex, double& rCut)
 279         {
 280             double fRetval(DBL_MAX);
 281             const double fZero(0.0);
 282             const sal_uInt32 nPolygonCount(rCandidate.count());
 283
 284             for(sal_uInt32 a(0); a < nPolygonCount; a++)
 285             {
 286                 const B2DPolygon& aCandidate(rCandidate.getB2DPolygon(a));
 287                 sal_uInt32 nNewEdgeIndex;
 288                 double fNewCut(0.0);
 289                 const double fNewDistance(getSmallestDistancePointToPolygon(aCandidate, rTestPoint, nNewEdgeIndex, fNewCut));
 290
 291                 if(fRetval == DBL_MAX || fNewDistance < fRetval)
 292                 {
 293                     fRetval = fNewDistance;
 294                     rPolygonIndex = a;
 295                     rEdgeIndex = nNewEdgeIndex;
 296                     rCut = fNewCut;
 297
 298                     if(fTools::equal(fRetval, fZero))
 299                     {
 300                         // already found zero distance, cannot get better. Ensure numerical zero value and end loop.
 301                         fRetval = 0.0;
 302                         break;
 303                     }
 304                 }
 305             }
 306
 307             return fRetval;
 308         }
 309
 310         B2DPolyPolygon distort(const B2DPolyPolygon& rCandidate, const B2DRange& rOriginal, const B2DPoint& rTopLeft, const B2DPoint& rTopRight, const B2DPoint& rBottomLeft, const B2DPoint& rBottomRight)
 311         {
 312             B2DPolyPolygon aRetval;
 313
 314             for(auto const& rPolygon : rCandidate)
 315             {
 316                 aRetval.append(distort(rPolygon, rOriginal, rTopLeft, rTopRight, rBottomLeft, rBottomRight));
 317             }
 318
 319             return aRetval;
 320         }
 321
 322         B2DPolyPolygon expandToCurve(const B2DPolyPolygon& rCandidate)
 323         {
 324             B2DPolyPolygon aRetval;
 325
 326             for(auto const& rPolygon : rCandidate)
 327             {
 328                 aRetval.append(expandToCurve(rPolygon));
 329             }
 330
 331             return aRetval;
 332         }
 333
 334         B2DPolyPolygon growInNormalDirection(const B2DPolyPolygon& rCandidate, double fValue)
 335         {
 336             if(fValue != 0.0)
 337             {
 338                 B2DPolyPolygon aRetval;
 339
 340                 for(auto const& rPolygon : rCandidate)
 341                 {
 342                     aRetval.append(growInNormalDirection(rPolygon, fValue));
 343                 }
 344
 345                 return aRetval;
 346             }
 347             else
 348             {
 349                 return rCandidate;
 350             }
 351         }
 352
 353         B2DPolyPolygon reSegmentPolyPolygon(const B2DPolyPolygon& rCandidate, sal_uInt32 nSegments)
 354         {
 355             B2DPolyPolygon aRetval;
 356
 357             for(auto const& rPolygon : rCandidate)
 358             {
 359                 aRetval.append(reSegmentPolygon(rPolygon, nSegments));
 360             }
 361
 362             return aRetval;
 363         }
 364
 365         B2DPolyPolygon interpolate(const B2DPolyPolygon& rOld1, const B2DPolyPolygon& rOld2, double t)
 366         {
 367             OSL_ENSURE(rOld1.count() == rOld2.count(), "B2DPolyPolygon interpolate: Different geometry (!)");
 368             B2DPolyPolygon aRetval;
 369
 370             for(sal_uInt32 a(0); a < rOld1.count(); a++)
 371             {
 372                 aRetval.append(interpolate(rOld1.getB2DPolygon(a), rOld2.getB2DPolygon(a), t));
 373             }
 374
 375             return aRetval;
 376         }
 377
 378         bool isRectangle( const B2DPolyPolygon& rPoly )
 379         {
 380             // exclude some cheap cases first
 381             if( rPoly.count() != 1 )
 382                 return false;
 383
 384             return isRectangle( rPoly.getB2DPolygon(0) );
 385         }
 386
 387         // #i76891#
 388         B2DPolyPolygon simplifyCurveSegments(const B2DPolyPolygon& rCandidate)
 389         {
 390             if(rCandidate.areControlPointsUsed())
 391             {
 392                 B2DPolyPolygon aRetval;
 393
 394                 for(auto const& rPolygon : rCandidate)
 395                 {
 396                     aRetval.append(simplifyCurveSegments(rPolygon));
 397                 }
 398
 399                 return aRetval;
 400             }
 401             else
 402             {
 403                 return rCandidate;
 404             }
 405         }
 406
 407         B2DPolyPolygon snapPointsOfHorizontalOrVerticalEdges(const B2DPolyPolygon& rCandidate)
 408         {
 409             B2DPolyPolygon aRetval;
 410
 411             for(auto const& rPolygon : rCandidate)
 412             {
 413                 aRetval.append(snapPointsOfHorizontalOrVerticalEdges(rPolygon));
 414             }
 415
 416             return aRetval;
 417         }
 418
 419         B2DPolyPolygon createSevenSegmentPolyPolygon(sal_Char nNumber, bool bLitSegments)
 420         {
 421             // config here
 422             // {
 423             const double fTotalSize=1.0;
 424             const double fPosMiddleSegment=0.6;
 425             const double fSegmentEndChopHoriz=0.08;
 426             const double fSegmentEndChopVert =0.04;
 427             // }
 428             // config here
 429
 430             const double fLeft=0.0;
 431             const double fRight=fTotalSize;
 432             const double fTop=0.0;
 433             const double fMiddle=fPosMiddleSegment;
 434             const double fBottom=fTotalSize;
 435
 436             // from 0 to 5: pair of segment corner coordinates
 437
 438             // segment corner indices are these:
 439
 440             //   0 - 1
 441             //   |   |
 442             //   2 - 3
 443             //   |   |
 444             //   4 - 5
 445
 446             static const double corners[] =
 447             {
 448                 fLeft,  fTop,
 449                 fRight, fTop,
 450                 fLeft,  fMiddle,
 451                 fRight, fMiddle,
 452                 fLeft,  fBottom,
 453                 fRight, fBottom
 454             };
 455
 456             // from 0 to 9: which segments are 'lit' for this number?
 457
 458             // array denotes graph edges to traverse, with -1 means
 459             // stop (the vertices are the corner indices from above):
 460             //     0
 461             //     -
 462             // 1 |   | 2
 463             //     - 3
 464             // 4 |   | 5
 465             //     -
 466             //     6
 467
 468             static const int numbers[] =
 469             {
 470                 1, 1, 1, 0, 1, 1, 1, // 0
 471                 0, 0, 1, 0, 0, 1, 0, // 1
 472                 1, 0, 1, 1, 1, 0, 1, // 2
 473                 1, 0, 1, 1, 0, 1, 1, // 3
 474                 0, 1, 1, 1, 0, 1, 0, // 4
 475                 1, 1, 0, 1, 0, 1, 1, // 5
 476                 1, 1, 0, 1, 1, 1, 1, // 6
 477                 1, 0, 1, 0, 0, 1, 0, // 1
 478                 1, 1, 1, 1, 1, 1, 1, // 8
 479                 1, 1, 1, 1, 0, 1, 1, // 9
 480                 0, 0, 0, 1, 0, 0, 0, // '-'
 481                 1, 1, 0, 1, 1, 0, 1, // 'E'
 482             };
 483
 484             // maps segment index to two corner ids:
 485             static const int index2corner[] =
 486             {
 487                 0, 2,  // 0
 488                 0, 4,  // 1
 489                 2, 6,  // 2
 490                 4, 6,  // 3
 491                 4, 8,  // 4
 492                 6, 10, // 5
 493                 8, 10, // 6
 494             };
 495
 496             B2DPolyPolygon aRes;
 497             if( nNumber == '-' )
 498             {
 499                 nNumber = 10;
 500             }
 501             else if( nNumber == 'E' )
 502             {
 503                 nNumber = 11;
 504             }
 505             else if( nNumber == '.' )
 506             {
 507                 if( bLitSegments )
 508                     aRes.append(createPolygonFromCircle(B2DPoint(fTotalSize/2, fTotalSize),
 509                                                         fSegmentEndChopHoriz));
 510                 return aRes;
 511             }
 512             else
 513             {
 514                 nNumber=std::clamp<sal_uInt32>(nNumber,'0','9') - '0';
 515             }
 516
 517             B2DPolygon aCurrSegment;
 518             const size_t sliceSize=SAL_N_ELEMENTS(numbers)/12;
 519             const int* pCurrSegment=numbers + nNumber*sliceSize;
 520             for( size_t i=0; i<sliceSize; i++, pCurrSegment++)
 521             {
 522                 if( !(*pCurrSegment ^ int(bLitSegments)) )
 523                 {
 524                     const size_t j=2*i;
 525                     aCurrSegment.clear();
 526                     B2DPoint start(corners[index2corner[j]],
 527                                    corners[index2corner[j]+1]  );
 528                     B2DPoint end  (corners[index2corner[j+1]],
 529                                    corners[index2corner[j+1]+1]);
 530
 531                     if( rtl::math::approxEqual(start.getX(), end.getX()) )
 532                     {
 533                         start.setY(start.getY()+fSegmentEndChopVert);
 534                         end.setY(end.getY()-fSegmentEndChopVert);
 535                     }
 536                     else
 537                     {
 538                         start.setX(start.getX()+fSegmentEndChopHoriz);
 539                         end.setX(end.getX()-fSegmentEndChopHoriz);
 540                     }
 541
 542                     aCurrSegment.append(start);
 543                     aCurrSegment.append(end);
 544                 }
 545                 aRes.append(aCurrSegment);
 546             }
 547
 548             return aRes;
 549         }
 550
 551         // converters for css::drawing::PointSequence
 552
 553         B2DPolyPolygon UnoPointSequenceSequenceToB2DPolyPolygon(
 554             const css::drawing::PointSequenceSequence& rPointSequenceSequenceSource)
 555         {
 556             B2DPolyPolygon aRetval;
 557             const css::drawing::PointSequence* pPointSequence = rPointSequenceSequenceSource.getConstArray();
 558             const css::drawing::PointSequence* pPointSeqEnd = pPointSequence + rPointSequenceSequenceSource.getLength();
 559
 560             for(;pPointSequence != pPointSeqEnd; pPointSequence++)
 561             {
 562                 const B2DPolygon aNewPolygon = UnoPointSequenceToB2DPolygon(*pPointSequence);
 563                 aRetval.append(aNewPolygon);
 564             }
 565
 566             return aRetval;
 567         }
 568
 569         void B2DPolyPolygonToUnoPointSequenceSequence(
 570             const B2DPolyPolygon& rPolyPolygon,
 571             css::drawing::PointSequenceSequence& rPointSequenceSequenceRetval)
 572         {
 573             const sal_uInt32 nCount(rPolyPolygon.count());
 574
 575             if(nCount)
 576             {
 577                 rPointSequenceSequenceRetval.realloc(nCount);
 578                 css::drawing::PointSequence* pPointSequence = rPointSequenceSequenceRetval.getArray();
 579
 580                 for(auto const& rPolygon : rPolyPolygon)
 581                 {
 582                     B2DPolygonToUnoPointSequence(rPolygon, *pPointSequence);
 583                     pPointSequence++;
 584                 }
 585             }
 586             else
 587             {
 588                 rPointSequenceSequenceRetval.realloc(0);
 589             }
 590         }
 591
 592         // converters for css::drawing::PolyPolygonBezierCoords (curved polygons)
 593
 594         B2DPolyPolygon UnoPolyPolygonBezierCoordsToB2DPolyPolygon(
 595             const css::drawing::PolyPolygonBezierCoords& rPolyPolygonBezierCoordsSource)
 596         {
 597             B2DPolyPolygon aRetval;
 598             const sal_uInt32 nSequenceCount(static_cast<sal_uInt32>(rPolyPolygonBezierCoordsSource.Coordinates.getLength()));
 599
 600             if(nSequenceCount)
 601             {
 602                 OSL_ENSURE(nSequenceCount == static_cast<sal_uInt32>(rPolyPolygonBezierCoordsSource.Flags.getLength()),
 603                     "UnoPolyPolygonBezierCoordsToB2DPolyPolygon: unequal number of Points and Flags (!)");
 604                 const css::drawing::PointSequence* pPointSequence = rPolyPolygonBezierCoordsSource.Coordinates.getConstArray();
 605                 const css::drawing::FlagSequence* pFlagSequence = rPolyPolygonBezierCoordsSource.Flags.getConstArray();
 606
 607                 for(sal_uInt32 a(0); a < nSequenceCount; a++)
 608                 {
 609                     const B2DPolygon aNewPolygon(UnoPolygonBezierCoordsToB2DPolygon(
 610                         *pPointSequence,
 611                         *pFlagSequence));
 612
 613                     pPointSequence++;
 614                     pFlagSequence++;
 615                     aRetval.append(aNewPolygon);
 616                 }
 617             }
 618
 619             return aRetval;
 620         }
 621
 622         void B2DPolyPolygonToUnoPolyPolygonBezierCoords(
 623             const B2DPolyPolygon& rPolyPolygon,
 624             css::drawing::PolyPolygonBezierCoords& rPolyPolygonBezierCoordsRetval)
 625         {
 626             const sal_uInt32 nCount(rPolyPolygon.count());
 627
 628             if(nCount)
 629             {
 630                 // prepare return value memory
 631                 rPolyPolygonBezierCoordsRetval.Coordinates.realloc(static_cast<sal_Int32>(nCount));
 632                 rPolyPolygonBezierCoordsRetval.Flags.realloc(static_cast<sal_Int32>(nCount));
 633
 634                 // get pointers to arrays
 635                 css::drawing::PointSequence* pPointSequence = rPolyPolygonBezierCoordsRetval.Coordinates.getArray();
 636                 css::drawing::FlagSequence*  pFlagSequence = rPolyPolygonBezierCoordsRetval.Flags.getArray();
 637
 638                 for(auto const& rSource : rPolyPolygon)
 639                 {
 640                     B2DPolygonToUnoPolygonBezierCoords(
 641                         rSource,
 642                         *pPointSequence,
 643                         *pFlagSequence);
 644                     pPointSequence++;
 645                     pFlagSequence++;
 646                 }
 647             }
 648             else
 649             {
 650                 rPolyPolygonBezierCoordsRetval.Coordinates.realloc(0);
 651                 rPolyPolygonBezierCoordsRetval.Flags.realloc(0);
 652             }
 653         }
 654
 655     } // end of namespace utils
 656 } // end of namespace basegfx
 657
 658 /* vim:set shiftwidth=4 softtabstop=4 expandtab: */