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