basegfx/source/polygon/b2dpolygontriangulator.cxx

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