basegfx/source/polygon/b2dpolygontriangulator.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/b2dpolygontriangulator.hxx>
  21 #include <basegfx/point/b2dpoint.hxx>
  22 #include <basegfx/polygon/b2dpolygon.hxx>
  23 #include <basegfx/polygon/b2dpolypolygon.hxx>
  24 #include <basegfx/vector/b2dvector.hxx>
  25 #include <basegfx/polygon/b2dpolygontools.hxx>
  26 #include <basegfx/polygon/b2dpolypolygontools.hxx>
  27 #include <basegfx/range/b2drange.hxx>
  28 #include <basegfx/numeric/ftools.hxx>
  29
  30 #include <algorithm>
  31
  32 namespace basegfx
  33 {
  34     namespace
  35     {
  36         class EdgeEntry
  37         {
  38             EdgeEntry*                              mpNext;
  39             B2DPoint                                maStart;
  40             B2DPoint                                maEnd;
  41             double                                  mfAtan2;
  42
  43         public:
  44             EdgeEntry(const B2DPoint& rStart, const B2DPoint& rEnd)
  45             :   mpNext(nullptr),
  46                 maStart(rStart),
  47                 maEnd(rEnd),
  48                 mfAtan2(0.0)
  49             {
  50                 // make sure edge goes down. If horizontal, let it go to the right (left-handed).
  51                 bool bSwap(false);
  52
  53                 if(::basegfx::fTools::equal(maStart.getY(), maEnd.getY()))
  54                 {
  55                     if(maStart.getX() > maEnd.getX())
  56                     {
  57                         bSwap = true;
  58                     }
  59                 }
  60                 else if(maStart.getY() > maEnd.getY())
  61                 {
  62                     bSwap = true;
  63                 }
  64
  65                 if(bSwap)
  66                 {
  67                     maStart = rEnd;
  68                     maEnd = rStart;
  69                 }
  70
  71                 mfAtan2 = atan2(maEnd.getY() - maStart.getY(), maEnd.getX() - maStart.getX());
  72             }
  73
  74             bool operator<(const EdgeEntry& rComp) const
  75             {
  76                 if(::basegfx::fTools::equal(maStart.getY(), rComp.maStart.getY()))
  77                 {
  78                     if(::basegfx::fTools::equal(maStart.getX(), rComp.maStart.getX()))
  79                     {
  80                         // same in x and y -> same start point. Sort emitting vectors from left to right.
  81                         return (mfAtan2 > rComp.mfAtan2);
  82                     }
  83
  84                     return (maStart.getX() < rComp.maStart.getX());
  85                 }
  86
  87                 return (maStart.getY() < rComp.maStart.getY());
  88             }
  89
  90             bool operator==(const EdgeEntry& rComp) const
  91             {
  92                 return (maStart.equal(rComp.maStart) && maEnd.equal(rComp.maEnd));
  93             }
  94
  95             bool operator!=(const EdgeEntry& rComp) const
  96             {
  97                 return !(*this == rComp);
  98             }
  99
 100             const B2DPoint& getStart() const { return maStart; }
 101             const B2DPoint& getEnd() const { return maEnd; }
 102
 103             EdgeEntry* getNext() const { return mpNext; }
 104             void setNext(EdgeEntry* pNext) { mpNext = pNext; }
 105         };
 106
 107         typedef std::vector< EdgeEntry > EdgeEntries;
 108
 109         class Triangulator
 110         {
 111             EdgeEntry*                                      mpList;
 112             EdgeEntries                                     maStartEntries;
 113             std::vector< std::unique_ptr<EdgeEntry> >       maNewEdgeEntries;
 114             triangulator::B2DTriangleVector                 maResult;
 115
 116             void handleClosingEdge(const B2DPoint& rStart, const B2DPoint& rEnd);
 117             bool CheckPointInTriangle(EdgeEntry* pEdgeA, EdgeEntry const * pEdgeB, const B2DPoint& rTestPoint);
 118             void createTriangle(const B2DPoint& rA, const B2DPoint& rB, const B2DPoint& rC);
 119
 120         public:
 121             explicit Triangulator(const B2DPolyPolygon& rCandidate);
 122
 123             const triangulator::B2DTriangleVector& getResult() const { return maResult; }
 124         };
 125
 126         void Triangulator::handleClosingEdge(const B2DPoint& rStart, const B2DPoint& rEnd)
 127         {
 128             // create an entry, else the comparison might use the wrong edges
 129             EdgeEntry aNew(rStart, rEnd);
 130             EdgeEntry* pCurr = mpList;
 131             EdgeEntry* pPrev = nullptr;
 132
 133             while(pCurr
 134                 && pCurr->getStart().getY() <= aNew.getStart().getY()
 135                 && *pCurr != aNew)
 136             {
 137                 pPrev = pCurr;
 138                 pCurr = pCurr->getNext();
 139             }
 140
 141             if(pCurr && *pCurr == aNew)
 142             {
 143                 // found closing edge, remove
 144                 if(pPrev)
 145                 {
 146                     pPrev->setNext(pCurr->getNext());
 147                 }
 148                 else
 149                 {
 150                     mpList = pCurr->getNext();
 151                 }
 152             }
 153             else
 154             {
 155                 // insert closing edge
 156                 EdgeEntry* pNew = new EdgeEntry(aNew);
 157                 maNewEdgeEntries.emplace_back(pNew);
 158                 pCurr = mpList;
 159                 pPrev = nullptr;
 160
 161                 while(pCurr && *pCurr < *pNew)
 162                 {
 163                     pPrev = pCurr;
 164                     pCurr = pCurr->getNext();
 165                 }
 166
 167                 if(pPrev)
 168                 {
 169                     pNew->setNext(pPrev->getNext());
 170                     pPrev->setNext(pNew);
 171                 }
 172                 else
 173                 {
 174                     pNew->setNext(mpList);
 175                     mpList = pNew;
 176                 }
 177             }
 178         }
 179
 180         bool Triangulator::CheckPointInTriangle(EdgeEntry* pEdgeA, EdgeEntry const * pEdgeB, const B2DPoint& rTestPoint)
 181         {
 182             // inside triangle or on edge?
 183             if(utils::isPointInTriangle(pEdgeA->getStart(), pEdgeA->getEnd(), pEdgeB->getEnd(), rTestPoint, true))
 184             {
 185                 // but not on point
 186                 if(!rTestPoint.equal(pEdgeA->getEnd()) && !rTestPoint.equal(pEdgeB->getEnd()))
 187                 {
 188                     // found point in triangle -> split triangle inserting two edges
 189                     EdgeEntry* pStart = new EdgeEntry(pEdgeA->getStart(), rTestPoint);
 190                     EdgeEntry* pEnd = new EdgeEntry(*pStart);
 191                     maNewEdgeEntries.emplace_back(pStart);
 192                     maNewEdgeEntries.emplace_back(pEnd);
 193
 194                     pStart->setNext(pEnd);
 195                     pEnd->setNext(pEdgeA->getNext());
 196                     pEdgeA->setNext(pStart);
 197
 198                     return false;
 199                 }
 200             }
 201
 202             return true;
 203         }
 204
 205         void Triangulator::createTriangle(const B2DPoint& rA, const B2DPoint& rB, const B2DPoint& rC)
 206         {
 207             maResult.emplace_back(
 208                 rA,
 209                 rB,
 210                 rC);
 211         }
 212
 213         // consume as long as there are edges
 214         Triangulator::Triangulator(const B2DPolyPolygon& rCandidate)
 215         :   mpList(nullptr)
 216         {
 217             // add all available edges to the single linked local list which will be sorted
 218             // by Y,X,atan2 when adding nodes
 219             if(rCandidate.count())
 220             {
 221                 for(sal_uInt32 a(0); a < rCandidate.count(); a++)
 222                 {
 223                     const B2DPolygon& aPolygonCandidate(rCandidate.getB2DPolygon(a));
 224                     const sal_uInt32 nCount(aPolygonCandidate.count());
 225
 226                     if(nCount > 2)
 227                     {
 228                         B2DPoint aPrevPnt(aPolygonCandidate.getB2DPoint(nCount - 1));
 229
 230                         for(sal_uInt32 b(0); b < nCount; b++)
 231                         {
 232                             B2DPoint aNextPnt(aPolygonCandidate.getB2DPoint(b));
 233
 234                             if( !aPrevPnt.equal(aNextPnt) )
 235                             {
 236                                 maStartEntries.emplace_back(aPrevPnt, aNextPnt);
 237                             }
 238
 239                             aPrevPnt = aNextPnt;
 240                         }
 241                     }
 242                 }
 243
 244                 if(!maStartEntries.empty())
 245                 {
 246                     // sort initial list
 247                     std::sort(maStartEntries.begin(), maStartEntries.end());
 248
 249                     // insert to own simply linked list
 250                     EdgeEntries::iterator aPos(maStartEntries.begin());
 251                     mpList = &(*aPos++);
 252                     EdgeEntry* pLast = mpList;
 253
 254                     while(aPos != maStartEntries.end())
 255                     {
 256                         EdgeEntry* pEntry = &(*aPos++);
 257                         pLast->setNext(pEntry);
 258                         pLast = pEntry;
 259                     }
 260                 }
 261             }
 262
 263             while(mpList)
 264             {
 265                 if(mpList->getNext() && mpList->getNext()->getStart().equal(mpList->getStart()))
 266                 {
 267                     // next candidate. There are two edges and start point is equal.
 268                     // Length is not zero.
 269                     EdgeEntry* pEdgeA = mpList;
 270                     EdgeEntry* pEdgeB = pEdgeA->getNext();
 271
 272                     if( pEdgeA->getEnd().equal(pEdgeB->getEnd()) )
 273                     {
 274                         // start and end equal -> neutral triangle, delete both
 275                         mpList = pEdgeB->getNext();
 276                     }
 277                     else
 278                     {
 279                         const B2DVector aLeft(pEdgeA->getEnd() - pEdgeA->getStart());
 280                         const B2DVector aRight(pEdgeB->getEnd() - pEdgeA->getStart());
 281
 282                         if(getOrientation(aLeft, aRight) == B2VectorOrientation::Neutral)
 283                         {
 284                             // edges are parallel and have different length -> neutral triangle,
 285                             // delete both edges and handle closing edge
 286                             mpList = pEdgeB->getNext();
 287                             handleClosingEdge(pEdgeA->getEnd(), pEdgeB->getEnd());
 288                         }
 289                         else
 290                         {
 291                             // not parallel, look for points inside
 292                             B2DRange aRange(pEdgeA->getStart(), pEdgeA->getEnd());
 293                             aRange.expand(pEdgeB->getEnd());
 294                             EdgeEntry* pTestEdge = pEdgeB->getNext();
 295                             bool bNoPointInTriangle(true);
 296
 297                             // look for start point in triangle
 298                             while(bNoPointInTriangle && pTestEdge)
 299                             {
 300                                 if(aRange.getMaxY() < pTestEdge->getStart().getY())
 301                                 {
 302                                     // edge is below test range and edges are sorted -> stop looking
 303                                     break;
 304                                 }
 305                                 else
 306                                 {
 307                                     // do not look for edges with same start point, they are sorted and cannot end inside.
 308                                     if(!pTestEdge->getStart().equal(pEdgeA->getStart()))
 309                                     {
 310                                         if(aRange.isInside(pTestEdge->getStart()))
 311                                         {
 312                                             bNoPointInTriangle = CheckPointInTriangle(pEdgeA, pEdgeB, pTestEdge->getStart());
 313                                         }
 314                                     }
 315                                 }
 316
 317                                 // next candidate
 318                                 pTestEdge = pTestEdge->getNext();
 319                             }
 320
 321                             if(bNoPointInTriangle)
 322                             {
 323                                 // look for end point in triangle
 324                                 pTestEdge = pEdgeB->getNext();
 325
 326                                 while(bNoPointInTriangle && pTestEdge)
 327                                 {
 328                                     if(aRange.getMaxY() < pTestEdge->getStart().getY())
 329                                     {
 330                                         // edge is below test range and edges are sorted -> stop looking
 331                                         break;
 332                                     }
 333                                     else
 334                                     {
 335                                         // do not look for edges with same end point, they are sorted and cannot end inside.
 336                                         if(!pTestEdge->getEnd().equal(pEdgeA->getStart()))
 337                                         {
 338                                             if(aRange.isInside(pTestEdge->getEnd()))
 339                                             {
 340                                                 bNoPointInTriangle = CheckPointInTriangle(pEdgeA, pEdgeB, pTestEdge->getEnd());
 341                                             }
 342                                         }
 343                                     }
 344
 345                                     // next candidate
 346                                     pTestEdge = pTestEdge->getNext();
 347                                 }
 348                             }
 349
 350                             if(bNoPointInTriangle)
 351                             {
 352                                 // create triangle, remove edges, handle closing edge
 353                                 mpList = pEdgeB->getNext();
 354                                 createTriangle(pEdgeA->getStart(), pEdgeB->getEnd(), pEdgeA->getEnd());
 355                                 handleClosingEdge(pEdgeA->getEnd(), pEdgeB->getEnd());
 356                             }
 357                         }
 358                     }
 359                 }
 360                 else
 361                 {
 362                     // only one entry at start point, delete it
 363                     mpList = mpList->getNext();
 364                 }
 365             }
 366         }
 367
 368     } // end of anonymous namespace
 369 } // end of namespace basegfx
 370
 371 namespace basegfx
 372 {
 373     namespace triangulator
 374     {
 375         B2DTriangleVector triangulate(const B2DPolygon& rCandidate)
 376         {
 377             B2DTriangleVector aRetval;
 378
 379             // subdivide locally (triangulate does not work with beziers), remove double and neutral points
 380             B2DPolygon aCandidate(rCandidate.areControlPointsUsed() ? utils::adaptiveSubdivideByAngle(rCandidate) : rCandidate);
 381             aCandidate.removeDoublePoints();
 382             aCandidate = utils::removeNeutralPoints(aCandidate);
 383
 384             if(aCandidate.count() == 2)
 385             {
 386                 // candidate IS a triangle, just append
 387                 aRetval.emplace_back(
 388                     aCandidate.getB2DPoint(0),
 389                     aCandidate.getB2DPoint(1),
 390                     aCandidate.getB2DPoint(2));
 391             }
 392             else if(aCandidate.count() > 2)
 393             {
 394                 if(utils::isConvex(aCandidate))
 395                 {
 396                     // polygon is convex, just use a triangle fan
 397                     utils::addTriangleFan(aCandidate, aRetval);
 398                 }
 399                 else
 400                 {
 401                     // polygon is concave.
 402                     const B2DPolyPolygon aCandPolyPoly(aCandidate);
 403                     Triangulator aTriangulator(aCandPolyPoly);
 404
 405                     aRetval = aTriangulator.getResult();
 406                 }
 407             }
 408
 409             return aRetval;
 410         }
 411
 412         B2DTriangleVector triangulate(const B2DPolyPolygon& rCandidate)
 413         {
 414             B2DTriangleVector aRetval;
 415
 416             // subdivide locally (triangulate does not work with beziers)
 417             B2DPolyPolygon aCandidate(rCandidate.areControlPointsUsed() ? utils::adaptiveSubdivideByAngle(rCandidate) : rCandidate);
 418
 419             if(aCandidate.count() == 1)
 420             {
 421                 // single polygon -> single polygon triangulation
 422                 const B2DPolygon& aSinglePolygon(aCandidate.getB2DPolygon(0));
 423
 424                 aRetval = triangulate(aSinglePolygon);
 425             }
 426             else
 427             {
 428                 Triangulator aTriangulator(aCandidate);
 429
 430                 aRetval = aTriangulator.getResult();
 431             }
 432
 433             return aRetval;
 434         }
 435     } // end of namespace triangulator
 436 } // end of namespace basegfx
 437
 438 /* vim:set shiftwidth=4 softtabstop=4 expandtab: */