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