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