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/b2dpolypolygontools.hxx> 31 #include <osl/diagnose.h> 32 #include <basegfx/polygon/b2dpolypolygon.hxx> 33 #include <basegfx/polygon/b2dpolygon.hxx> 34 #include <basegfx/polygon/b2dpolygontools.hxx> 35 #include <basegfx/numeric/ftools.hxx> 36 #include <basegfx/polygon/b2dpolypolygoncutter.hxx> 37 38 #include <numeric> 39 40 ////////////////////////////////////////////////////////////////////////////// 41 42 namespace basegfx 43 { 44 namespace tools 45 { 46 B2DPolyPolygon correctOrientations(const B2DPolyPolygon& rCandidate) 47 { 48 B2DPolyPolygon aRetval(rCandidate); 49 const sal_uInt32 nCount(aRetval.count()); 50 51 for(sal_uInt32 a(0L); a < nCount; a++) 52 { 53 const B2DPolygon aCandidate(rCandidate.getB2DPolygon(a)); 54 const B2VectorOrientation aOrientation(tools::getOrientation(aCandidate)); 55 sal_uInt32 nDepth(0L); 56 57 for(sal_uInt32 b(0L); b < nCount; b++) 58 { 59 if(b != a) 60 { 61 const B2DPolygon aCompare(rCandidate.getB2DPolygon(b)); 62 63 if(tools::isInside(aCompare, aCandidate, true)) 64 { 65 nDepth++; 66 } 67 } 68 } 69 70 const bool bShallBeHole(1L == (nDepth & 0x00000001)); 71 const bool bIsHole(ORIENTATION_NEGATIVE == aOrientation); 72 73 if(bShallBeHole != bIsHole && ORIENTATION_NEUTRAL != aOrientation) 74 { 75 B2DPolygon aFlipped(aCandidate); 76 aFlipped.flip(); 77 aRetval.setB2DPolygon(a, aFlipped); 78 } 79 } 80 81 return aRetval; 82 } 83 84 B2DPolyPolygon correctOutmostPolygon(const B2DPolyPolygon& rCandidate) 85 { 86 const sal_uInt32 nCount(rCandidate.count()); 87 88 if(nCount > 1L) 89 { 90 for(sal_uInt32 a(0L); a < nCount; a++) 91 { 92 const B2DPolygon aCandidate(rCandidate.getB2DPolygon(a)); 93 sal_uInt32 nDepth(0L); 94 95 for(sal_uInt32 b(0L); b < nCount; b++) 96 { 97 if(b != a) 98 { 99 const B2DPolygon aCompare(rCandidate.getB2DPolygon(b)); 100 101 if(tools::isInside(aCompare, aCandidate, true)) 102 { 103 nDepth++; 104 } 105 } 106 } 107 108 if(!nDepth) 109 { 110 B2DPolyPolygon aRetval(rCandidate); 111 112 if(a != 0L) 113 { 114 // exchange polygon a and polygon 0L 115 aRetval.setB2DPolygon(0L, aCandidate); 116 aRetval.setB2DPolygon(a, rCandidate.getB2DPolygon(0L)); 117 } 118 119 // exit 120 return aRetval; 121 } 122 } 123 } 124 125 return rCandidate; 126 } 127 128 B2DPolyPolygon adaptiveSubdivideByDistance(const B2DPolyPolygon& rCandidate, double fDistanceBound) 129 { 130 if(rCandidate.areControlPointsUsed()) 131 { 132 const sal_uInt32 nPolygonCount(rCandidate.count()); 133 B2DPolyPolygon aRetval; 134 135 for(sal_uInt32 a(0L); a < nPolygonCount; a++) 136 { 137 const B2DPolygon aCandidate(rCandidate.getB2DPolygon(a)); 138 139 if(aCandidate.areControlPointsUsed()) 140 { 141 aRetval.append(tools::adaptiveSubdivideByDistance(aCandidate, fDistanceBound)); 142 } 143 else 144 { 145 aRetval.append(aCandidate); 146 } 147 } 148 149 return aRetval; 150 } 151 else 152 { 153 return rCandidate; 154 } 155 } 156 157 B2DPolyPolygon adaptiveSubdivideByAngle(const B2DPolyPolygon& rCandidate, double fAngleBound) 158 { 159 if(rCandidate.areControlPointsUsed()) 160 { 161 const sal_uInt32 nPolygonCount(rCandidate.count()); 162 B2DPolyPolygon aRetval; 163 164 for(sal_uInt32 a(0L); a < nPolygonCount; a++) 165 { 166 const B2DPolygon aCandidate(rCandidate.getB2DPolygon(a)); 167 168 if(aCandidate.areControlPointsUsed()) 169 { 170 aRetval.append(tools::adaptiveSubdivideByAngle(aCandidate, fAngleBound)); 171 } 172 else 173 { 174 aRetval.append(aCandidate); 175 } 176 } 177 178 return aRetval; 179 } 180 else 181 { 182 return rCandidate; 183 } 184 } 185 186 B2DPolyPolygon adaptiveSubdivideByCount(const B2DPolyPolygon& rCandidate, sal_uInt32 nCount) 187 { 188 if(rCandidate.areControlPointsUsed()) 189 { 190 const sal_uInt32 nPolygonCount(rCandidate.count()); 191 B2DPolyPolygon aRetval; 192 193 for(sal_uInt32 a(0L); a < nPolygonCount; a++) 194 { 195 const B2DPolygon aCandidate(rCandidate.getB2DPolygon(a)); 196 197 if(aCandidate.areControlPointsUsed()) 198 { 199 aRetval.append(tools::adaptiveSubdivideByCount(aCandidate, nCount)); 200 } 201 else 202 { 203 aRetval.append(aCandidate); 204 } 205 } 206 207 return aRetval; 208 } 209 else 210 { 211 return rCandidate; 212 } 213 } 214 215 bool isInside(const B2DPolyPolygon& rCandidate, const B2DPoint& rPoint, bool bWithBorder) 216 { 217 const sal_uInt32 nPolygonCount(rCandidate.count()); 218 219 if(1L == nPolygonCount) 220 { 221 return isInside(rCandidate.getB2DPolygon(0L), rPoint, bWithBorder); 222 } 223 else 224 { 225 sal_Int32 nInsideCount(0L); 226 227 for(sal_uInt32 a(0L); a < nPolygonCount; a++) 228 { 229 const B2DPolygon aPolygon(rCandidate.getB2DPolygon(a)); 230 const bool bInside(isInside(aPolygon, rPoint, bWithBorder)); 231 232 if(bInside) 233 { 234 nInsideCount++; 235 } 236 } 237 238 return (nInsideCount % 2L); 239 } 240 } 241 242 B2DRange getRangeWithControlPoints(const B2DPolyPolygon& rCandidate) 243 { 244 B2DRange aRetval; 245 const sal_uInt32 nPolygonCount(rCandidate.count()); 246 247 for(sal_uInt32 a(0L); a < nPolygonCount; a++) 248 { 249 B2DPolygon aCandidate = rCandidate.getB2DPolygon(a); 250 aRetval.expand(tools::getRangeWithControlPoints(aCandidate)); 251 } 252 253 return aRetval; 254 } 255 256 B2DRange getRange(const B2DPolyPolygon& rCandidate) 257 { 258 B2DRange aRetval; 259 const sal_uInt32 nPolygonCount(rCandidate.count()); 260 261 for(sal_uInt32 a(0L); a < nPolygonCount; a++) 262 { 263 B2DPolygon aCandidate = rCandidate.getB2DPolygon(a); 264 aRetval.expand(tools::getRange(aCandidate)); 265 } 266 267 return aRetval; 268 } 269 270 void applyLineDashing(const B2DPolyPolygon& rCandidate, const ::std::vector<double>& rDotDashArray, B2DPolyPolygon* pLineTarget, B2DPolyPolygon* pGapTarget, double fFullDashDotLen) 271 { 272 if(0.0 == fFullDashDotLen && rDotDashArray.size()) 273 { 274 // calculate fFullDashDotLen from rDotDashArray 275 fFullDashDotLen = ::std::accumulate(rDotDashArray.begin(), rDotDashArray.end(), 0.0); 276 } 277 278 if(rCandidate.count() && fFullDashDotLen > 0.0) 279 { 280 B2DPolyPolygon aLineTarget, aGapTarget; 281 282 for(sal_uInt32 a(0L); a < rCandidate.count(); a++) 283 { 284 const B2DPolygon aCandidate(rCandidate.getB2DPolygon(a)); 285 286 applyLineDashing( 287 aCandidate, 288 rDotDashArray, 289 pLineTarget ? &aLineTarget : 0, 290 pGapTarget ? &aGapTarget : 0, 291 fFullDashDotLen); 292 293 if(pLineTarget) 294 { 295 pLineTarget->append(aLineTarget); 296 } 297 298 if(pGapTarget) 299 { 300 pGapTarget->append(aGapTarget); 301 } 302 } 303 } 304 } 305 306 bool isInEpsilonRange(const B2DPolyPolygon& rCandidate, const B2DPoint& rTestPosition, double fDistance) 307 { 308 const sal_uInt32 nPolygonCount(rCandidate.count()); 309 310 for(sal_uInt32 a(0L); a < nPolygonCount; a++) 311 { 312 B2DPolygon aCandidate(rCandidate.getB2DPolygon(a)); 313 314 if(isInEpsilonRange(aCandidate, rTestPosition, fDistance)) 315 { 316 return true; 317 } 318 } 319 320 return false; 321 } 322 323 B3DPolyPolygon createB3DPolyPolygonFromB2DPolyPolygon(const B2DPolyPolygon& rCandidate, double fZCoordinate) 324 { 325 const sal_uInt32 nPolygonCount(rCandidate.count()); 326 B3DPolyPolygon aRetval; 327 328 for(sal_uInt32 a(0L); a < nPolygonCount; a++) 329 { 330 B2DPolygon aCandidate(rCandidate.getB2DPolygon(a)); 331 332 aRetval.append(createB3DPolygonFromB2DPolygon(aCandidate, fZCoordinate)); 333 } 334 335 return aRetval; 336 } 337 338 B2DPolyPolygon createB2DPolyPolygonFromB3DPolyPolygon(const B3DPolyPolygon& rCandidate, const B3DHomMatrix& rMat) 339 { 340 const sal_uInt32 nPolygonCount(rCandidate.count()); 341 B2DPolyPolygon aRetval; 342 343 for(sal_uInt32 a(0L); a < nPolygonCount; a++) 344 { 345 B3DPolygon aCandidate(rCandidate.getB3DPolygon(a)); 346 347 aRetval.append(createB2DPolygonFromB3DPolygon(aCandidate, rMat)); 348 } 349 350 return aRetval; 351 } 352 353 double getSmallestDistancePointToPolyPolygon(const B2DPolyPolygon& rCandidate, const B2DPoint& rTestPoint, sal_uInt32& rPolygonIndex, sal_uInt32& rEdgeIndex, double& rCut) 354 { 355 double fRetval(DBL_MAX); 356 const double fZero(0.0); 357 const sal_uInt32 nPolygonCount(rCandidate.count()); 358 359 for(sal_uInt32 a(0L); a < nPolygonCount; a++) 360 { 361 const B2DPolygon aCandidate(rCandidate.getB2DPolygon(a)); 362 sal_uInt32 nNewEdgeIndex; 363 double fNewCut; 364 const double fNewDistance(getSmallestDistancePointToPolygon(aCandidate, rTestPoint, nNewEdgeIndex, fNewCut)); 365 366 if(DBL_MAX == fRetval || fNewDistance < fRetval) 367 { 368 fRetval = fNewDistance; 369 rPolygonIndex = a; 370 rEdgeIndex = nNewEdgeIndex; 371 rCut = fNewCut; 372 373 if(fTools::equal(fRetval, fZero)) 374 { 375 // already found zero distance, cannot get better. Ensure numerical zero value and end loop. 376 fRetval = 0.0; 377 break; 378 } 379 } 380 } 381 382 return fRetval; 383 } 384 385 B2DPolyPolygon distort(const B2DPolyPolygon& rCandidate, const B2DRange& rOriginal, const B2DPoint& rTopLeft, const B2DPoint& rTopRight, const B2DPoint& rBottomLeft, const B2DPoint& rBottomRight) 386 { 387 const sal_uInt32 nPolygonCount(rCandidate.count()); 388 B2DPolyPolygon aRetval; 389 390 for(sal_uInt32 a(0L); a < nPolygonCount; a++) 391 { 392 const B2DPolygon aCandidate(rCandidate.getB2DPolygon(a)); 393 394 aRetval.append(distort(aCandidate, rOriginal, rTopLeft, rTopRight, rBottomLeft, rBottomRight)); 395 } 396 397 return aRetval; 398 } 399 400 B2DPolyPolygon rotateAroundPoint(const B2DPolyPolygon& rCandidate, const B2DPoint& rCenter, double fAngle) 401 { 402 const sal_uInt32 nPolygonCount(rCandidate.count()); 403 B2DPolyPolygon aRetval; 404 405 for(sal_uInt32 a(0L); a < nPolygonCount; a++) 406 { 407 const B2DPolygon aCandidate(rCandidate.getB2DPolygon(a)); 408 409 aRetval.append(rotateAroundPoint(aCandidate, rCenter, fAngle)); 410 } 411 412 return aRetval; 413 } 414 415 B2DPolyPolygon expandToCurve(const B2DPolyPolygon& rCandidate) 416 { 417 const sal_uInt32 nPolygonCount(rCandidate.count()); 418 B2DPolyPolygon aRetval; 419 420 for(sal_uInt32 a(0L); a < nPolygonCount; a++) 421 { 422 const B2DPolygon aCandidate(rCandidate.getB2DPolygon(a)); 423 424 aRetval.append(expandToCurve(aCandidate)); 425 } 426 427 return aRetval; 428 } 429 430 B2DPolyPolygon setContinuity(const B2DPolyPolygon& rCandidate, B2VectorContinuity eContinuity) 431 { 432 if(rCandidate.areControlPointsUsed()) 433 { 434 const sal_uInt32 nPolygonCount(rCandidate.count()); 435 B2DPolyPolygon aRetval; 436 437 for(sal_uInt32 a(0L); a < nPolygonCount; a++) 438 { 439 const B2DPolygon aCandidate(rCandidate.getB2DPolygon(a)); 440 441 aRetval.append(setContinuity(aCandidate, eContinuity)); 442 } 443 444 return aRetval; 445 } 446 else 447 { 448 return rCandidate; 449 } 450 } 451 452 B2DPolyPolygon growInNormalDirection(const B2DPolyPolygon& rCandidate, double fValue) 453 { 454 if(0.0 != fValue) 455 { 456 B2DPolyPolygon aRetval; 457 458 for(sal_uInt32 a(0L); a < rCandidate.count(); a++) 459 { 460 aRetval.append(growInNormalDirection(rCandidate.getB2DPolygon(a), fValue)); 461 } 462 463 return aRetval; 464 } 465 else 466 { 467 return rCandidate; 468 } 469 } 470 471 void correctGrowShrinkPolygonPair(B2DPolyPolygon& /*rOriginal*/, B2DPolyPolygon& /*rGrown*/) 472 { 473 } 474 475 B2DPolyPolygon reSegmentPolyPolygon(const B2DPolyPolygon& rCandidate, sal_uInt32 nSegments) 476 { 477 B2DPolyPolygon aRetval; 478 479 for(sal_uInt32 a(0L); a < rCandidate.count(); a++) 480 { 481 aRetval.append(reSegmentPolygon(rCandidate.getB2DPolygon(a), nSegments)); 482 } 483 484 return aRetval; 485 } 486 487 B2DPolyPolygon interpolate(const B2DPolyPolygon& rOld1, const B2DPolyPolygon& rOld2, double t) 488 { 489 OSL_ENSURE(rOld1.count() == rOld2.count(), "B2DPolyPolygon interpolate: Different geometry (!)"); 490 B2DPolyPolygon aRetval; 491 492 for(sal_uInt32 a(0L); a < rOld1.count(); a++) 493 { 494 aRetval.append(interpolate(rOld1.getB2DPolygon(a), rOld2.getB2DPolygon(a), t)); 495 } 496 497 return aRetval; 498 } 499 500 bool isRectangle( const B2DPolyPolygon& rPoly ) 501 { 502 // exclude some cheap cases first 503 if( rPoly.count() != 1 ) 504 return false; 505 506 return isRectangle( rPoly.getB2DPolygon(0) ); 507 } 508 509 // #i76891# 510 B2DPolyPolygon simplifyCurveSegments(const B2DPolyPolygon& rCandidate) 511 { 512 if(rCandidate.areControlPointsUsed()) 513 { 514 B2DPolyPolygon aRetval; 515 516 for(sal_uInt32 a(0L); a < rCandidate.count(); a++) 517 { 518 aRetval.append(simplifyCurveSegments(rCandidate.getB2DPolygon(a))); 519 } 520 521 return aRetval; 522 } 523 else 524 { 525 return rCandidate; 526 } 527 } 528 529 B2DPolyPolygon reSegmentPolyPolygonEdges(const B2DPolyPolygon& rCandidate, sal_uInt32 nSubEdges, bool bHandleCurvedEdges, bool bHandleStraightEdges) 530 { 531 B2DPolyPolygon aRetval; 532 533 for(sal_uInt32 a(0L); a < rCandidate.count(); a++) 534 { 535 aRetval.append(reSegmentPolygonEdges(rCandidate.getB2DPolygon(a), nSubEdges, bHandleCurvedEdges, bHandleStraightEdges)); 536 } 537 538 return aRetval; 539 } 540 541 ////////////////////////////////////////////////////////////////////// 542 // comparators with tolerance for 2D PolyPolygons 543 544 bool equal(const B2DPolyPolygon& rCandidateA, const B2DPolyPolygon& rCandidateB, const double& rfSmallValue) 545 { 546 const sal_uInt32 nPolygonCount(rCandidateA.count()); 547 548 if(nPolygonCount != rCandidateB.count()) 549 return false; 550 551 for(sal_uInt32 a(0); a < nPolygonCount; a++) 552 { 553 const B2DPolygon aCandidate(rCandidateA.getB2DPolygon(a)); 554 555 if(!equal(aCandidate, rCandidateB.getB2DPolygon(a), rfSmallValue)) 556 return false; 557 } 558 559 return true; 560 } 561 562 bool equal(const B2DPolyPolygon& rCandidateA, const B2DPolyPolygon& rCandidateB) 563 { 564 const double fSmallValue(fTools::getSmallValue()); 565 566 return equal(rCandidateA, rCandidateB, fSmallValue); 567 } 568 569 B2DPolyPolygon snapPointsOfHorizontalOrVerticalEdges(const B2DPolyPolygon& rCandidate) 570 { 571 B2DPolyPolygon aRetval; 572 573 for(sal_uInt32 a(0L); a < rCandidate.count(); a++) 574 { 575 aRetval.append(snapPointsOfHorizontalOrVerticalEdges(rCandidate.getB2DPolygon(a))); 576 } 577 578 return aRetval; 579 } 580 581 } // end of namespace tools 582 } // end of namespace basegfx 583 584 ////////////////////////////////////////////////////////////////////////////// 585 // eof 586