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