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