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