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 467