basegfx/source/polygon/b2dpolygontriangulator.cxx

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