LCOV - code coverage report
Current view: top level - basegfx/source/polygon - b2dpolygontriangulator.cxx (source / functions) Hit Total Coverage
Test: commit c8344322a7af75b84dd3ca8f78b05543a976dfd5 Lines: 0 166 0.0 %
Date: 2015-06-13 12:38:46 Functions: 0 19 0.0 %
Legend: Lines: hit not hit

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

Generated by: LCOV version 1.11