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