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/numeric/ftools.hxx> 31 #include <basegfx/polygon/b2dpolygontools.hxx> 32 #include <osl/diagnose.h> 33 #include <rtl/math.hxx> 34 #include <basegfx/polygon/b2dpolygon.hxx> 35 #include <basegfx/polygon/b2dpolypolygon.hxx> 36 #include <basegfx/range/b2drange.hxx> 37 #include <basegfx/curve/b2dcubicbezier.hxx> 38 #include <basegfx/polygon/b2dpolypolygoncutter.hxx> 39 #include <basegfx/point/b3dpoint.hxx> 40 #include <basegfx/matrix/b3dhommatrix.hxx> 41 #include <basegfx/matrix/b2dhommatrix.hxx> 42 #include <basegfx/curve/b2dbeziertools.hxx> 43 #include <basegfx/matrix/b2dhommatrixtools.hxx> 44 #include <osl/mutex.hxx> 45 46 #include <numeric> 47 #include <limits> 48 49 // #i37443# 50 #define ANGLE_BOUND_START_VALUE (2.25) 51 #define ANGLE_BOUND_MINIMUM_VALUE (0.1) 52 #define COUNT_SUBDIVIDE_DEFAULT (4L) 53 #ifdef DBG_UTIL 54 static double fAngleBoundStartValue = ANGLE_BOUND_START_VALUE; 55 #endif 56 #define STEPSPERQUARTER (3) 57 58 ////////////////////////////////////////////////////////////////////////////// 59 60 namespace basegfx 61 { 62 namespace tools 63 { 64 void openWithGeometryChange(B2DPolygon& rCandidate) 65 { 66 if(rCandidate.isClosed()) 67 { 68 if(rCandidate.count()) 69 { 70 rCandidate.append(rCandidate.getB2DPoint(0)); 71 72 if(rCandidate.areControlPointsUsed() && rCandidate.isPrevControlPointUsed(0)) 73 { 74 rCandidate.setPrevControlPoint(rCandidate.count() - 1, rCandidate.getPrevControlPoint(0)); 75 rCandidate.resetPrevControlPoint(0); 76 } 77 } 78 79 rCandidate.setClosed(false); 80 } 81 } 82 83 void closeWithGeometryChange(B2DPolygon& rCandidate) 84 { 85 if(!rCandidate.isClosed()) 86 { 87 while(rCandidate.count() > 1 && rCandidate.getB2DPoint(0) == rCandidate.getB2DPoint(rCandidate.count() - 1)) 88 { 89 if(rCandidate.areControlPointsUsed() && rCandidate.isPrevControlPointUsed(rCandidate.count() - 1)) 90 { 91 rCandidate.setPrevControlPoint(0, rCandidate.getPrevControlPoint(rCandidate.count() - 1)); 92 } 93 94 rCandidate.remove(rCandidate.count() - 1); 95 } 96 97 rCandidate.setClosed(true); 98 } 99 } 100 101 void checkClosed(B2DPolygon& rCandidate) 102 { 103 // #i80172# Removed unnecessary assertion 104 // OSL_ENSURE(!rCandidate.isClosed(), "checkClosed: already closed (!)"); 105 106 if(rCandidate.count() > 1 && rCandidate.getB2DPoint(0) == rCandidate.getB2DPoint(rCandidate.count() - 1)) 107 { 108 closeWithGeometryChange(rCandidate); 109 } 110 } 111 112 // Get successor and predecessor indices. Returning the same index means there 113 // is none. Same for successor. 114 sal_uInt32 getIndexOfPredecessor(sal_uInt32 nIndex, const B2DPolygon& rCandidate) 115 { 116 OSL_ENSURE(nIndex < rCandidate.count(), "getIndexOfPredecessor: Access to polygon out of range (!)"); 117 118 if(nIndex) 119 { 120 return nIndex - 1L; 121 } 122 else if(rCandidate.count()) 123 { 124 return rCandidate.count() - 1L; 125 } 126 else 127 { 128 return nIndex; 129 } 130 } 131 132 sal_uInt32 getIndexOfSuccessor(sal_uInt32 nIndex, const B2DPolygon& rCandidate) 133 { 134 OSL_ENSURE(nIndex < rCandidate.count(), "getIndexOfPredecessor: Access to polygon out of range (!)"); 135 136 if(nIndex + 1L < rCandidate.count()) 137 { 138 return nIndex + 1L; 139 } 140 else if(nIndex + 1L == rCandidate.count()) 141 { 142 return 0L; 143 } 144 else 145 { 146 return nIndex; 147 } 148 } 149 150 B2VectorOrientation getOrientation(const B2DPolygon& rCandidate) 151 { 152 B2VectorOrientation eRetval(ORIENTATION_NEUTRAL); 153 154 if(rCandidate.count() > 2L || rCandidate.areControlPointsUsed()) 155 { 156 const double fSignedArea(getSignedArea(rCandidate)); 157 158 if(fTools::equalZero(fSignedArea)) 159 { 160 // ORIENTATION_NEUTRAL, already set 161 } 162 if(fSignedArea > 0.0) 163 { 164 eRetval = ORIENTATION_POSITIVE; 165 } 166 else if(fSignedArea < 0.0) 167 { 168 eRetval = ORIENTATION_NEGATIVE; 169 } 170 } 171 172 return eRetval; 173 } 174 175 B2VectorContinuity getContinuityInPoint(const B2DPolygon& rCandidate, sal_uInt32 nIndex) 176 { 177 return rCandidate.getContinuityInPoint(nIndex); 178 } 179 180 B2DPolygon adaptiveSubdivideByDistance(const B2DPolygon& rCandidate, double fDistanceBound) 181 { 182 if(rCandidate.areControlPointsUsed()) 183 { 184 const sal_uInt32 nPointCount(rCandidate.count()); 185 B2DPolygon aRetval; 186 187 if(nPointCount) 188 { 189 // prepare edge-oriented loop 190 const sal_uInt32 nEdgeCount(rCandidate.isClosed() ? nPointCount : nPointCount - 1); 191 B2DCubicBezier aBezier; 192 aBezier.setStartPoint(rCandidate.getB2DPoint(0)); 193 194 // perf: try to avoid too many realloctions by guessing the result's pointcount 195 aRetval.reserve(nPointCount*4); 196 197 // add start point (always) 198 aRetval.append(aBezier.getStartPoint()); 199 200 for(sal_uInt32 a(0L); a < nEdgeCount; a++) 201 { 202 // get next and control points 203 const sal_uInt32 nNextIndex((a + 1) % nPointCount); 204 aBezier.setEndPoint(rCandidate.getB2DPoint(nNextIndex)); 205 aBezier.setControlPointA(rCandidate.getNextControlPoint(a)); 206 aBezier.setControlPointB(rCandidate.getPrevControlPoint(nNextIndex)); 207 aBezier.testAndSolveTrivialBezier(); 208 209 if(aBezier.isBezier()) 210 { 211 // add curved edge and generate DistanceBound 212 double fBound(0.0); 213 214 if(0.0 == fDistanceBound) 215 { 216 // If not set, use B2DCubicBezier functionality to guess a rough value 217 const double fRoughLength((aBezier.getEdgeLength() + aBezier.getControlPolygonLength()) / 2.0); 218 219 // take 1/100th of the rough curve length 220 fBound = fRoughLength * 0.01; 221 } 222 else 223 { 224 // use given bound value 225 fBound = fDistanceBound; 226 } 227 228 // make sure bound value is not too small. The base units are 1/100th mm, thus 229 // just make sure it's not smaller then 1/100th of that 230 if(fBound < 0.01) 231 { 232 fBound = 0.01; 233 } 234 235 // call adaptive subdivide which adds edges to aRetval accordingly 236 aBezier.adaptiveSubdivideByDistance(aRetval, fBound); 237 } 238 else 239 { 240 // add non-curved edge 241 aRetval.append(aBezier.getEndPoint()); 242 } 243 244 // prepare next step 245 aBezier.setStartPoint(aBezier.getEndPoint()); 246 } 247 248 if(rCandidate.isClosed()) 249 { 250 // set closed flag and correct last point (which is added double now). 251 closeWithGeometryChange(aRetval); 252 } 253 } 254 255 return aRetval; 256 } 257 else 258 { 259 return rCandidate; 260 } 261 } 262 263 B2DPolygon adaptiveSubdivideByAngle(const B2DPolygon& rCandidate, double fAngleBound) 264 { 265 if(rCandidate.areControlPointsUsed()) 266 { 267 const sal_uInt32 nPointCount(rCandidate.count()); 268 B2DPolygon aRetval; 269 270 if(nPointCount) 271 { 272 // prepare edge-oriented loop 273 const sal_uInt32 nEdgeCount(rCandidate.isClosed() ? nPointCount : nPointCount - 1); 274 B2DCubicBezier aBezier; 275 aBezier.setStartPoint(rCandidate.getB2DPoint(0)); 276 277 // perf: try to avoid too many realloctions by guessing the result's pointcount 278 aRetval.reserve(nPointCount*4); 279 280 // add start point (always) 281 aRetval.append(aBezier.getStartPoint()); 282 283 // #i37443# prepare convenient AngleBound if none was given 284 if(0.0 == fAngleBound) 285 { 286 #ifdef DBG_UTIL 287 fAngleBound = fAngleBoundStartValue; 288 #else 289 fAngleBound = ANGLE_BOUND_START_VALUE; 290 #endif 291 } 292 else if(fTools::less(fAngleBound, ANGLE_BOUND_MINIMUM_VALUE)) 293 { 294 fAngleBound = 0.1; 295 } 296 297 for(sal_uInt32 a(0L); a < nEdgeCount; a++) 298 { 299 // get next and control points 300 const sal_uInt32 nNextIndex((a + 1) % nPointCount); 301 aBezier.setEndPoint(rCandidate.getB2DPoint(nNextIndex)); 302 aBezier.setControlPointA(rCandidate.getNextControlPoint(a)); 303 aBezier.setControlPointB(rCandidate.getPrevControlPoint(nNextIndex)); 304 aBezier.testAndSolveTrivialBezier(); 305 306 if(aBezier.isBezier()) 307 { 308 // call adaptive subdivide 309 aBezier.adaptiveSubdivideByAngle(aRetval, fAngleBound, true); 310 } 311 else 312 { 313 // add non-curved edge 314 aRetval.append(aBezier.getEndPoint()); 315 } 316 317 // prepare next step 318 aBezier.setStartPoint(aBezier.getEndPoint()); 319 } 320 321 if(rCandidate.isClosed()) 322 { 323 // set closed flag and correct last point (which is added double now). 324 closeWithGeometryChange(aRetval); 325 } 326 } 327 328 return aRetval; 329 } 330 else 331 { 332 return rCandidate; 333 } 334 } 335 336 B2DPolygon adaptiveSubdivideByCount(const B2DPolygon& rCandidate, sal_uInt32 nCount) 337 { 338 if(rCandidate.areControlPointsUsed()) 339 { 340 const sal_uInt32 nPointCount(rCandidate.count()); 341 B2DPolygon aRetval; 342 343 if(nPointCount) 344 { 345 // prepare edge-oriented loop 346 const sal_uInt32 nEdgeCount(rCandidate.isClosed() ? nPointCount : nPointCount - 1); 347 B2DCubicBezier aBezier; 348 aBezier.setStartPoint(rCandidate.getB2DPoint(0)); 349 350 // perf: try to avoid too many realloctions by guessing the result's pointcount 351 aRetval.reserve(nPointCount*4); 352 353 // add start point (always) 354 aRetval.append(aBezier.getStartPoint()); 355 356 // #i37443# prepare convenient count if none was given 357 if(0L == nCount) 358 { 359 nCount = COUNT_SUBDIVIDE_DEFAULT; 360 } 361 362 for(sal_uInt32 a(0L); a < nEdgeCount; a++) 363 { 364 // get next and control points 365 const sal_uInt32 nNextIndex((a + 1) % nPointCount); 366 aBezier.setEndPoint(rCandidate.getB2DPoint(nNextIndex)); 367 aBezier.setControlPointA(rCandidate.getNextControlPoint(a)); 368 aBezier.setControlPointB(rCandidate.getPrevControlPoint(nNextIndex)); 369 aBezier.testAndSolveTrivialBezier(); 370 371 if(aBezier.isBezier()) 372 { 373 // call adaptive subdivide 374 aBezier.adaptiveSubdivideByCount(aRetval, nCount); 375 } 376 else 377 { 378 // add non-curved edge 379 aRetval.append(aBezier.getEndPoint()); 380 } 381 382 // prepare next step 383 aBezier.setStartPoint(aBezier.getEndPoint()); 384 } 385 386 if(rCandidate.isClosed()) 387 { 388 // set closed flag and correct last point (which is added double now). 389 closeWithGeometryChange(aRetval); 390 } 391 } 392 393 return aRetval; 394 } 395 else 396 { 397 return rCandidate; 398 } 399 } 400 401 bool isInside(const B2DPolygon& rCandidate, const B2DPoint& rPoint, bool bWithBorder) 402 { 403 const B2DPolygon aCandidate(rCandidate.areControlPointsUsed() ? rCandidate.getDefaultAdaptiveSubdivision() : rCandidate); 404 405 if(bWithBorder && isPointOnPolygon(aCandidate, rPoint, true)) 406 { 407 return true; 408 } 409 else 410 { 411 bool bRetval(false); 412 const sal_uInt32 nPointCount(aCandidate.count()); 413 414 if(nPointCount) 415 { 416 B2DPoint aCurrentPoint(aCandidate.getB2DPoint(nPointCount - 1L)); 417 418 for(sal_uInt32 a(0L); a < nPointCount; a++) 419 { 420 const B2DPoint aPreviousPoint(aCurrentPoint); 421 aCurrentPoint = aCandidate.getB2DPoint(a); 422 423 // cross-over in Y? 424 const bool bCompYA(fTools::more(aPreviousPoint.getY(), rPoint.getY())); 425 const bool bCompYB(fTools::more(aCurrentPoint.getY(), rPoint.getY())); 426 427 if(bCompYA != bCompYB) 428 { 429 // cross-over in X? 430 const bool bCompXA(fTools::more(aPreviousPoint.getX(), rPoint.getX())); 431 const bool bCompXB(fTools::more(aCurrentPoint.getX(), rPoint.getX())); 432 433 if(bCompXA == bCompXB) 434 { 435 if(bCompXA) 436 { 437 bRetval = !bRetval; 438 } 439 } 440 else 441 { 442 const double fCompare( 443 aCurrentPoint.getX() - (aCurrentPoint.getY() - rPoint.getY()) * 444 (aPreviousPoint.getX() - aCurrentPoint.getX()) / 445 (aPreviousPoint.getY() - aCurrentPoint.getY())); 446 447 if(fTools::more(fCompare, rPoint.getX())) 448 { 449 bRetval = !bRetval; 450 } 451 } 452 } 453 } 454 } 455 456 return bRetval; 457 } 458 } 459 460 bool isInside(const B2DPolygon& rCandidate, const B2DPolygon& rPolygon, bool bWithBorder) 461 { 462 const B2DPolygon aCandidate(rCandidate.areControlPointsUsed() ? rCandidate.getDefaultAdaptiveSubdivision() : rCandidate); 463 const B2DPolygon aPolygon(rPolygon.areControlPointsUsed() ? rPolygon.getDefaultAdaptiveSubdivision() : rPolygon); 464 const sal_uInt32 nPointCount(aPolygon.count()); 465 466 for(sal_uInt32 a(0L); a < nPointCount; a++) 467 { 468 const B2DPoint aTestPoint(aPolygon.getB2DPoint(a)); 469 470 if(!isInside(aCandidate, aTestPoint, bWithBorder)) 471 { 472 return false; 473 } 474 } 475 476 return true; 477 } 478 479 B2DRange getRangeWithControlPoints(const B2DPolygon& rCandidate) 480 { 481 const sal_uInt32 nPointCount(rCandidate.count()); 482 B2DRange aRetval; 483 484 if(nPointCount) 485 { 486 const bool bControlPointsUsed(rCandidate.areControlPointsUsed()); 487 488 for(sal_uInt32 a(0); a < nPointCount; a++) 489 { 490 aRetval.expand(rCandidate.getB2DPoint(a)); 491 492 if(bControlPointsUsed) 493 { 494 aRetval.expand(rCandidate.getNextControlPoint(a)); 495 aRetval.expand(rCandidate.getPrevControlPoint(a)); 496 } 497 } 498 } 499 500 return aRetval; 501 } 502 503 B2DRange getRange(const B2DPolygon& rCandidate) 504 { 505 // changed to use internally buffered version at B2DPolygon 506 return rCandidate.getB2DRange(); 507 } 508 509 double getSignedArea(const B2DPolygon& rCandidate) 510 { 511 const B2DPolygon aCandidate(rCandidate.areControlPointsUsed() ? rCandidate.getDefaultAdaptiveSubdivision() : rCandidate); 512 double fRetval(0.0); 513 const sal_uInt32 nPointCount(aCandidate.count()); 514 515 if(nPointCount > 2) 516 { 517 for(sal_uInt32 a(0L); a < nPointCount; a++) 518 { 519 const B2DPoint aPreviousPoint(aCandidate.getB2DPoint((!a) ? nPointCount - 1L : a - 1L)); 520 const B2DPoint aCurrentPoint(aCandidate.getB2DPoint(a)); 521 522 fRetval += aPreviousPoint.getX() * aCurrentPoint.getY(); 523 fRetval -= aPreviousPoint.getY() * aCurrentPoint.getX(); 524 } 525 526 fRetval /= 2.0; 527 528 // correct to zero if small enough. Also test the quadratic 529 // of the result since the precision is near quadratic due to 530 // the algorithm 531 if(fTools::equalZero(fRetval) || fTools::equalZero(fRetval * fRetval)) 532 { 533 fRetval = 0.0; 534 } 535 } 536 537 return fRetval; 538 } 539 540 double getArea(const B2DPolygon& rCandidate) 541 { 542 double fRetval(0.0); 543 544 if(rCandidate.count() > 2 || rCandidate.areControlPointsUsed()) 545 { 546 fRetval = getSignedArea(rCandidate); 547 const double fZero(0.0); 548 549 if(fTools::less(fRetval, fZero)) 550 { 551 fRetval = -fRetval; 552 } 553 } 554 555 return fRetval; 556 } 557 558 double getEdgeLength(const B2DPolygon& rCandidate, sal_uInt32 nIndex) 559 { 560 const sal_uInt32 nPointCount(rCandidate.count()); 561 OSL_ENSURE(nIndex < nPointCount, "getEdgeLength: Access to polygon out of range (!)"); 562 double fRetval(0.0); 563 564 if(nPointCount) 565 { 566 const sal_uInt32 nNextIndex((nIndex + 1) % nPointCount); 567 568 if(rCandidate.areControlPointsUsed()) 569 { 570 B2DCubicBezier aEdge; 571 572 aEdge.setStartPoint(rCandidate.getB2DPoint(nIndex)); 573 aEdge.setControlPointA(rCandidate.getNextControlPoint(nIndex)); 574 aEdge.setControlPointB(rCandidate.getPrevControlPoint(nNextIndex)); 575 aEdge.setEndPoint(rCandidate.getB2DPoint(nNextIndex)); 576 577 fRetval = aEdge.getLength(); 578 } 579 else 580 { 581 const B2DPoint aCurrent(rCandidate.getB2DPoint(nIndex)); 582 const B2DPoint aNext(rCandidate.getB2DPoint(nNextIndex)); 583 584 fRetval = B2DVector(aNext - aCurrent).getLength(); 585 } 586 } 587 588 return fRetval; 589 } 590 591 double getLength(const B2DPolygon& rCandidate) 592 { 593 double fRetval(0.0); 594 const sal_uInt32 nPointCount(rCandidate.count()); 595 596 if(nPointCount) 597 { 598 const sal_uInt32 nEdgeCount(rCandidate.isClosed() ? nPointCount : nPointCount - 1L); 599 600 if(rCandidate.areControlPointsUsed()) 601 { 602 B2DCubicBezier aEdge; 603 aEdge.setStartPoint(rCandidate.getB2DPoint(0)); 604 605 for(sal_uInt32 a(0); a < nEdgeCount; a++) 606 { 607 const sal_uInt32 nNextIndex((a + 1) % nPointCount); 608 aEdge.setControlPointA(rCandidate.getNextControlPoint(a)); 609 aEdge.setControlPointB(rCandidate.getPrevControlPoint(nNextIndex)); 610 aEdge.setEndPoint(rCandidate.getB2DPoint(nNextIndex)); 611 612 fRetval += aEdge.getLength(); 613 aEdge.setStartPoint(aEdge.getEndPoint()); 614 } 615 } 616 else 617 { 618 B2DPoint aCurrent(rCandidate.getB2DPoint(0)); 619 620 for(sal_uInt32 a(0); a < nEdgeCount; a++) 621 { 622 const sal_uInt32 nNextIndex((a + 1) % nPointCount); 623 const B2DPoint aNext(rCandidate.getB2DPoint(nNextIndex)); 624 625 fRetval += B2DVector(aNext - aCurrent).getLength(); 626 aCurrent = aNext; 627 } 628 } 629 } 630 631 return fRetval; 632 } 633 634 B2DPoint getPositionAbsolute(const B2DPolygon& rCandidate, double fDistance, double fLength) 635 { 636 B2DPoint aRetval; 637 const sal_uInt32 nPointCount(rCandidate.count()); 638 639 if( 1L == nPointCount ) 640 { 641 // only one point (i.e. no edge) - simply take that point 642 aRetval = rCandidate.getB2DPoint(0); 643 } 644 else if(nPointCount > 1L) 645 { 646 const sal_uInt32 nEdgeCount(rCandidate.isClosed() ? nPointCount : nPointCount - 1); 647 sal_uInt32 nIndex(0L); 648 bool bIndexDone(false); 649 650 // get length if not given 651 if(fTools::equalZero(fLength)) 652 { 653 fLength = getLength(rCandidate); 654 } 655 656 if(fTools::less(fDistance, 0.0)) 657 { 658 // handle fDistance < 0.0 659 if(rCandidate.isClosed()) 660 { 661 // if fDistance < 0.0 increment with multiple of fLength 662 sal_uInt32 nCount(sal_uInt32(-fDistance / fLength)); 663 fDistance += double(nCount + 1L) * fLength; 664 } 665 else 666 { 667 // crop to polygon start 668 fDistance = 0.0; 669 bIndexDone = true; 670 } 671 } 672 else if(fTools::moreOrEqual(fDistance, fLength)) 673 { 674 // handle fDistance >= fLength 675 if(rCandidate.isClosed()) 676 { 677 // if fDistance >= fLength decrement with multiple of fLength 678 sal_uInt32 nCount(sal_uInt32(fDistance / fLength)); 679 fDistance -= (double)(nCount) * fLength; 680 } 681 else 682 { 683 // crop to polygon end 684 fDistance = 0.0; 685 nIndex = nEdgeCount; 686 bIndexDone = true; 687 } 688 } 689 690 // look for correct index. fDistance is now [0.0 .. fLength[ 691 double fEdgeLength(getEdgeLength(rCandidate, nIndex)); 692 693 while(!bIndexDone) 694 { 695 // edge found must be on the half-open range 696 // [0,fEdgeLength). 697 // Note that in theory, we cannot move beyond 698 // the last polygon point, since fDistance>=fLength 699 // is checked above. Unfortunately, with floating- 700 // point calculations, this case might happen. 701 // Handled by nIndex check below 702 if(nIndex < nEdgeCount && fTools::moreOrEqual(fDistance, fEdgeLength)) 703 { 704 // go to next edge 705 fDistance -= fEdgeLength; 706 fEdgeLength = getEdgeLength(rCandidate, ++nIndex); 707 } 708 else 709 { 710 // it's on this edge, stop 711 bIndexDone = true; 712 } 713 } 714 715 // get the point using nIndex 716 aRetval = rCandidate.getB2DPoint(nIndex); 717 718 // if fDistance != 0.0, move that length on the edge. The edge 719 // length is in fEdgeLength. 720 if(!fTools::equalZero(fDistance)) 721 { 722 if(fTools::moreOrEqual(fDistance, fEdgeLength)) 723 { 724 // end point of choosen edge 725 const sal_uInt32 nNextIndex((nIndex + 1) % nPointCount); 726 aRetval = rCandidate.getB2DPoint(nNextIndex); 727 } 728 else if(fTools::equalZero(fDistance)) 729 { 730 // start point of choosen edge 731 aRetval = aRetval; 732 } 733 else 734 { 735 // inside edge 736 const sal_uInt32 nNextIndex((nIndex + 1) % nPointCount); 737 const B2DPoint aNextPoint(rCandidate.getB2DPoint(nNextIndex)); 738 bool bDone(false); 739 740 // add calculated average value to the return value 741 if(rCandidate.areControlPointsUsed()) 742 { 743 // get as bezier segment 744 const B2DCubicBezier aBezierSegment( 745 aRetval, rCandidate.getNextControlPoint(nIndex), 746 rCandidate.getPrevControlPoint(nNextIndex), aNextPoint); 747 748 if(aBezierSegment.isBezier()) 749 { 750 // use B2DCubicBezierHelper to bridge the non-linear gap between 751 // length and bezier distances 752 const B2DCubicBezierHelper aBezierSegmentHelper(aBezierSegment); 753 const double fBezierDistance(aBezierSegmentHelper.distanceToRelative(fDistance)); 754 755 aRetval = aBezierSegment.interpolatePoint(fBezierDistance); 756 bDone = true; 757 } 758 } 759 760 if(!bDone) 761 { 762 const double fRelativeInEdge(fDistance / fEdgeLength); 763 aRetval = interpolate(aRetval, aNextPoint, fRelativeInEdge); 764 } 765 } 766 } 767 } 768 769 return aRetval; 770 } 771 772 B2DPoint getPositionRelative(const B2DPolygon& rCandidate, double fDistance, double fLength) 773 { 774 // get length if not given 775 if(fTools::equalZero(fLength)) 776 { 777 fLength = getLength(rCandidate); 778 } 779 780 // multiply fDistance with real length to get absolute position and 781 // use getPositionAbsolute 782 return getPositionAbsolute(rCandidate, fDistance * fLength, fLength); 783 } 784 785 B2DPolygon getSnippetAbsolute(const B2DPolygon& rCandidate, double fFrom, double fTo, double fLength) 786 { 787 const sal_uInt32 nPointCount(rCandidate.count()); 788 789 if(nPointCount) 790 { 791 // get length if not given 792 if(fTools::equalZero(fLength)) 793 { 794 fLength = getLength(rCandidate); 795 } 796 797 // test and correct fFrom 798 if(fTools::less(fFrom, 0.0)) 799 { 800 fFrom = 0.0; 801 } 802 803 // test and correct fTo 804 if(fTools::more(fTo, fLength)) 805 { 806 fTo = fLength; 807 } 808 809 // test and correct relationship of fFrom, fTo 810 if(fTools::more(fFrom, fTo)) 811 { 812 fFrom = fTo = (fFrom + fTo) / 2.0; 813 } 814 815 if(fTools::equalZero(fFrom) && fTools::equal(fTo, fLength)) 816 { 817 // no change, result is the whole polygon 818 return rCandidate; 819 } 820 else 821 { 822 B2DPolygon aRetval; 823 const sal_uInt32 nEdgeCount(rCandidate.isClosed() ? nPointCount : nPointCount - 1); 824 double fPositionOfStart(0.0); 825 bool bStartDone(false); 826 bool bEndDone(false); 827 828 for(sal_uInt32 a(0L); !(bStartDone && bEndDone) && a < nEdgeCount; a++) 829 { 830 const double fEdgeLength(getEdgeLength(rCandidate, a)); 831 832 if(!bStartDone) 833 { 834 if(fTools::equalZero(fFrom)) 835 { 836 aRetval.append(rCandidate.getB2DPoint(a)); 837 838 if(rCandidate.areControlPointsUsed()) 839 { 840 aRetval.setNextControlPoint(aRetval.count() - 1, rCandidate.getNextControlPoint(a)); 841 } 842 843 bStartDone = true; 844 } 845 else if(fTools::moreOrEqual(fFrom, fPositionOfStart) && fTools::less(fFrom, fPositionOfStart + fEdgeLength)) 846 { 847 // calculate and add start point 848 if(fTools::equalZero(fEdgeLength)) 849 { 850 aRetval.append(rCandidate.getB2DPoint(a)); 851 852 if(rCandidate.areControlPointsUsed()) 853 { 854 aRetval.setNextControlPoint(aRetval.count() - 1, rCandidate.getNextControlPoint(a)); 855 } 856 } 857 else 858 { 859 const sal_uInt32 nNextIndex((a + 1) % nPointCount); 860 const B2DPoint aStart(rCandidate.getB2DPoint(a)); 861 const B2DPoint aEnd(rCandidate.getB2DPoint(nNextIndex)); 862 bool bDone(false); 863 864 if(rCandidate.areControlPointsUsed()) 865 { 866 const B2DCubicBezier aBezierSegment( 867 aStart, rCandidate.getNextControlPoint(a), 868 rCandidate.getPrevControlPoint(nNextIndex), aEnd); 869 870 if(aBezierSegment.isBezier()) 871 { 872 // use B2DCubicBezierHelper to bridge the non-linear gap between 873 // length and bezier distances 874 const B2DCubicBezierHelper aBezierSegmentHelper(aBezierSegment); 875 const double fBezierDistance(aBezierSegmentHelper.distanceToRelative(fFrom - fPositionOfStart)); 876 B2DCubicBezier aRight; 877 878 aBezierSegment.split(fBezierDistance, 0, &aRight); 879 aRetval.append(aRight.getStartPoint()); 880 aRetval.setNextControlPoint(aRetval.count() - 1, aRight.getControlPointA()); 881 bDone = true; 882 } 883 } 884 885 if(!bDone) 886 { 887 const double fRelValue((fFrom - fPositionOfStart) / fEdgeLength); 888 aRetval.append(interpolate(aStart, aEnd, fRelValue)); 889 } 890 } 891 892 bStartDone = true; 893 894 // if same point, end is done, too. 895 if(fFrom == fTo) 896 { 897 bEndDone = true; 898 } 899 } 900 } 901 902 if(!bEndDone && fTools::moreOrEqual(fTo, fPositionOfStart) && fTools::less(fTo, fPositionOfStart + fEdgeLength)) 903 { 904 // calculate and add end point 905 if(fTools::equalZero(fEdgeLength)) 906 { 907 const sal_uInt32 nNextIndex((a + 1) % nPointCount); 908 aRetval.append(rCandidate.getB2DPoint(nNextIndex)); 909 910 if(rCandidate.areControlPointsUsed()) 911 { 912 aRetval.setPrevControlPoint(aRetval.count() - 1, rCandidate.getPrevControlPoint(nNextIndex)); 913 } 914 } 915 else 916 { 917 const sal_uInt32 nNextIndex((a + 1) % nPointCount); 918 const B2DPoint aStart(rCandidate.getB2DPoint(a)); 919 const B2DPoint aEnd(rCandidate.getB2DPoint(nNextIndex)); 920 bool bDone(false); 921 922 if(rCandidate.areControlPointsUsed()) 923 { 924 const B2DCubicBezier aBezierSegment( 925 aStart, rCandidate.getNextControlPoint(a), 926 rCandidate.getPrevControlPoint(nNextIndex), aEnd); 927 928 if(aBezierSegment.isBezier()) 929 { 930 // use B2DCubicBezierHelper to bridge the non-linear gap between 931 // length and bezier distances 932 const B2DCubicBezierHelper aBezierSegmentHelper(aBezierSegment); 933 const double fBezierDistance(aBezierSegmentHelper.distanceToRelative(fTo - fPositionOfStart)); 934 B2DCubicBezier aLeft; 935 936 aBezierSegment.split(fBezierDistance, &aLeft, 0); 937 aRetval.append(aLeft.getEndPoint()); 938 aRetval.setPrevControlPoint(aRetval.count() - 1, aLeft.getControlPointB()); 939 bDone = true; 940 } 941 } 942 943 if(!bDone) 944 { 945 const double fRelValue((fTo - fPositionOfStart) / fEdgeLength); 946 aRetval.append(interpolate(aStart, aEnd, fRelValue)); 947 } 948 } 949 950 bEndDone = true; 951 } 952 953 if(!bEndDone) 954 { 955 if(bStartDone) 956 { 957 // add segments end point 958 const sal_uInt32 nNextIndex((a + 1) % nPointCount); 959 aRetval.append(rCandidate.getB2DPoint(nNextIndex)); 960 961 if(rCandidate.areControlPointsUsed()) 962 { 963 aRetval.setPrevControlPoint(aRetval.count() - 1, rCandidate.getPrevControlPoint(nNextIndex)); 964 aRetval.setNextControlPoint(aRetval.count() - 1, rCandidate.getNextControlPoint(nNextIndex)); 965 } 966 } 967 968 // increment fPositionOfStart 969 fPositionOfStart += fEdgeLength; 970 } 971 } 972 return aRetval; 973 } 974 } 975 else 976 { 977 return rCandidate; 978 } 979 } 980 981 B2DPolygon getSnippetRelative(const B2DPolygon& rCandidate, double fFrom, double fTo, double fLength) 982 { 983 // get length if not given 984 if(fTools::equalZero(fLength)) 985 { 986 fLength = getLength(rCandidate); 987 } 988 989 // multiply distances with real length to get absolute position and 990 // use getSnippetAbsolute 991 return getSnippetAbsolute(rCandidate, fFrom * fLength, fTo * fLength, fLength); 992 } 993 994 CutFlagValue findCut( 995 const B2DPolygon& rCandidate, 996 sal_uInt32 nIndex1, sal_uInt32 nIndex2, 997 CutFlagValue aCutFlags, 998 double* pCut1, double* pCut2) 999 { 1000 CutFlagValue aRetval(CUTFLAG_NONE); 1001 const sal_uInt32 nPointCount(rCandidate.count()); 1002 1003 if(nIndex1 < nPointCount && nIndex2 < nPointCount && nIndex1 != nIndex2) 1004 { 1005 sal_uInt32 nEnd1(getIndexOfSuccessor(nIndex1, rCandidate)); 1006 sal_uInt32 nEnd2(getIndexOfSuccessor(nIndex2, rCandidate)); 1007 1008 const B2DPoint aStart1(rCandidate.getB2DPoint(nIndex1)); 1009 const B2DPoint aEnd1(rCandidate.getB2DPoint(nEnd1)); 1010 const B2DVector aVector1(aEnd1 - aStart1); 1011 1012 const B2DPoint aStart2(rCandidate.getB2DPoint(nIndex2)); 1013 const B2DPoint aEnd2(rCandidate.getB2DPoint(nEnd2)); 1014 const B2DVector aVector2(aEnd2 - aStart2); 1015 1016 aRetval = findCut( 1017 aStart1, aVector1, aStart2, aVector2, 1018 aCutFlags, pCut1, pCut2); 1019 } 1020 1021 return aRetval; 1022 } 1023 1024 CutFlagValue findCut( 1025 const B2DPolygon& rCandidate1, sal_uInt32 nIndex1, 1026 const B2DPolygon& rCandidate2, sal_uInt32 nIndex2, 1027 CutFlagValue aCutFlags, 1028 double* pCut1, double* pCut2) 1029 { 1030 CutFlagValue aRetval(CUTFLAG_NONE); 1031 const sal_uInt32 nPointCount1(rCandidate1.count()); 1032 const sal_uInt32 nPointCount2(rCandidate2.count()); 1033 1034 if(nIndex1 < nPointCount1 && nIndex2 < nPointCount2) 1035 { 1036 sal_uInt32 nEnd1(getIndexOfSuccessor(nIndex1, rCandidate1)); 1037 sal_uInt32 nEnd2(getIndexOfSuccessor(nIndex2, rCandidate2)); 1038 1039 const B2DPoint aStart1(rCandidate1.getB2DPoint(nIndex1)); 1040 const B2DPoint aEnd1(rCandidate1.getB2DPoint(nEnd1)); 1041 const B2DVector aVector1(aEnd1 - aStart1); 1042 1043 const B2DPoint aStart2(rCandidate2.getB2DPoint(nIndex2)); 1044 const B2DPoint aEnd2(rCandidate2.getB2DPoint(nEnd2)); 1045 const B2DVector aVector2(aEnd2 - aStart2); 1046 1047 aRetval = findCut( 1048 aStart1, aVector1, aStart2, aVector2, 1049 aCutFlags, pCut1, pCut2); 1050 } 1051 1052 return aRetval; 1053 } 1054 1055 CutFlagValue findCut( 1056 const B2DPoint& rEdge1Start, const B2DVector& rEdge1Delta, 1057 const B2DPoint& rEdge2Start, const B2DVector& rEdge2Delta, 1058 CutFlagValue aCutFlags, 1059 double* pCut1, double* pCut2) 1060 { 1061 CutFlagValue aRetval(CUTFLAG_NONE); 1062 double fCut1(0.0); 1063 double fCut2(0.0); 1064 bool bFinished(!((bool)(aCutFlags & CUTFLAG_ALL))); 1065 1066 // test for same points? 1067 if(!bFinished 1068 && (aCutFlags & (CUTFLAG_START1|CUTFLAG_END1)) 1069 && (aCutFlags & (CUTFLAG_START2|CUTFLAG_END2))) 1070 { 1071 // same startpoint? 1072 if(!bFinished && (aCutFlags & (CUTFLAG_START1|CUTFLAG_START2)) == (CUTFLAG_START1|CUTFLAG_START2)) 1073 { 1074 if(rEdge1Start.equal(rEdge2Start)) 1075 { 1076 bFinished = true; 1077 aRetval = (CUTFLAG_START1|CUTFLAG_START2); 1078 } 1079 } 1080 1081 // same endpoint? 1082 if(!bFinished && (aCutFlags & (CUTFLAG_END1|CUTFLAG_END2)) == (CUTFLAG_END1|CUTFLAG_END2)) 1083 { 1084 const B2DPoint aEnd1(rEdge1Start + rEdge1Delta); 1085 const B2DPoint aEnd2(rEdge2Start + rEdge2Delta); 1086 1087 if(aEnd1.equal(aEnd2)) 1088 { 1089 bFinished = true; 1090 aRetval = (CUTFLAG_END1|CUTFLAG_END2); 1091 fCut1 = fCut2 = 1.0; 1092 } 1093 } 1094 1095 // startpoint1 == endpoint2? 1096 if(!bFinished && (aCutFlags & (CUTFLAG_START1|CUTFLAG_END2)) == (CUTFLAG_START1|CUTFLAG_END2)) 1097 { 1098 const B2DPoint aEnd2(rEdge2Start + rEdge2Delta); 1099 1100 if(rEdge1Start.equal(aEnd2)) 1101 { 1102 bFinished = true; 1103 aRetval = (CUTFLAG_START1|CUTFLAG_END2); 1104 fCut1 = 0.0; 1105 fCut2 = 1.0; 1106 } 1107 } 1108 1109 // startpoint2 == endpoint1? 1110 if(!bFinished&& (aCutFlags & (CUTFLAG_START2|CUTFLAG_END1)) == (CUTFLAG_START2|CUTFLAG_END1)) 1111 { 1112 const B2DPoint aEnd1(rEdge1Start + rEdge1Delta); 1113 1114 if(rEdge2Start.equal(aEnd1)) 1115 { 1116 bFinished = true; 1117 aRetval = (CUTFLAG_START2|CUTFLAG_END1); 1118 fCut1 = 1.0; 1119 fCut2 = 0.0; 1120 } 1121 } 1122 } 1123 1124 if(!bFinished && (aCutFlags & CUTFLAG_LINE)) 1125 { 1126 if(!bFinished && (aCutFlags & CUTFLAG_START1)) 1127 { 1128 // start1 on line 2 ? 1129 if(isPointOnEdge(rEdge1Start, rEdge2Start, rEdge2Delta, &fCut2)) 1130 { 1131 bFinished = true; 1132 aRetval = (CUTFLAG_LINE|CUTFLAG_START1); 1133 } 1134 } 1135 1136 if(!bFinished && (aCutFlags & CUTFLAG_START2)) 1137 { 1138 // start2 on line 1 ? 1139 if(isPointOnEdge(rEdge2Start, rEdge1Start, rEdge1Delta, &fCut1)) 1140 { 1141 bFinished = true; 1142 aRetval = (CUTFLAG_LINE|CUTFLAG_START2); 1143 } 1144 } 1145 1146 if(!bFinished && (aCutFlags & CUTFLAG_END1)) 1147 { 1148 // end1 on line 2 ? 1149 const B2DPoint aEnd1(rEdge1Start + rEdge1Delta); 1150 1151 if(isPointOnEdge(aEnd1, rEdge2Start, rEdge2Delta, &fCut2)) 1152 { 1153 bFinished = true; 1154 aRetval = (CUTFLAG_LINE|CUTFLAG_END1); 1155 } 1156 } 1157 1158 if(!bFinished && (aCutFlags & CUTFLAG_END2)) 1159 { 1160 // end2 on line 1 ? 1161 const B2DPoint aEnd2(rEdge2Start + rEdge2Delta); 1162 1163 if(isPointOnEdge(aEnd2, rEdge1Start, rEdge1Delta, &fCut1)) 1164 { 1165 bFinished = true; 1166 aRetval = (CUTFLAG_LINE|CUTFLAG_END2); 1167 } 1168 } 1169 1170 if(!bFinished) 1171 { 1172 // cut in line1, line2 ? 1173 fCut1 = (rEdge1Delta.getX() * rEdge2Delta.getY()) - (rEdge1Delta.getY() * rEdge2Delta.getX()); 1174 1175 if(!fTools::equalZero(fCut1)) 1176 { 1177 fCut1 = (rEdge2Delta.getY() * (rEdge2Start.getX() - rEdge1Start.getX()) 1178 + rEdge2Delta.getX() * (rEdge1Start.getY() - rEdge2Start.getY())) / fCut1; 1179 1180 const double fZero(0.0); 1181 const double fOne(1.0); 1182 1183 // inside parameter range edge1 AND fCut2 is calcable 1184 if(fTools::more(fCut1, fZero) && fTools::less(fCut1, fOne) 1185 && (!fTools::equalZero(rEdge2Delta.getX()) || !fTools::equalZero(rEdge2Delta.getY()))) 1186 { 1187 // take the mopre precise calculation of the two possible 1188 if(fabs(rEdge2Delta.getX()) > fabs(rEdge2Delta.getY())) 1189 { 1190 fCut2 = (rEdge1Start.getX() + fCut1 1191 * rEdge1Delta.getX() - rEdge2Start.getX()) / rEdge2Delta.getX(); 1192 } 1193 else 1194 { 1195 fCut2 = (rEdge1Start.getY() + fCut1 1196 * rEdge1Delta.getY() - rEdge2Start.getY()) / rEdge2Delta.getY(); 1197 } 1198 1199 // inside parameter range edge2, too 1200 if(fTools::more(fCut2, fZero) && fTools::less(fCut2, fOne)) 1201 { 1202 bFinished = true; 1203 aRetval = CUTFLAG_LINE; 1204 } 1205 } 1206 } 1207 } 1208 } 1209 1210 // copy values if wanted 1211 if(pCut1) 1212 { 1213 *pCut1 = fCut1; 1214 } 1215 1216 if(pCut2) 1217 { 1218 *pCut2 = fCut2; 1219 } 1220 1221 return aRetval; 1222 } 1223 1224 bool isPointOnEdge( 1225 const B2DPoint& rPoint, 1226 const B2DPoint& rEdgeStart, 1227 const B2DVector& rEdgeDelta, 1228 double* pCut) 1229 { 1230 bool bDeltaXIsZero(fTools::equalZero(rEdgeDelta.getX())); 1231 bool bDeltaYIsZero(fTools::equalZero(rEdgeDelta.getY())); 1232 const double fZero(0.0); 1233 const double fOne(1.0); 1234 1235 if(bDeltaXIsZero && bDeltaYIsZero) 1236 { 1237 // no line, just a point 1238 return false; 1239 } 1240 else if(bDeltaXIsZero) 1241 { 1242 // vertical line 1243 if(fTools::equal(rPoint.getX(), rEdgeStart.getX())) 1244 { 1245 double fValue = (rPoint.getY() - rEdgeStart.getY()) / rEdgeDelta.getY(); 1246 1247 if(fTools::more(fValue, fZero) && fTools::less(fValue, fOne)) 1248 { 1249 if(pCut) 1250 { 1251 *pCut = fValue; 1252 } 1253 1254 return true; 1255 } 1256 } 1257 } 1258 else if(bDeltaYIsZero) 1259 { 1260 // horizontal line 1261 if(fTools::equal(rPoint.getY(), rEdgeStart.getY())) 1262 { 1263 double fValue = (rPoint.getX() - rEdgeStart.getX()) / rEdgeDelta.getX(); 1264 1265 if(fTools::more(fValue, fZero) && fTools::less(fValue, fOne)) 1266 { 1267 if(pCut) 1268 { 1269 *pCut = fValue; 1270 } 1271 1272 return true; 1273 } 1274 } 1275 } 1276 else 1277 { 1278 // any angle line 1279 double fTOne = (rPoint.getX() - rEdgeStart.getX()) / rEdgeDelta.getX(); 1280 double fTTwo = (rPoint.getY() - rEdgeStart.getY()) / rEdgeDelta.getY(); 1281 1282 if(fTools::equal(fTOne, fTTwo)) 1283 { 1284 // same parameter representation, point is on line. Take 1285 // middle value for better results 1286 double fValue = (fTOne + fTTwo) / 2.0; 1287 1288 if(fTools::more(fValue, fZero) && fTools::less(fValue, fOne)) 1289 { 1290 // point is inside line bounds, too 1291 if(pCut) 1292 { 1293 *pCut = fValue; 1294 } 1295 1296 return true; 1297 } 1298 } 1299 } 1300 1301 return false; 1302 } 1303 1304 void applyLineDashing(const B2DPolygon& rCandidate, const ::std::vector<double>& rDotDashArray, B2DPolyPolygon* pLineTarget, B2DPolyPolygon* pGapTarget, double fDotDashLength) 1305 { 1306 const sal_uInt32 nPointCount(rCandidate.count()); 1307 const sal_uInt32 nDotDashCount(rDotDashArray.size()); 1308 1309 if(fTools::lessOrEqual(fDotDashLength, 0.0)) 1310 { 1311 fDotDashLength = ::std::accumulate(rDotDashArray.begin(), rDotDashArray.end(), 0.0); 1312 } 1313 1314 if(fTools::more(fDotDashLength, 0.0) && (pLineTarget || pGapTarget) && nPointCount) 1315 { 1316 // clear targets 1317 if(pLineTarget) 1318 { 1319 pLineTarget->clear(); 1320 } 1321 1322 if(pGapTarget) 1323 { 1324 pGapTarget->clear(); 1325 } 1326 1327 // prepare current edge's start 1328 B2DCubicBezier aCurrentEdge; 1329 const sal_uInt32 nEdgeCount(rCandidate.isClosed() ? nPointCount : nPointCount - 1); 1330 aCurrentEdge.setStartPoint(rCandidate.getB2DPoint(0)); 1331 1332 // prepare DotDashArray iteration and the line/gap switching bool 1333 sal_uInt32 nDotDashIndex(0); 1334 bool bIsLine(true); 1335 double fDotDashMovingLength(rDotDashArray[0]); 1336 B2DPolygon aSnippet; 1337 1338 // iterate over all edges 1339 for(sal_uInt32 a(0); a < nEdgeCount; a++) 1340 { 1341 // update current edge (fill in C1, C2 and end point) 1342 double fLastDotDashMovingLength(0.0); 1343 const sal_uInt32 nNextIndex((a + 1) % nPointCount); 1344 aCurrentEdge.setControlPointA(rCandidate.getNextControlPoint(a)); 1345 aCurrentEdge.setControlPointB(rCandidate.getPrevControlPoint(nNextIndex)); 1346 aCurrentEdge.setEndPoint(rCandidate.getB2DPoint(nNextIndex)); 1347 1348 // check if we have a trivial bezier segment -> possible fallback to edge 1349 aCurrentEdge.testAndSolveTrivialBezier(); 1350 1351 if(aCurrentEdge.isBezier()) 1352 { 1353 // bezier segment 1354 const B2DCubicBezierHelper aCubicBezierHelper(aCurrentEdge); 1355 const double fEdgeLength(aCubicBezierHelper.getLength()); 1356 1357 if(!fTools::equalZero(fEdgeLength)) 1358 { 1359 while(fTools::less(fDotDashMovingLength, fEdgeLength)) 1360 { 1361 // new split is inside edge, create and append snippet [fLastDotDashMovingLength, fDotDashMovingLength] 1362 const bool bHandleLine(bIsLine && pLineTarget); 1363 const bool bHandleGap(!bIsLine && pGapTarget); 1364 1365 if(bHandleLine || bHandleGap) 1366 { 1367 const double fBezierSplitStart(aCubicBezierHelper.distanceToRelative(fLastDotDashMovingLength)); 1368 const double fBezierSplitEnd(aCubicBezierHelper.distanceToRelative(fDotDashMovingLength)); 1369 B2DCubicBezier aBezierSnippet(aCurrentEdge.snippet(fBezierSplitStart, fBezierSplitEnd)); 1370 1371 if(!aSnippet.count()) 1372 { 1373 aSnippet.append(aBezierSnippet.getStartPoint()); 1374 } 1375 1376 aSnippet.appendBezierSegment(aBezierSnippet.getControlPointA(), aBezierSnippet.getControlPointB(), aBezierSnippet.getEndPoint()); 1377 1378 if(bHandleLine) 1379 { 1380 pLineTarget->append(aSnippet); 1381 } 1382 else 1383 { 1384 pGapTarget->append(aSnippet); 1385 } 1386 1387 aSnippet.clear(); 1388 } 1389 1390 // prepare next DotDashArray step and flip line/gap flag 1391 fLastDotDashMovingLength = fDotDashMovingLength; 1392 fDotDashMovingLength += rDotDashArray[(++nDotDashIndex) % nDotDashCount]; 1393 bIsLine = !bIsLine; 1394 } 1395 1396 // append closing snippet [fLastDotDashMovingLength, fEdgeLength] 1397 const bool bHandleLine(bIsLine && pLineTarget); 1398 const bool bHandleGap(!bIsLine && pGapTarget); 1399 1400 if(bHandleLine || bHandleGap) 1401 { 1402 B2DCubicBezier aRight; 1403 const double fBezierSplit(aCubicBezierHelper.distanceToRelative(fLastDotDashMovingLength)); 1404 1405 aCurrentEdge.split(fBezierSplit, 0, &aRight); 1406 1407 if(!aSnippet.count()) 1408 { 1409 aSnippet.append(aRight.getStartPoint()); 1410 } 1411 1412 aSnippet.appendBezierSegment(aRight.getControlPointA(), aRight.getControlPointB(), aRight.getEndPoint()); 1413 } 1414 1415 // prepare move to next edge 1416 fDotDashMovingLength -= fEdgeLength; 1417 } 1418 } 1419 else 1420 { 1421 // simple edge 1422 const double fEdgeLength(aCurrentEdge.getEdgeLength()); 1423 1424 if(!fTools::equalZero(fEdgeLength)) 1425 { 1426 while(fTools::less(fDotDashMovingLength, fEdgeLength)) 1427 { 1428 // new split is inside edge, create and append snippet [fLastDotDashMovingLength, fDotDashMovingLength] 1429 const bool bHandleLine(bIsLine && pLineTarget); 1430 const bool bHandleGap(!bIsLine && pGapTarget); 1431 1432 if(bHandleLine || bHandleGap) 1433 { 1434 if(!aSnippet.count()) 1435 { 1436 aSnippet.append(interpolate(aCurrentEdge.getStartPoint(), aCurrentEdge.getEndPoint(), fLastDotDashMovingLength / fEdgeLength)); 1437 } 1438 1439 aSnippet.append(interpolate(aCurrentEdge.getStartPoint(), aCurrentEdge.getEndPoint(), fDotDashMovingLength / fEdgeLength)); 1440 1441 if(bHandleLine) 1442 { 1443 pLineTarget->append(aSnippet); 1444 } 1445 else 1446 { 1447 pGapTarget->append(aSnippet); 1448 } 1449 1450 aSnippet.clear(); 1451 } 1452 1453 // prepare next DotDashArray step and flip line/gap flag 1454 fLastDotDashMovingLength = fDotDashMovingLength; 1455 fDotDashMovingLength += rDotDashArray[(++nDotDashIndex) % nDotDashCount]; 1456 bIsLine = !bIsLine; 1457 } 1458 1459 // append snippet [fLastDotDashMovingLength, fEdgeLength] 1460 const bool bHandleLine(bIsLine && pLineTarget); 1461 const bool bHandleGap(!bIsLine && pGapTarget); 1462 1463 if(bHandleLine || bHandleGap) 1464 { 1465 if(!aSnippet.count()) 1466 { 1467 aSnippet.append(interpolate(aCurrentEdge.getStartPoint(), aCurrentEdge.getEndPoint(), fLastDotDashMovingLength / fEdgeLength)); 1468 } 1469 1470 aSnippet.append(aCurrentEdge.getEndPoint()); 1471 } 1472 1473 // prepare move to next edge 1474 fDotDashMovingLength -= fEdgeLength; 1475 } 1476 } 1477 1478 // prepare next edge step (end point gets new start point) 1479 aCurrentEdge.setStartPoint(aCurrentEdge.getEndPoint()); 1480 } 1481 1482 // append last intermediate results (if exists) 1483 if(aSnippet.count()) 1484 { 1485 if(bIsLine && pLineTarget) 1486 { 1487 pLineTarget->append(aSnippet); 1488 } 1489 else if(!bIsLine && pGapTarget) 1490 { 1491 pGapTarget->append(aSnippet); 1492 } 1493 } 1494 1495 // check if start and end polygon may be merged 1496 if(pLineTarget) 1497 { 1498 const sal_uInt32 nCount(pLineTarget->count()); 1499 1500 if(nCount > 1) 1501 { 1502 // these polygons were created above, there exists none with less than two points, 1503 // thus dircet point access below is allowed 1504 const B2DPolygon aFirst(pLineTarget->getB2DPolygon(0)); 1505 B2DPolygon aLast(pLineTarget->getB2DPolygon(nCount - 1)); 1506 1507 if(aFirst.getB2DPoint(0).equal(aLast.getB2DPoint(aLast.count() - 1))) 1508 { 1509 // start of first and end of last are the same -> merge them 1510 aLast.append(aFirst); 1511 aLast.removeDoublePoints(); 1512 pLineTarget->setB2DPolygon(0, aLast); 1513 pLineTarget->remove(nCount - 1); 1514 } 1515 } 1516 } 1517 1518 if(pGapTarget) 1519 { 1520 const sal_uInt32 nCount(pGapTarget->count()); 1521 1522 if(nCount > 1) 1523 { 1524 // these polygons were created above, there exists none with less than two points, 1525 // thus dircet point access below is allowed 1526 const B2DPolygon aFirst(pGapTarget->getB2DPolygon(0)); 1527 B2DPolygon aLast(pGapTarget->getB2DPolygon(nCount - 1)); 1528 1529 if(aFirst.getB2DPoint(0).equal(aLast.getB2DPoint(aLast.count() - 1))) 1530 { 1531 // start of first and end of last are the same -> merge them 1532 aLast.append(aFirst); 1533 aLast.removeDoublePoints(); 1534 pGapTarget->setB2DPolygon(0, aLast); 1535 pGapTarget->remove(nCount - 1); 1536 } 1537 } 1538 } 1539 } 1540 else 1541 { 1542 // parameters make no sense, just add source to targets 1543 if(pLineTarget) 1544 { 1545 pLineTarget->append(rCandidate); 1546 } 1547 1548 if(pGapTarget) 1549 { 1550 pGapTarget->append(rCandidate); 1551 } 1552 } 1553 } 1554 1555 // test if point is inside epsilon-range around an edge defined 1556 // by the two given points. Can be used for HitTesting. The epsilon-range 1557 // is defined to be the rectangle centered to the given edge, using height 1558 // 2 x fDistance, and the circle around both points with radius fDistance. 1559 bool isInEpsilonRange(const B2DPoint& rEdgeStart, const B2DPoint& rEdgeEnd, const B2DPoint& rTestPosition, double fDistance) 1560 { 1561 // build edge vector 1562 const B2DVector aEdge(rEdgeEnd - rEdgeStart); 1563 bool bDoDistanceTestStart(false); 1564 bool bDoDistanceTestEnd(false); 1565 1566 if(aEdge.equalZero()) 1567 { 1568 // no edge, just a point. Do one of the distance tests. 1569 bDoDistanceTestStart = true; 1570 } 1571 else 1572 { 1573 // edge has a length. Create perpendicular vector. 1574 const B2DVector aPerpend(getPerpendicular(aEdge)); 1575 double fCut( 1576 (aPerpend.getY() * (rTestPosition.getX() - rEdgeStart.getX()) 1577 + aPerpend.getX() * (rEdgeStart.getY() - rTestPosition.getY())) / 1578 (aEdge.getX() * aEdge.getX() + aEdge.getY() * aEdge.getY())); 1579 const double fZero(0.0); 1580 const double fOne(1.0); 1581 1582 if(fTools::less(fCut, fZero)) 1583 { 1584 // left of rEdgeStart 1585 bDoDistanceTestStart = true; 1586 } 1587 else if(fTools::more(fCut, fOne)) 1588 { 1589 // right of rEdgeEnd 1590 bDoDistanceTestEnd = true; 1591 } 1592 else 1593 { 1594 // inside line [0.0 .. 1.0] 1595 const B2DPoint aCutPoint(interpolate(rEdgeStart, rEdgeEnd, fCut)); 1596 const B2DVector aDelta(rTestPosition - aCutPoint); 1597 const double fDistanceSquare(aDelta.scalar(aDelta)); 1598 1599 if(fDistanceSquare <= fDistance * fDistance) 1600 { 1601 return true; 1602 } 1603 else 1604 { 1605 return false; 1606 } 1607 } 1608 } 1609 1610 if(bDoDistanceTestStart) 1611 { 1612 const B2DVector aDelta(rTestPosition - rEdgeStart); 1613 const double fDistanceSquare(aDelta.scalar(aDelta)); 1614 1615 if(fDistanceSquare <= fDistance * fDistance) 1616 { 1617 return true; 1618 } 1619 } 1620 else if(bDoDistanceTestEnd) 1621 { 1622 const B2DVector aDelta(rTestPosition - rEdgeEnd); 1623 const double fDistanceSquare(aDelta.scalar(aDelta)); 1624 1625 if(fDistanceSquare <= fDistance * fDistance) 1626 { 1627 return true; 1628 } 1629 } 1630 1631 return false; 1632 } 1633 1634 // test if point is inside epsilon-range around the given Polygon. Can be used 1635 // for HitTesting. The epsilon-range is defined to be the tube around the polygon 1636 // with distance fDistance and rounded edges (start and end point). 1637 bool isInEpsilonRange(const B2DPolygon& rCandidate, const B2DPoint& rTestPosition, double fDistance) 1638 { 1639 // force to non-bezier polygon 1640 const B2DPolygon aCandidate(rCandidate.getDefaultAdaptiveSubdivision()); 1641 const sal_uInt32 nPointCount(aCandidate.count()); 1642 1643 if(nPointCount) 1644 { 1645 const sal_uInt32 nEdgeCount(aCandidate.isClosed() ? nPointCount : nPointCount - 1L); 1646 B2DPoint aCurrent(aCandidate.getB2DPoint(0)); 1647 1648 if(nEdgeCount) 1649 { 1650 // edges 1651 for(sal_uInt32 a(0); a < nEdgeCount; a++) 1652 { 1653 const sal_uInt32 nNextIndex((a + 1) % nPointCount); 1654 const B2DPoint aNext(aCandidate.getB2DPoint(nNextIndex)); 1655 1656 if(isInEpsilonRange(aCurrent, aNext, rTestPosition, fDistance)) 1657 { 1658 return true; 1659 } 1660 1661 // prepare next step 1662 aCurrent = aNext; 1663 } 1664 } 1665 else 1666 { 1667 // no edges, but points -> not closed. Check single point. Just 1668 // use isInEpsilonRange with twice the same point, it handles those well 1669 if(isInEpsilonRange(aCurrent, aCurrent, rTestPosition, fDistance)) 1670 { 1671 return true; 1672 } 1673 } 1674 } 1675 1676 return false; 1677 } 1678 1679 B2DPolygon createPolygonFromRect( const B2DRectangle& rRect, double fRadius ) 1680 { 1681 const double fZero(0.0); 1682 const double fOne(1.0); 1683 1684 if(fTools::lessOrEqual(fRadius, fZero)) 1685 { 1686 // no radius, use rectangle 1687 return createPolygonFromRect( rRect ); 1688 } 1689 else if(fTools::moreOrEqual(fRadius, fOne)) 1690 { 1691 // full radius, use ellipse 1692 const B2DPoint aCenter(rRect.getCenter()); 1693 const double fRadiusX(rRect.getWidth() / 2.0); 1694 const double fRadiusY(rRect.getHeight() / 2.0); 1695 1696 return createPolygonFromEllipse( aCenter, fRadiusX, fRadiusY ); 1697 } 1698 else 1699 { 1700 // create rectangle with two radii between ]0.0 .. 1.0[ 1701 return createPolygonFromRect( rRect, fRadius, fRadius ); 1702 } 1703 } 1704 1705 B2DPolygon createPolygonFromRect( const B2DRectangle& rRect, double fRadiusX, double fRadiusY ) 1706 { 1707 const double fZero(0.0); 1708 const double fOne(1.0); 1709 1710 // crop to useful values 1711 if(fTools::less(fRadiusX, fZero)) 1712 { 1713 fRadiusX = fZero; 1714 } 1715 else if(fTools::more(fRadiusX, fOne)) 1716 { 1717 fRadiusX = fOne; 1718 } 1719 1720 if(fTools::less(fRadiusY, fZero)) 1721 { 1722 fRadiusY = fZero; 1723 } 1724 else if(fTools::more(fRadiusY, fOne)) 1725 { 1726 fRadiusY = fOne; 1727 } 1728 1729 if(fZero == fRadiusX || fZero == fRadiusY) 1730 { 1731 B2DPolygon aRetval; 1732 1733 // at least in one direction no radius, use rectangle. 1734 // Do not use createPolygonFromRect() here since original 1735 // creator (historical reasons) still creates a start point at the 1736 // bottom center, so do the same here to get the same line patterns. 1737 // Due to this the order of points is different, too. 1738 const B2DPoint aBottomCenter(rRect.getCenter().getX(), rRect.getMaxY()); 1739 aRetval.append(aBottomCenter); 1740 1741 aRetval.append( B2DPoint( rRect.getMinX(), rRect.getMaxY() ) ); 1742 aRetval.append( B2DPoint( rRect.getMinX(), rRect.getMinY() ) ); 1743 aRetval.append( B2DPoint( rRect.getMaxX(), rRect.getMinY() ) ); 1744 aRetval.append( B2DPoint( rRect.getMaxX(), rRect.getMaxY() ) ); 1745 1746 // close 1747 aRetval.setClosed( true ); 1748 1749 return aRetval; 1750 } 1751 else if(fOne == fRadiusX && fOne == fRadiusY) 1752 { 1753 // in both directions full radius, use ellipse 1754 const B2DPoint aCenter(rRect.getCenter()); 1755 const double fRectRadiusX(rRect.getWidth() / 2.0); 1756 const double fRectRadiusY(rRect.getHeight() / 2.0); 1757 1758 return createPolygonFromEllipse( aCenter, fRectRadiusX, fRectRadiusY ); 1759 } 1760 else 1761 { 1762 B2DPolygon aRetval; 1763 const double fBowX((rRect.getWidth() / 2.0) * fRadiusX); 1764 const double fBowY((rRect.getHeight() / 2.0) * fRadiusY); 1765 const double fKappa((M_SQRT2 - 1.0) * 4.0 / 3.0); 1766 1767 // create start point at bottom center 1768 if(fOne != fRadiusX) 1769 { 1770 const B2DPoint aBottomCenter(rRect.getCenter().getX(), rRect.getMaxY()); 1771 aRetval.append(aBottomCenter); 1772 } 1773 1774 // create first bow 1775 { 1776 const B2DPoint aBottomRight(rRect.getMaxX(), rRect.getMaxY()); 1777 const B2DPoint aStart(aBottomRight + B2DPoint(-fBowX, 0.0)); 1778 const B2DPoint aStop(aBottomRight + B2DPoint(0.0, -fBowY)); 1779 aRetval.append(aStart); 1780 aRetval.appendBezierSegment(interpolate(aStart, aBottomRight, fKappa), interpolate(aStop, aBottomRight, fKappa), aStop); 1781 } 1782 1783 // create second bow 1784 { 1785 const B2DPoint aTopRight(rRect.getMaxX(), rRect.getMinY()); 1786 const B2DPoint aStart(aTopRight + B2DPoint(0.0, fBowY)); 1787 const B2DPoint aStop(aTopRight + B2DPoint(-fBowX, 0.0)); 1788 aRetval.append(aStart); 1789 aRetval.appendBezierSegment(interpolate(aStart, aTopRight, fKappa), interpolate(aStop, aTopRight, fKappa), aStop); 1790 } 1791 1792 // create third bow 1793 { 1794 const B2DPoint aTopLeft(rRect.getMinX(), rRect.getMinY()); 1795 const B2DPoint aStart(aTopLeft + B2DPoint(fBowX, 0.0)); 1796 const B2DPoint aStop(aTopLeft + B2DPoint(0.0, fBowY)); 1797 aRetval.append(aStart); 1798 aRetval.appendBezierSegment(interpolate(aStart, aTopLeft, fKappa), interpolate(aStop, aTopLeft, fKappa), aStop); 1799 } 1800 1801 // create forth bow 1802 { 1803 const B2DPoint aBottomLeft(rRect.getMinX(), rRect.getMaxY()); 1804 const B2DPoint aStart(aBottomLeft + B2DPoint(0.0, -fBowY)); 1805 const B2DPoint aStop(aBottomLeft + B2DPoint(fBowX, 0.0)); 1806 aRetval.append(aStart); 1807 aRetval.appendBezierSegment(interpolate(aStart, aBottomLeft, fKappa), interpolate(aStop, aBottomLeft, fKappa), aStop); 1808 } 1809 1810 // close 1811 aRetval.setClosed( true ); 1812 1813 // remove double created points if there are extreme radii envolved 1814 if(fOne == fRadiusX || fOne == fRadiusY) 1815 { 1816 aRetval.removeDoublePoints(); 1817 } 1818 1819 return aRetval; 1820 } 1821 } 1822 1823 B2DPolygon createPolygonFromRect( const B2DRectangle& rRect ) 1824 { 1825 B2DPolygon aRetval; 1826 1827 aRetval.append( B2DPoint( rRect.getMinX(), rRect.getMinY() ) ); 1828 aRetval.append( B2DPoint( rRect.getMaxX(), rRect.getMinY() ) ); 1829 aRetval.append( B2DPoint( rRect.getMaxX(), rRect.getMaxY() ) ); 1830 aRetval.append( B2DPoint( rRect.getMinX(), rRect.getMaxY() ) ); 1831 1832 // close 1833 aRetval.setClosed( true ); 1834 1835 return aRetval; 1836 } 1837 1838 B2DPolygon createUnitPolygon() 1839 { 1840 static B2DPolygon aRetval; 1841 1842 if(!aRetval.count()) 1843 { 1844 aRetval.append( B2DPoint( 0.0, 0.0 ) ); 1845 aRetval.append( B2DPoint( 1.0, 0.0 ) ); 1846 aRetval.append( B2DPoint( 1.0, 1.0 ) ); 1847 aRetval.append( B2DPoint( 0.0, 1.0 ) ); 1848 1849 // close 1850 aRetval.setClosed( true ); 1851 } 1852 1853 return aRetval; 1854 } 1855 1856 B2DPolygon createPolygonFromCircle( const B2DPoint& rCenter, double fRadius ) 1857 { 1858 return createPolygonFromEllipse( rCenter, fRadius, fRadius ); 1859 } 1860 1861 B2DPolygon impCreateUnitCircle(sal_uInt32 nStartQuadrant) 1862 { 1863 B2DPolygon aUnitCircle; 1864 const double fKappa((M_SQRT2 - 1.0) * 4.0 / 3.0); 1865 const double fScaledKappa(fKappa * (1.0 / STEPSPERQUARTER)); 1866 const B2DHomMatrix aRotateMatrix(createRotateB2DHomMatrix(F_PI2 / STEPSPERQUARTER)); 1867 1868 B2DPoint aPoint(1.0, 0.0); 1869 B2DPoint aForward(1.0, fScaledKappa); 1870 B2DPoint aBackward(1.0, -fScaledKappa); 1871 1872 if(0 != nStartQuadrant) 1873 { 1874 const B2DHomMatrix aQuadrantMatrix(createRotateB2DHomMatrix(F_PI2 * (nStartQuadrant % 4))); 1875 aPoint *= aQuadrantMatrix; 1876 aBackward *= aQuadrantMatrix; 1877 aForward *= aQuadrantMatrix; 1878 } 1879 1880 aUnitCircle.append(aPoint); 1881 1882 for(sal_uInt32 a(0); a < STEPSPERQUARTER * 4; a++) 1883 { 1884 aPoint *= aRotateMatrix; 1885 aBackward *= aRotateMatrix; 1886 aUnitCircle.appendBezierSegment(aForward, aBackward, aPoint); 1887 aForward *= aRotateMatrix; 1888 } 1889 1890 aUnitCircle.setClosed(true); 1891 aUnitCircle.removeDoublePoints(); 1892 1893 return aUnitCircle; 1894 } 1895 1896 B2DPolygon createPolygonFromUnitCircle(sal_uInt32 nStartQuadrant) 1897 { 1898 switch(nStartQuadrant % 4) 1899 { 1900 case 1 : 1901 { 1902 static B2DPolygon aUnitCircleStartQuadrantOne; 1903 1904 if(!aUnitCircleStartQuadrantOne.count()) 1905 { 1906 ::osl::Mutex m_mutex; 1907 aUnitCircleStartQuadrantOne = impCreateUnitCircle(1); 1908 } 1909 1910 return aUnitCircleStartQuadrantOne; 1911 } 1912 case 2 : 1913 { 1914 static B2DPolygon aUnitCircleStartQuadrantTwo; 1915 1916 if(!aUnitCircleStartQuadrantTwo.count()) 1917 { 1918 ::osl::Mutex m_mutex; 1919 aUnitCircleStartQuadrantTwo = impCreateUnitCircle(2); 1920 } 1921 1922 return aUnitCircleStartQuadrantTwo; 1923 } 1924 case 3 : 1925 { 1926 static B2DPolygon aUnitCircleStartQuadrantThree; 1927 1928 if(!aUnitCircleStartQuadrantThree.count()) 1929 { 1930 ::osl::Mutex m_mutex; 1931 aUnitCircleStartQuadrantThree = impCreateUnitCircle(3); 1932 } 1933 1934 return aUnitCircleStartQuadrantThree; 1935 } 1936 default : // case 0 : 1937 { 1938 static B2DPolygon aUnitCircleStartQuadrantZero; 1939 1940 if(!aUnitCircleStartQuadrantZero.count()) 1941 { 1942 ::osl::Mutex m_mutex; 1943 aUnitCircleStartQuadrantZero = impCreateUnitCircle(0); 1944 } 1945 1946 return aUnitCircleStartQuadrantZero; 1947 } 1948 } 1949 } 1950 1951 B2DPolygon createPolygonFromEllipse( const B2DPoint& rCenter, double fRadiusX, double fRadiusY ) 1952 { 1953 B2DPolygon aRetval(createPolygonFromUnitCircle()); 1954 const B2DHomMatrix aMatrix(createScaleTranslateB2DHomMatrix(fRadiusX, fRadiusY, rCenter.getX(), rCenter.getY())); 1955 1956 aRetval.transform(aMatrix); 1957 1958 return aRetval; 1959 } 1960 1961 B2DPolygon createPolygonFromUnitEllipseSegment( double fStart, double fEnd ) 1962 { 1963 B2DPolygon aRetval; 1964 1965 // truncate fStart, fEnd to a range of [0.0 .. F_2PI[ where F_2PI 1966 // falls back to 0.0 to ensure a unique definition 1967 if(fTools::less(fStart, 0.0)) 1968 { 1969 fStart = 0.0; 1970 } 1971 1972 if(fTools::moreOrEqual(fStart, F_2PI)) 1973 { 1974 fStart = 0.0; 1975 } 1976 1977 if(fTools::less(fEnd, 0.0)) 1978 { 1979 fEnd = 0.0; 1980 } 1981 1982 if(fTools::moreOrEqual(fEnd, F_2PI)) 1983 { 1984 fEnd = 0.0; 1985 } 1986 1987 if(fTools::equal(fStart, fEnd)) 1988 { 1989 // same start and end angle, add single point 1990 aRetval.append(B2DPoint(cos(fStart), sin(fStart))); 1991 } 1992 else 1993 { 1994 const sal_uInt32 nSegments(STEPSPERQUARTER * 4); 1995 const double fAnglePerSegment(F_PI2 / STEPSPERQUARTER); 1996 const sal_uInt32 nStartSegment(sal_uInt32(fStart / fAnglePerSegment) % nSegments); 1997 const sal_uInt32 nEndSegment(sal_uInt32(fEnd / fAnglePerSegment) % nSegments); 1998 const double fKappa((M_SQRT2 - 1.0) * 4.0 / 3.0); 1999 const double fScaledKappa(fKappa * (1.0 / STEPSPERQUARTER)); 2000 2001 B2DPoint aSegStart(cos(fStart), sin(fStart)); 2002 aRetval.append(aSegStart); 2003 2004 if(nStartSegment == nEndSegment && fTools::more(fEnd, fStart)) 2005 { 2006 // start and end in one sector and in the right order, create in one segment 2007 const B2DPoint aSegEnd(cos(fEnd), sin(fEnd)); 2008 const double fFactor(fScaledKappa * ((fEnd - fStart) / fAnglePerSegment)); 2009 2010 aRetval.appendBezierSegment( 2011 aSegStart + (B2DPoint(-aSegStart.getY(), aSegStart.getX()) * fFactor), 2012 aSegEnd - (B2DPoint(-aSegEnd.getY(), aSegEnd.getX()) * fFactor), 2013 aSegEnd); 2014 } 2015 else 2016 { 2017 double fSegEndRad((nStartSegment + 1) * fAnglePerSegment); 2018 double fFactor(fScaledKappa * ((fSegEndRad - fStart) / fAnglePerSegment)); 2019 B2DPoint aSegEnd(cos(fSegEndRad), sin(fSegEndRad)); 2020 2021 aRetval.appendBezierSegment( 2022 aSegStart + (B2DPoint(-aSegStart.getY(), aSegStart.getX()) * fFactor), 2023 aSegEnd - (B2DPoint(-aSegEnd.getY(), aSegEnd.getX()) * fFactor), 2024 aSegEnd); 2025 2026 sal_uInt32 nSegment((nStartSegment + 1) % nSegments); 2027 aSegStart = aSegEnd; 2028 2029 while(nSegment != nEndSegment) 2030 { 2031 // No end in this sector, add full sector. 2032 fSegEndRad = (nSegment + 1) * fAnglePerSegment; 2033 aSegEnd = B2DPoint(cos(fSegEndRad), sin(fSegEndRad)); 2034 2035 aRetval.appendBezierSegment( 2036 aSegStart + (B2DPoint(-aSegStart.getY(), aSegStart.getX()) * fScaledKappa), 2037 aSegEnd - (B2DPoint(-aSegEnd.getY(), aSegEnd.getX()) * fScaledKappa), 2038 aSegEnd); 2039 2040 nSegment = (nSegment + 1) % nSegments; 2041 aSegStart = aSegEnd; 2042 } 2043 2044 // End in this sector 2045 const double fSegStartRad(nSegment * fAnglePerSegment); 2046 fFactor = fScaledKappa * ((fEnd - fSegStartRad) / fAnglePerSegment); 2047 aSegEnd = B2DPoint(cos(fEnd), sin(fEnd)); 2048 2049 aRetval.appendBezierSegment( 2050 aSegStart + (B2DPoint(-aSegStart.getY(), aSegStart.getX()) * fFactor), 2051 aSegEnd - (B2DPoint(-aSegEnd.getY(), aSegEnd.getX()) * fFactor), 2052 aSegEnd); 2053 } 2054 } 2055 2056 // remove double points between segments created by segmented creation 2057 aRetval.removeDoublePoints(); 2058 2059 return aRetval; 2060 } 2061 2062 B2DPolygon createPolygonFromEllipseSegment( const B2DPoint& rCenter, double fRadiusX, double fRadiusY, double fStart, double fEnd ) 2063 { 2064 B2DPolygon aRetval(createPolygonFromUnitEllipseSegment(fStart, fEnd)); 2065 const B2DHomMatrix aMatrix(createScaleTranslateB2DHomMatrix(fRadiusX, fRadiusY, rCenter.getX(), rCenter.getY())); 2066 2067 aRetval.transform(aMatrix); 2068 2069 return aRetval; 2070 } 2071 2072 bool hasNeutralPoints(const B2DPolygon& rCandidate) 2073 { 2074 OSL_ENSURE(!rCandidate.areControlPointsUsed(), "hasNeutralPoints: ATM works not for curves (!)"); 2075 const sal_uInt32 nPointCount(rCandidate.count()); 2076 2077 if(nPointCount > 2L) 2078 { 2079 B2DPoint aPrevPoint(rCandidate.getB2DPoint(nPointCount - 1L)); 2080 B2DPoint aCurrPoint(rCandidate.getB2DPoint(0L)); 2081 2082 for(sal_uInt32 a(0L); a < nPointCount; a++) 2083 { 2084 const B2DPoint aNextPoint(rCandidate.getB2DPoint((a + 1) % nPointCount)); 2085 const B2DVector aPrevVec(aPrevPoint - aCurrPoint); 2086 const B2DVector aNextVec(aNextPoint - aCurrPoint); 2087 const B2VectorOrientation aOrientation(getOrientation(aNextVec, aPrevVec)); 2088 2089 if(ORIENTATION_NEUTRAL == aOrientation) 2090 { 2091 // current has neutral orientation 2092 return true; 2093 } 2094 else 2095 { 2096 // prepare next 2097 aPrevPoint = aCurrPoint; 2098 aCurrPoint = aNextPoint; 2099 } 2100 } 2101 } 2102 2103 return false; 2104 } 2105 2106 B2DPolygon removeNeutralPoints(const B2DPolygon& rCandidate) 2107 { 2108 if(hasNeutralPoints(rCandidate)) 2109 { 2110 const sal_uInt32 nPointCount(rCandidate.count()); 2111 B2DPolygon aRetval; 2112 B2DPoint aPrevPoint(rCandidate.getB2DPoint(nPointCount - 1L)); 2113 B2DPoint aCurrPoint(rCandidate.getB2DPoint(0L)); 2114 2115 for(sal_uInt32 a(0L); a < nPointCount; a++) 2116 { 2117 const B2DPoint aNextPoint(rCandidate.getB2DPoint((a + 1) % nPointCount)); 2118 const B2DVector aPrevVec(aPrevPoint - aCurrPoint); 2119 const B2DVector aNextVec(aNextPoint - aCurrPoint); 2120 const B2VectorOrientation aOrientation(getOrientation(aNextVec, aPrevVec)); 2121 2122 if(ORIENTATION_NEUTRAL == aOrientation) 2123 { 2124 // current has neutral orientation, leave it out and prepare next 2125 aCurrPoint = aNextPoint; 2126 } 2127 else 2128 { 2129 // add current point 2130 aRetval.append(aCurrPoint); 2131 2132 // prepare next 2133 aPrevPoint = aCurrPoint; 2134 aCurrPoint = aNextPoint; 2135 } 2136 } 2137 2138 while(aRetval.count() && ORIENTATION_NEUTRAL == getOrientationForIndex(aRetval, 0L)) 2139 { 2140 aRetval.remove(0L); 2141 } 2142 2143 // copy closed state 2144 aRetval.setClosed(rCandidate.isClosed()); 2145 2146 return aRetval; 2147 } 2148 else 2149 { 2150 return rCandidate; 2151 } 2152 } 2153 2154 bool isConvex(const B2DPolygon& rCandidate) 2155 { 2156 OSL_ENSURE(!rCandidate.areControlPointsUsed(), "isConvex: ATM works not for curves (!)"); 2157 const sal_uInt32 nPointCount(rCandidate.count()); 2158 2159 if(nPointCount > 2L) 2160 { 2161 const B2DPoint aPrevPoint(rCandidate.getB2DPoint(nPointCount - 1L)); 2162 B2DPoint aCurrPoint(rCandidate.getB2DPoint(0L)); 2163 B2DVector aCurrVec(aPrevPoint - aCurrPoint); 2164 B2VectorOrientation aOrientation(ORIENTATION_NEUTRAL); 2165 2166 for(sal_uInt32 a(0L); a < nPointCount; a++) 2167 { 2168 const B2DPoint aNextPoint(rCandidate.getB2DPoint((a + 1) % nPointCount)); 2169 const B2DVector aNextVec(aNextPoint - aCurrPoint); 2170 const B2VectorOrientation aCurrentOrientation(getOrientation(aNextVec, aCurrVec)); 2171 2172 if(ORIENTATION_NEUTRAL == aOrientation) 2173 { 2174 // set start value, maybe neutral again 2175 aOrientation = aCurrentOrientation; 2176 } 2177 else 2178 { 2179 if(ORIENTATION_NEUTRAL != aCurrentOrientation && aCurrentOrientation != aOrientation) 2180 { 2181 // different orientations found, that's it 2182 return false; 2183 } 2184 } 2185 2186 // prepare next 2187 aCurrPoint = aNextPoint; 2188 aCurrVec = -aNextVec; 2189 } 2190 } 2191 2192 return true; 2193 } 2194 2195 B2VectorOrientation getOrientationForIndex(const B2DPolygon& rCandidate, sal_uInt32 nIndex) 2196 { 2197 OSL_ENSURE(nIndex < rCandidate.count(), "getOrientationForIndex: index out of range (!)"); 2198 const B2DPoint aPrev(rCandidate.getB2DPoint(getIndexOfPredecessor(nIndex, rCandidate))); 2199 const B2DPoint aCurr(rCandidate.getB2DPoint(nIndex)); 2200 const B2DPoint aNext(rCandidate.getB2DPoint(getIndexOfSuccessor(nIndex, rCandidate))); 2201 const B2DVector aBack(aPrev - aCurr); 2202 const B2DVector aForw(aNext - aCurr); 2203 2204 return getOrientation(aForw, aBack); 2205 } 2206 2207 bool isPointOnLine(const B2DPoint& rStart, const B2DPoint& rEnd, const B2DPoint& rCandidate, bool bWithPoints) 2208 { 2209 if(rCandidate.equal(rStart) || rCandidate.equal(rEnd)) 2210 { 2211 // candidate is in epsilon around start or end -> inside 2212 return bWithPoints; 2213 } 2214 else if(rStart.equal(rEnd)) 2215 { 2216 // start and end are equal, but candidate is outside their epsilon -> outside 2217 return false; 2218 } 2219 else 2220 { 2221 const B2DVector aEdgeVector(rEnd - rStart); 2222 const B2DVector aTestVector(rCandidate - rStart); 2223 2224 if(areParallel(aEdgeVector, aTestVector)) 2225 { 2226 const double fZero(0.0); 2227 const double fOne(1.0); 2228 const double fParamTestOnCurr(fabs(aEdgeVector.getX()) > fabs(aEdgeVector.getY()) 2229 ? aTestVector.getX() / aEdgeVector.getX() 2230 : aTestVector.getY() / aEdgeVector.getY()); 2231 2232 if(fTools::more(fParamTestOnCurr, fZero) && fTools::less(fParamTestOnCurr, fOne)) 2233 { 2234 return true; 2235 } 2236 } 2237 2238 return false; 2239 } 2240 } 2241 2242 bool isPointOnPolygon(const B2DPolygon& rCandidate, const B2DPoint& rPoint, bool bWithPoints) 2243 { 2244 const B2DPolygon aCandidate(rCandidate.areControlPointsUsed() ? rCandidate.getDefaultAdaptiveSubdivision() : rCandidate); 2245 const sal_uInt32 nPointCount(aCandidate.count()); 2246 2247 if(nPointCount > 1L) 2248 { 2249 const sal_uInt32 nLoopCount(aCandidate.isClosed() ? nPointCount : nPointCount - 1L); 2250 B2DPoint aCurrentPoint(aCandidate.getB2DPoint(0L)); 2251 2252 for(sal_uInt32 a(0L); a < nLoopCount; a++) 2253 { 2254 const B2DPoint aNextPoint(aCandidate.getB2DPoint((a + 1L) % nPointCount)); 2255 2256 if(isPointOnLine(aCurrentPoint, aNextPoint, rPoint, bWithPoints)) 2257 { 2258 return true; 2259 } 2260 2261 aCurrentPoint = aNextPoint; 2262 } 2263 } 2264 else if(nPointCount && bWithPoints) 2265 { 2266 return rPoint.equal(aCandidate.getB2DPoint(0L)); 2267 } 2268 2269 return false; 2270 } 2271 2272 bool isPointInTriangle(const B2DPoint& rA, const B2DPoint& rB, const B2DPoint& rC, const B2DPoint& rCandidate, bool bWithBorder) 2273 { 2274 if(arePointsOnSameSideOfLine(rA, rB, rC, rCandidate, bWithBorder)) 2275 { 2276 if(arePointsOnSameSideOfLine(rB, rC, rA, rCandidate, bWithBorder)) 2277 { 2278 if(arePointsOnSameSideOfLine(rC, rA, rB, rCandidate, bWithBorder)) 2279 { 2280 return true; 2281 } 2282 } 2283 } 2284 2285 return false; 2286 } 2287 2288 bool arePointsOnSameSideOfLine(const B2DPoint& rStart, const B2DPoint& rEnd, const B2DPoint& rCandidateA, const B2DPoint& rCandidateB, bool bWithLine) 2289 { 2290 const B2DVector aLineVector(rEnd - rStart); 2291 const B2DVector aVectorToA(rEnd - rCandidateA); 2292 const double fCrossA(aLineVector.cross(aVectorToA)); 2293 2294 if(fTools::equalZero(fCrossA)) 2295 { 2296 // one point on the line 2297 return bWithLine; 2298 } 2299 2300 const B2DVector aVectorToB(rEnd - rCandidateB); 2301 const double fCrossB(aLineVector.cross(aVectorToB)); 2302 2303 if(fTools::equalZero(fCrossB)) 2304 { 2305 // one point on the line 2306 return bWithLine; 2307 } 2308 2309 // return true if they both have the same sign 2310 return ((fCrossA > 0.0) == (fCrossB > 0.0)); 2311 } 2312 2313 void addTriangleFan(const B2DPolygon& rCandidate, B2DPolygon& rTarget) 2314 { 2315 const sal_uInt32 nCount(rCandidate.count()); 2316 2317 if(nCount > 2L) 2318 { 2319 const B2DPoint aStart(rCandidate.getB2DPoint(0L)); 2320 B2DPoint aLast(rCandidate.getB2DPoint(1L)); 2321 2322 for(sal_uInt32 a(2L); a < nCount; a++) 2323 { 2324 const B2DPoint aCurrent(rCandidate.getB2DPoint(a)); 2325 rTarget.append(aStart); 2326 rTarget.append(aLast); 2327 rTarget.append(aCurrent); 2328 2329 // prepare next 2330 aLast = aCurrent; 2331 } 2332 } 2333 } 2334 2335 namespace 2336 { 2337 /// return 0 for input of 0, -1 for negative and 1 for positive input 2338 inline int lcl_sgn( const double n ) 2339 { 2340 return n == 0.0 ? 0 : 1 - 2*::rtl::math::isSignBitSet(n); 2341 } 2342 } 2343 2344 bool isRectangle( const B2DPolygon& rPoly ) 2345 { 2346 // polygon must be closed to resemble a rect, and contain 2347 // at least four points. 2348 if( !rPoly.isClosed() || 2349 rPoly.count() < 4 || 2350 rPoly.areControlPointsUsed() ) 2351 { 2352 return false; 2353 } 2354 2355 // number of 90 degree turns the polygon has taken 2356 int nNumTurns(0); 2357 2358 int nVerticalEdgeType=0; 2359 int nHorizontalEdgeType=0; 2360 bool bNullVertex(true); 2361 bool bCWPolygon(false); // when true, polygon is CW 2362 // oriented, when false, CCW 2363 bool bOrientationSet(false); // when false, polygon 2364 // orientation has not yet 2365 // been determined. 2366 2367 // scan all _edges_ (which involves coming back to point 0 2368 // for the last edge - thus the modulo operation below) 2369 const sal_Int32 nCount( rPoly.count() ); 2370 for( sal_Int32 i=0; i<nCount; ++i ) 2371 { 2372 const B2DPoint& rPoint0( rPoly.getB2DPoint(i % nCount) ); 2373 const B2DPoint& rPoint1( rPoly.getB2DPoint((i+1) % nCount) ); 2374 2375 // is 0 for zero direction vector, 1 for south edge and -1 2376 // for north edge (standard screen coordinate system) 2377 int nCurrVerticalEdgeType( lcl_sgn( rPoint1.getY() - rPoint0.getY() ) ); 2378 2379 // is 0 for zero direction vector, 1 for east edge and -1 2380 // for west edge (standard screen coordinate system) 2381 int nCurrHorizontalEdgeType( lcl_sgn(rPoint1.getX() - rPoint0.getX()) ); 2382 2383 if( nCurrVerticalEdgeType && nCurrHorizontalEdgeType ) 2384 return false; // oblique edge - for sure no rect 2385 2386 const bool bCurrNullVertex( !nCurrVerticalEdgeType && !nCurrHorizontalEdgeType ); 2387 2388 // current vertex is equal to previous - just skip, 2389 // until we have a real edge 2390 if( bCurrNullVertex ) 2391 continue; 2392 2393 // if previous edge has two identical points, because 2394 // no previous edge direction was available, simply 2395 // take this first non-null edge as the start 2396 // direction. That's what will happen here, if 2397 // bNullVertex is false 2398 if( !bNullVertex ) 2399 { 2400 // 2D cross product - is 1 for CW and -1 for CCW turns 2401 const int nCrossProduct( nHorizontalEdgeType*nCurrVerticalEdgeType - 2402 nVerticalEdgeType*nCurrHorizontalEdgeType ); 2403 2404 if( !nCrossProduct ) 2405 continue; // no change in orientation - 2406 // collinear edges - just go on 2407 2408 // if polygon orientation is not set, we'll 2409 // determine it now 2410 if( !bOrientationSet ) 2411 { 2412 bCWPolygon = nCrossProduct == 1; 2413 bOrientationSet = true; 2414 } 2415 else 2416 { 2417 // if current turn orientation is not equal 2418 // initial orientation, this is not a 2419 // rectangle (as rectangles have consistent 2420 // orientation). 2421 if( (nCrossProduct == 1) != bCWPolygon ) 2422 return false; 2423 } 2424 2425 ++nNumTurns; 2426 2427 // More than four 90 degree turns are an 2428 // indication that this must not be a rectangle. 2429 if( nNumTurns > 4 ) 2430 return false; 2431 } 2432 2433 // store current state for the next turn 2434 nVerticalEdgeType = nCurrVerticalEdgeType; 2435 nHorizontalEdgeType = nCurrHorizontalEdgeType; 2436 bNullVertex = false; // won't reach this line, 2437 // if bCurrNullVertex is 2438 // true - see above 2439 } 2440 2441 return true; 2442 } 2443 2444 B3DPolygon createB3DPolygonFromB2DPolygon(const B2DPolygon& rCandidate, double fZCoordinate) 2445 { 2446 if(rCandidate.areControlPointsUsed()) 2447 { 2448 // call myself recursively with subdivided input 2449 const B2DPolygon aCandidate(adaptiveSubdivideByAngle(rCandidate)); 2450 return createB3DPolygonFromB2DPolygon(aCandidate, fZCoordinate); 2451 } 2452 else 2453 { 2454 B3DPolygon aRetval; 2455 2456 for(sal_uInt32 a(0L); a < rCandidate.count(); a++) 2457 { 2458 B2DPoint aPoint(rCandidate.getB2DPoint(a)); 2459 aRetval.append(B3DPoint(aPoint.getX(), aPoint.getY(), fZCoordinate)); 2460 } 2461 2462 // copy closed state 2463 aRetval.setClosed(rCandidate.isClosed()); 2464 2465 return aRetval; 2466 } 2467 } 2468 2469 B2DPolygon createB2DPolygonFromB3DPolygon(const B3DPolygon& rCandidate, const B3DHomMatrix& rMat) 2470 { 2471 B2DPolygon aRetval; 2472 const sal_uInt32 nCount(rCandidate.count()); 2473 const bool bIsIdentity(rMat.isIdentity()); 2474 2475 for(sal_uInt32 a(0L); a < nCount; a++) 2476 { 2477 B3DPoint aCandidate(rCandidate.getB3DPoint(a)); 2478 2479 if(!bIsIdentity) 2480 { 2481 aCandidate *= rMat; 2482 } 2483 2484 aRetval.append(B2DPoint(aCandidate.getX(), aCandidate.getY())); 2485 } 2486 2487 // copy closed state 2488 aRetval.setClosed(rCandidate.isClosed()); 2489 2490 return aRetval; 2491 } 2492 2493 double getDistancePointToEndlessRay(const B2DPoint& rPointA, const B2DPoint& rPointB, const B2DPoint& rTestPoint, double& rCut) 2494 { 2495 if(rPointA.equal(rPointB)) 2496 { 2497 rCut = 0.0; 2498 const B2DVector aVector(rTestPoint - rPointA); 2499 return aVector.getLength(); 2500 } 2501 else 2502 { 2503 // get the relative cut value on line vector (Vector1) for cut with perpendicular through TestPoint 2504 const B2DVector aVector1(rPointB - rPointA); 2505 const B2DVector aVector2(rTestPoint - rPointA); 2506 const double fDividend((aVector2.getX() * aVector1.getX()) + (aVector2.getY() * aVector1.getY())); 2507 const double fDivisor((aVector1.getX() * aVector1.getX()) + (aVector1.getY() * aVector1.getY())); 2508 2509 rCut = fDividend / fDivisor; 2510 2511 const B2DPoint aCutPoint(rPointA + rCut * aVector1); 2512 const B2DVector aVector(rTestPoint - aCutPoint); 2513 return aVector.getLength(); 2514 } 2515 } 2516 2517 double getSmallestDistancePointToEdge(const B2DPoint& rPointA, const B2DPoint& rPointB, const B2DPoint& rTestPoint, double& rCut) 2518 { 2519 if(rPointA.equal(rPointB)) 2520 { 2521 rCut = 0.0; 2522 const B2DVector aVector(rTestPoint - rPointA); 2523 return aVector.getLength(); 2524 } 2525 else 2526 { 2527 // get the relative cut value on line vector (Vector1) for cut with perpendicular through TestPoint 2528 const B2DVector aVector1(rPointB - rPointA); 2529 const B2DVector aVector2(rTestPoint - rPointA); 2530 const double fDividend((aVector2.getX() * aVector1.getX()) + (aVector2.getY() * aVector1.getY())); 2531 const double fDivisor((aVector1.getX() * aVector1.getX()) + (aVector1.getY() * aVector1.getY())); 2532 const double fCut(fDividend / fDivisor); 2533 2534 if(fCut < 0.0) 2535 { 2536 // not in line range, get distance to PointA 2537 rCut = 0.0; 2538 return aVector2.getLength(); 2539 } 2540 else if(fCut > 1.0) 2541 { 2542 // not in line range, get distance to PointB 2543 rCut = 1.0; 2544 const B2DVector aVector(rTestPoint - rPointB); 2545 return aVector.getLength(); 2546 } 2547 else 2548 { 2549 // in line range 2550 const B2DPoint aCutPoint(rPointA + fCut * aVector1); 2551 const B2DVector aVector(rTestPoint - aCutPoint); 2552 rCut = fCut; 2553 return aVector.getLength(); 2554 } 2555 } 2556 } 2557 2558 double getSmallestDistancePointToPolygon(const B2DPolygon& rCandidate, const B2DPoint& rTestPoint, sal_uInt32& rEdgeIndex, double& rCut) 2559 { 2560 double fRetval(DBL_MAX); 2561 const sal_uInt32 nPointCount(rCandidate.count()); 2562 2563 if(nPointCount > 1L) 2564 { 2565 const double fZero(0.0); 2566 const sal_uInt32 nEdgeCount(rCandidate.isClosed() ? nPointCount : nPointCount - 1L); 2567 B2DCubicBezier aBezier; 2568 aBezier.setStartPoint(rCandidate.getB2DPoint(0)); 2569 2570 for(sal_uInt32 a(0L); a < nEdgeCount; a++) 2571 { 2572 const sal_uInt32 nNextIndex((a + 1) % nPointCount); 2573 aBezier.setEndPoint(rCandidate.getB2DPoint(nNextIndex)); 2574 double fEdgeDist; 2575 double fNewCut; 2576 bool bEdgeIsCurve(false); 2577 2578 if(rCandidate.areControlPointsUsed()) 2579 { 2580 aBezier.setControlPointA(rCandidate.getNextControlPoint(a)); 2581 aBezier.setControlPointB(rCandidate.getPrevControlPoint(nNextIndex)); 2582 aBezier.testAndSolveTrivialBezier(); 2583 bEdgeIsCurve = aBezier.isBezier(); 2584 } 2585 2586 if(bEdgeIsCurve) 2587 { 2588 fEdgeDist = aBezier.getSmallestDistancePointToBezierSegment(rTestPoint, fNewCut); 2589 } 2590 else 2591 { 2592 fEdgeDist = getSmallestDistancePointToEdge(aBezier.getStartPoint(), aBezier.getEndPoint(), rTestPoint, fNewCut); 2593 } 2594 2595 if(DBL_MAX == fRetval || fEdgeDist < fRetval) 2596 { 2597 fRetval = fEdgeDist; 2598 rEdgeIndex = a; 2599 rCut = fNewCut; 2600 2601 if(fTools::equal(fRetval, fZero)) 2602 { 2603 // already found zero distance, cannot get better. Ensure numerical zero value and end loop. 2604 fRetval = 0.0; 2605 break; 2606 } 2607 } 2608 2609 // prepare next step 2610 aBezier.setStartPoint(aBezier.getEndPoint()); 2611 } 2612 2613 if(1.0 == rCut) 2614 { 2615 // correct rEdgeIndex when not last point 2616 if(rCandidate.isClosed()) 2617 { 2618 rEdgeIndex = getIndexOfSuccessor(rEdgeIndex, rCandidate); 2619 rCut = 0.0; 2620 } 2621 else 2622 { 2623 if(rEdgeIndex != nEdgeCount - 1L) 2624 { 2625 rEdgeIndex++; 2626 rCut = 0.0; 2627 } 2628 } 2629 } 2630 } 2631 2632 return fRetval; 2633 } 2634 2635 B2DPoint distort(const B2DPoint& rCandidate, const B2DRange& rOriginal, const B2DPoint& rTopLeft, const B2DPoint& rTopRight, const B2DPoint& rBottomLeft, const B2DPoint& rBottomRight) 2636 { 2637 if(fTools::equalZero(rOriginal.getWidth()) || fTools::equalZero(rOriginal.getHeight())) 2638 { 2639 return rCandidate; 2640 } 2641 else 2642 { 2643 const double fRelativeX((rCandidate.getX() - rOriginal.getMinX()) / rOriginal.getWidth()); 2644 const double fRelativeY((rCandidate.getY() - rOriginal.getMinY()) / rOriginal.getHeight()); 2645 const double fOneMinusRelativeX(1.0 - fRelativeX); 2646 const double fOneMinusRelativeY(1.0 - fRelativeY); 2647 const double fNewX((fOneMinusRelativeY) * ((fOneMinusRelativeX) * rTopLeft.getX() + fRelativeX * rTopRight.getX()) + 2648 fRelativeY * ((fOneMinusRelativeX) * rBottomLeft.getX() + fRelativeX * rBottomRight.getX())); 2649 const double fNewY((fOneMinusRelativeX) * ((fOneMinusRelativeY) * rTopLeft.getY() + fRelativeY * rBottomLeft.getY()) + 2650 fRelativeX * ((fOneMinusRelativeY) * rTopRight.getY() + fRelativeY * rBottomRight.getY())); 2651 2652 return B2DPoint(fNewX, fNewY); 2653 } 2654 } 2655 2656 B2DPolygon distort(const B2DPolygon& rCandidate, const B2DRange& rOriginal, const B2DPoint& rTopLeft, const B2DPoint& rTopRight, const B2DPoint& rBottomLeft, const B2DPoint& rBottomRight) 2657 { 2658 const sal_uInt32 nPointCount(rCandidate.count()); 2659 2660 if(nPointCount && 0.0 != rOriginal.getWidth() && 0.0 != rOriginal.getHeight()) 2661 { 2662 B2DPolygon aRetval; 2663 2664 for(sal_uInt32 a(0L); a < nPointCount; a++) 2665 { 2666 aRetval.append(distort(rCandidate.getB2DPoint(a), rOriginal, rTopLeft, rTopRight, rBottomLeft, rBottomRight)); 2667 2668 if(rCandidate.areControlPointsUsed()) 2669 { 2670 if(!rCandidate.getPrevControlPoint(a).equalZero()) 2671 { 2672 aRetval.setPrevControlPoint(a, distort(rCandidate.getPrevControlPoint(a), rOriginal, rTopLeft, rTopRight, rBottomLeft, rBottomRight)); 2673 } 2674 2675 if(!rCandidate.getNextControlPoint(a).equalZero()) 2676 { 2677 aRetval.setNextControlPoint(a, distort(rCandidate.getNextControlPoint(a), rOriginal, rTopLeft, rTopRight, rBottomLeft, rBottomRight)); 2678 } 2679 } 2680 } 2681 2682 aRetval.setClosed(rCandidate.isClosed()); 2683 return aRetval; 2684 } 2685 else 2686 { 2687 return rCandidate; 2688 } 2689 } 2690 2691 B2DPolygon rotateAroundPoint(const B2DPolygon& rCandidate, const B2DPoint& rCenter, double fAngle) 2692 { 2693 const sal_uInt32 nPointCount(rCandidate.count()); 2694 B2DPolygon aRetval(rCandidate); 2695 2696 if(nPointCount) 2697 { 2698 const B2DHomMatrix aMatrix(basegfx::tools::createRotateAroundPoint(rCenter, fAngle)); 2699 2700 aRetval.transform(aMatrix); 2701 } 2702 2703 return aRetval; 2704 } 2705 2706 B2DPolygon expandToCurve(const B2DPolygon& rCandidate) 2707 { 2708 B2DPolygon aRetval(rCandidate); 2709 2710 for(sal_uInt32 a(0L); a < rCandidate.count(); a++) 2711 { 2712 expandToCurveInPoint(aRetval, a); 2713 } 2714 2715 return aRetval; 2716 } 2717 2718 bool expandToCurveInPoint(B2DPolygon& rCandidate, sal_uInt32 nIndex) 2719 { 2720 OSL_ENSURE(nIndex < rCandidate.count(), "expandToCurveInPoint: Access to polygon out of range (!)"); 2721 bool bRetval(false); 2722 const sal_uInt32 nPointCount(rCandidate.count()); 2723 2724 if(nPointCount) 2725 { 2726 // predecessor 2727 if(!rCandidate.isPrevControlPointUsed(nIndex)) 2728 { 2729 if(!rCandidate.isClosed() && 0 == nIndex) 2730 { 2731 // do not create previous vector for start point of open polygon 2732 } 2733 else 2734 { 2735 const sal_uInt32 nPrevIndex((nIndex + (nPointCount - 1)) % nPointCount); 2736 rCandidate.setPrevControlPoint(nIndex, interpolate(rCandidate.getB2DPoint(nIndex), rCandidate.getB2DPoint(nPrevIndex), 1.0 / 3.0)); 2737 bRetval = true; 2738 } 2739 } 2740 2741 // successor 2742 if(!rCandidate.isNextControlPointUsed(nIndex)) 2743 { 2744 if(!rCandidate.isClosed() && nIndex + 1 == nPointCount) 2745 { 2746 // do not create next vector for end point of open polygon 2747 } 2748 else 2749 { 2750 const sal_uInt32 nNextIndex((nIndex + 1) % nPointCount); 2751 rCandidate.setNextControlPoint(nIndex, interpolate(rCandidate.getB2DPoint(nIndex), rCandidate.getB2DPoint(nNextIndex), 1.0 / 3.0)); 2752 bRetval = true; 2753 } 2754 } 2755 } 2756 2757 return bRetval; 2758 } 2759 2760 B2DPolygon setContinuity(const B2DPolygon& rCandidate, B2VectorContinuity eContinuity) 2761 { 2762 B2DPolygon aRetval(rCandidate); 2763 2764 for(sal_uInt32 a(0L); a < rCandidate.count(); a++) 2765 { 2766 setContinuityInPoint(aRetval, a, eContinuity); 2767 } 2768 2769 return aRetval; 2770 } 2771 2772 bool setContinuityInPoint(B2DPolygon& rCandidate, sal_uInt32 nIndex, B2VectorContinuity eContinuity) 2773 { 2774 OSL_ENSURE(nIndex < rCandidate.count(), "setContinuityInPoint: Access to polygon out of range (!)"); 2775 bool bRetval(false); 2776 const sal_uInt32 nPointCount(rCandidate.count()); 2777 2778 if(nPointCount) 2779 { 2780 const B2DPoint aCurrentPoint(rCandidate.getB2DPoint(nIndex)); 2781 2782 switch(eContinuity) 2783 { 2784 case CONTINUITY_NONE : 2785 { 2786 if(rCandidate.isPrevControlPointUsed(nIndex)) 2787 { 2788 if(!rCandidate.isClosed() && 0 == nIndex) 2789 { 2790 // remove existing previous vector for start point of open polygon 2791 rCandidate.resetPrevControlPoint(nIndex); 2792 } 2793 else 2794 { 2795 const sal_uInt32 nPrevIndex((nIndex + (nPointCount - 1)) % nPointCount); 2796 rCandidate.setPrevControlPoint(nIndex, interpolate(aCurrentPoint, rCandidate.getB2DPoint(nPrevIndex), 1.0 / 3.0)); 2797 } 2798 2799 bRetval = true; 2800 } 2801 2802 if(rCandidate.isNextControlPointUsed(nIndex)) 2803 { 2804 if(!rCandidate.isClosed() && nIndex == nPointCount + 1) 2805 { 2806 // remove next vector for end point of open polygon 2807 rCandidate.resetNextControlPoint(nIndex); 2808 } 2809 else 2810 { 2811 const sal_uInt32 nNextIndex((nIndex + 1) % nPointCount); 2812 rCandidate.setNextControlPoint(nIndex, interpolate(aCurrentPoint, rCandidate.getB2DPoint(nNextIndex), 1.0 / 3.0)); 2813 } 2814 2815 bRetval = true; 2816 } 2817 2818 break; 2819 } 2820 case CONTINUITY_C1 : 2821 { 2822 if(rCandidate.isPrevControlPointUsed(nIndex) && rCandidate.isNextControlPointUsed(nIndex)) 2823 { 2824 // lengths both exist since both are used 2825 B2DVector aVectorPrev(rCandidate.getPrevControlPoint(nIndex) - aCurrentPoint); 2826 B2DVector aVectorNext(rCandidate.getNextControlPoint(nIndex) - aCurrentPoint); 2827 const double fLenPrev(aVectorPrev.getLength()); 2828 const double fLenNext(aVectorNext.getLength()); 2829 aVectorPrev.normalize(); 2830 aVectorNext.normalize(); 2831 const B2VectorOrientation aOrientation(getOrientation(aVectorPrev, aVectorNext)); 2832 2833 if(ORIENTATION_NEUTRAL == aOrientation && aVectorPrev.scalar(aVectorNext) < 0.0) 2834 { 2835 // parallel and opposite direction; check length 2836 if(fTools::equal(fLenPrev, fLenNext)) 2837 { 2838 // this would be even C2, but we want C1. Use the lengths of the corresponding edges. 2839 const sal_uInt32 nPrevIndex((nIndex + (nPointCount - 1)) % nPointCount); 2840 const sal_uInt32 nNextIndex((nIndex + 1) % nPointCount); 2841 const double fLenPrevEdge(B2DVector(rCandidate.getB2DPoint(nPrevIndex) - aCurrentPoint).getLength() * (1.0 / 3.0)); 2842 const double fLenNextEdge(B2DVector(rCandidate.getB2DPoint(nNextIndex) - aCurrentPoint).getLength() * (1.0 / 3.0)); 2843 2844 rCandidate.setControlPoints(nIndex, 2845 aCurrentPoint + (aVectorPrev * fLenPrevEdge), 2846 aCurrentPoint + (aVectorNext * fLenNextEdge)); 2847 bRetval = true; 2848 } 2849 } 2850 else 2851 { 2852 // not parallel or same direction, set vectors and length 2853 const B2DVector aNormalizedPerpendicular(getNormalizedPerpendicular(aVectorPrev + aVectorNext)); 2854 2855 if(ORIENTATION_POSITIVE == aOrientation) 2856 { 2857 rCandidate.setControlPoints(nIndex, 2858 aCurrentPoint - (aNormalizedPerpendicular * fLenPrev), 2859 aCurrentPoint + (aNormalizedPerpendicular * fLenNext)); 2860 } 2861 else 2862 { 2863 rCandidate.setControlPoints(nIndex, 2864 aCurrentPoint + (aNormalizedPerpendicular * fLenPrev), 2865 aCurrentPoint - (aNormalizedPerpendicular * fLenNext)); 2866 } 2867 2868 bRetval = true; 2869 } 2870 } 2871 break; 2872 } 2873 case CONTINUITY_C2 : 2874 { 2875 if(rCandidate.isPrevControlPointUsed(nIndex) && rCandidate.isNextControlPointUsed(nIndex)) 2876 { 2877 // lengths both exist since both are used 2878 B2DVector aVectorPrev(rCandidate.getPrevControlPoint(nIndex) - aCurrentPoint); 2879 B2DVector aVectorNext(rCandidate.getNextControlPoint(nIndex) - aCurrentPoint); 2880 const double fCommonLength((aVectorPrev.getLength() + aVectorNext.getLength()) / 2.0); 2881 aVectorPrev.normalize(); 2882 aVectorNext.normalize(); 2883 const B2VectorOrientation aOrientation(getOrientation(aVectorPrev, aVectorNext)); 2884 2885 if(ORIENTATION_NEUTRAL == aOrientation && aVectorPrev.scalar(aVectorNext) < 0.0) 2886 { 2887 // parallel and opposite direction; set length. Use one direction for better numerical correctness 2888 const B2DVector aScaledDirection(aVectorPrev * fCommonLength); 2889 2890 rCandidate.setControlPoints(nIndex, 2891 aCurrentPoint + aScaledDirection, 2892 aCurrentPoint - aScaledDirection); 2893 } 2894 else 2895 { 2896 // not parallel or same direction, set vectors and length 2897 const B2DVector aNormalizedPerpendicular(getNormalizedPerpendicular(aVectorPrev + aVectorNext)); 2898 const B2DVector aPerpendicular(aNormalizedPerpendicular * fCommonLength); 2899 2900 if(ORIENTATION_POSITIVE == aOrientation) 2901 { 2902 rCandidate.setControlPoints(nIndex, 2903 aCurrentPoint - aPerpendicular, 2904 aCurrentPoint + aPerpendicular); 2905 } 2906 else 2907 { 2908 rCandidate.setControlPoints(nIndex, 2909 aCurrentPoint + aPerpendicular, 2910 aCurrentPoint - aPerpendicular); 2911 } 2912 } 2913 2914 bRetval = true; 2915 } 2916 break; 2917 } 2918 } 2919 } 2920 2921 return bRetval; 2922 } 2923 2924 B2DPolygon growInNormalDirection(const B2DPolygon& rCandidate, double fValue) 2925 { 2926 if(0.0 != fValue) 2927 { 2928 if(rCandidate.areControlPointsUsed()) 2929 { 2930 // call myself recursively with subdivided input 2931 const B2DPolygon aCandidate(adaptiveSubdivideByAngle(rCandidate)); 2932 return growInNormalDirection(aCandidate, fValue); 2933 } 2934 else 2935 { 2936 B2DPolygon aRetval; 2937 const sal_uInt32 nPointCount(rCandidate.count()); 2938 2939 if(nPointCount) 2940 { 2941 B2DPoint aPrev(rCandidate.getB2DPoint(nPointCount - 1L)); 2942 B2DPoint aCurrent(rCandidate.getB2DPoint(0L)); 2943 2944 for(sal_uInt32 a(0L); a < nPointCount; a++) 2945 { 2946 const B2DPoint aNext(rCandidate.getB2DPoint(a + 1L == nPointCount ? 0L : a + 1L)); 2947 const B2DVector aBack(aPrev - aCurrent); 2948 const B2DVector aForw(aNext - aCurrent); 2949 const B2DVector aPerpBack(getNormalizedPerpendicular(aBack)); 2950 const B2DVector aPerpForw(getNormalizedPerpendicular(aForw)); 2951 B2DVector aDirection(aPerpBack - aPerpForw); 2952 aDirection.normalize(); 2953 aDirection *= fValue; 2954 aRetval.append(aCurrent + aDirection); 2955 2956 // prepare next step 2957 aPrev = aCurrent; 2958 aCurrent = aNext; 2959 } 2960 } 2961 2962 // copy closed state 2963 aRetval.setClosed(rCandidate.isClosed()); 2964 2965 return aRetval; 2966 } 2967 } 2968 else 2969 { 2970 return rCandidate; 2971 } 2972 } 2973 2974 B2DPolygon reSegmentPolygon(const B2DPolygon& rCandidate, sal_uInt32 nSegments) 2975 { 2976 B2DPolygon aRetval; 2977 const sal_uInt32 nPointCount(rCandidate.count()); 2978 2979 if(nPointCount && nSegments) 2980 { 2981 // get current segment count 2982 const sal_uInt32 nSegmentCount(rCandidate.isClosed() ? nPointCount : nPointCount - 1L); 2983 2984 if(nSegmentCount == nSegments) 2985 { 2986 aRetval = rCandidate; 2987 } 2988 else 2989 { 2990 const double fLength(getLength(rCandidate)); 2991 const sal_uInt32 nLoopCount(rCandidate.isClosed() ? nSegments : nSegments + 1L); 2992 2993 for(sal_uInt32 a(0L); a < nLoopCount; a++) 2994 { 2995 const double fRelativePos((double)a / (double)nSegments); // 0.0 .. 1.0 2996 const B2DPoint aNewPoint(getPositionRelative(rCandidate, fRelativePos, fLength)); 2997 aRetval.append(aNewPoint); 2998 } 2999 3000 // copy closed flag 3001 aRetval.setClosed(rCandidate.isClosed()); 3002 } 3003 } 3004 3005 return aRetval; 3006 } 3007 3008 B2DPolygon reSegmentPolygonEdges(const B2DPolygon& rCandidate, sal_uInt32 nSubEdges, bool bHandleCurvedEdges, bool bHandleStraightEdges) 3009 { 3010 const sal_uInt32 nPointCount(rCandidate.count()); 3011 3012 if(nPointCount < 2 || nSubEdges < 2 || (!bHandleCurvedEdges && !bHandleStraightEdges)) 3013 { 3014 // nothing to do: 3015 // - less than two points -> no edge at all 3016 // - less than two nSubEdges -> no resegment necessary 3017 // - neither bHandleCurvedEdges nor bHandleStraightEdges -> nothing to do 3018 return rCandidate; 3019 } 3020 else 3021 { 3022 B2DPolygon aRetval; 3023 const sal_uInt32 nEdgeCount(rCandidate.isClosed() ? nPointCount : nPointCount - 1); 3024 B2DCubicBezier aCurrentEdge; 3025 3026 // prepare first edge and add start point to target 3027 aCurrentEdge.setStartPoint(rCandidate.getB2DPoint(0)); 3028 aRetval.append(aCurrentEdge.getStartPoint()); 3029 3030 for(sal_uInt32 a(0); a < nEdgeCount; a++) 3031 { 3032 // fill edge 3033 const sal_uInt32 nNextIndex((a + 1) % nPointCount); 3034 aCurrentEdge.setControlPointA(rCandidate.getNextControlPoint(a)); 3035 aCurrentEdge.setControlPointB(rCandidate.getPrevControlPoint(nNextIndex)); 3036 aCurrentEdge.setEndPoint(rCandidate.getB2DPoint(nNextIndex)); 3037 3038 if(aCurrentEdge.isBezier()) 3039 { 3040 if(bHandleCurvedEdges) 3041 { 3042 for(sal_uInt32 b(nSubEdges); b > 1; b--) 3043 { 3044 const double fSplitPoint(1.0 / b); 3045 B2DCubicBezier aLeftPart; 3046 3047 aCurrentEdge.split(fSplitPoint, &aLeftPart, &aCurrentEdge); 3048 aRetval.appendBezierSegment(aLeftPart.getControlPointA(), aLeftPart.getControlPointB(), aLeftPart.getEndPoint()); 3049 } 3050 } 3051 3052 // copy remaining segment to target 3053 aRetval.appendBezierSegment(aCurrentEdge.getControlPointA(), aCurrentEdge.getControlPointB(), aCurrentEdge.getEndPoint()); 3054 } 3055 else 3056 { 3057 if(bHandleStraightEdges) 3058 { 3059 for(sal_uInt32 b(nSubEdges); b > 1; b--) 3060 { 3061 const double fSplitPoint(1.0 / b); 3062 const B2DPoint aSplitPoint(interpolate(aCurrentEdge.getStartPoint(), aCurrentEdge.getEndPoint(), fSplitPoint)); 3063 3064 aRetval.append(aSplitPoint); 3065 aCurrentEdge.setStartPoint(aSplitPoint); 3066 } 3067 } 3068 3069 // copy remaining segment to target 3070 aRetval.append(aCurrentEdge.getEndPoint()); 3071 } 3072 3073 // prepare next step 3074 aCurrentEdge.setStartPoint(aCurrentEdge.getEndPoint()); 3075 } 3076 3077 // copy closed flag and return 3078 aRetval.setClosed(rCandidate.isClosed()); 3079 return aRetval; 3080 } 3081 } 3082 3083 B2DPolygon interpolate(const B2DPolygon& rOld1, const B2DPolygon& rOld2, double t) 3084 { 3085 OSL_ENSURE(rOld1.count() == rOld2.count(), "B2DPolygon interpolate: Different geometry (!)"); 3086 3087 if(fTools::lessOrEqual(t, 0.0) || rOld1 == rOld2) 3088 { 3089 return rOld1; 3090 } 3091 else if(fTools::moreOrEqual(t, 1.0)) 3092 { 3093 return rOld2; 3094 } 3095 else 3096 { 3097 B2DPolygon aRetval; 3098 const bool bInterpolateVectors(rOld1.areControlPointsUsed() || rOld2.areControlPointsUsed()); 3099 aRetval.setClosed(rOld1.isClosed() && rOld2.isClosed()); 3100 3101 for(sal_uInt32 a(0L); a < rOld1.count(); a++) 3102 { 3103 aRetval.append(interpolate(rOld1.getB2DPoint(a), rOld2.getB2DPoint(a), t)); 3104 3105 if(bInterpolateVectors) 3106 { 3107 aRetval.setPrevControlPoint(a, interpolate(rOld1.getPrevControlPoint(a), rOld2.getPrevControlPoint(a), t)); 3108 aRetval.setNextControlPoint(a, interpolate(rOld1.getNextControlPoint(a), rOld2.getNextControlPoint(a), t)); 3109 } 3110 } 3111 3112 return aRetval; 3113 } 3114 } 3115 3116 bool isPolyPolygonEqualRectangle( const B2DPolyPolygon& rPolyPoly, 3117 const B2DRange& rRect ) 3118 { 3119 // exclude some cheap cases first 3120 if( rPolyPoly.count() != 1 ) 3121 return false; 3122 3123 // fill array with rectangle vertices 3124 const B2DPoint aPoints[] = 3125 { 3126 B2DPoint(rRect.getMinX(),rRect.getMinY()), 3127 B2DPoint(rRect.getMaxX(),rRect.getMinY()), 3128 B2DPoint(rRect.getMaxX(),rRect.getMaxY()), 3129 B2DPoint(rRect.getMinX(),rRect.getMaxY()) 3130 }; 3131 3132 const B2DPolygon& rPoly( rPolyPoly.getB2DPolygon(0) ); 3133 const sal_uInt32 nCount( rPoly.count() ); 3134 const double epsilon = ::std::numeric_limits<double>::epsilon(); 3135 3136 for(unsigned int j=0; j<4; ++j) 3137 { 3138 const B2DPoint &p1 = aPoints[j]; 3139 const B2DPoint &p2 = aPoints[(j+1)%4]; 3140 bool bPointOnBoundary = false; 3141 for( sal_uInt32 i=0; i<nCount; ++i ) 3142 { 3143 const B2DPoint p(rPoly.getB2DPoint(i)); 3144 3145 // 1 | x0 y0 1 | 3146 // A = - | x1 y1 1 | 3147 // 2 | x2 y2 1 | 3148 double fDoubleArea = p2.getX()*p.getY() - 3149 p2.getY()*p.getX() - 3150 p1.getX()*p.getY() + 3151 p1.getY()*p.getX() + 3152 p1.getX()*p2.getY() - 3153 p1.getY()*p2.getX(); 3154 3155 if(fDoubleArea < epsilon) 3156 { 3157 bPointOnBoundary=true; 3158 break; 3159 } 3160 } 3161 if(!(bPointOnBoundary)) 3162 return false; 3163 } 3164 3165 return true; 3166 } 3167 3168 3169 // create simplified version of the original polygon by 3170 // replacing segments with spikes/loops and self intersections 3171 // by several trivial sub-segments 3172 B2DPolygon createSimplifiedPolygon( const B2DPolygon& rCandidate ) 3173 { 3174 const sal_uInt32 nCount(rCandidate.count()); 3175 3176 if(nCount && rCandidate.areControlPointsUsed()) 3177 { 3178 const sal_uInt32 nEdgeCount(rCandidate.isClosed() ? nCount : nCount - 1); 3179 B2DPolygon aRetval; 3180 B2DCubicBezier aSegment; 3181 3182 aSegment.setStartPoint(rCandidate.getB2DPoint(0)); 3183 aRetval.append(aSegment.getStartPoint()); 3184 3185 for(sal_uInt32 a(0); a < nEdgeCount; a++) 3186 { 3187 // fill edge 3188 const sal_uInt32 nNextIndex((a + 1) % nCount); 3189 aSegment.setControlPointA(rCandidate.getNextControlPoint(a)); 3190 aSegment.setControlPointB(rCandidate.getPrevControlPoint(nNextIndex)); 3191 aSegment.setEndPoint(rCandidate.getB2DPoint(nNextIndex)); 3192 3193 if(aSegment.isBezier()) 3194 { 3195 double fExtremumPos(0.0); 3196 sal_uInt32 nExtremumCounter(4); 3197 3198 while(nExtremumCounter-- && aSegment.isBezier() && aSegment.getMinimumExtremumPosition(fExtremumPos)) 3199 { 3200 // split off left, now extremum-free part and append 3201 B2DCubicBezier aLeft; 3202 3203 aSegment.split(fExtremumPos, &aLeft, &aSegment); 3204 aLeft.testAndSolveTrivialBezier(); 3205 aSegment.testAndSolveTrivialBezier(); 3206 3207 if(aLeft.isBezier()) 3208 { 3209 aRetval.appendBezierSegment(aLeft.getControlPointA(), aLeft.getControlPointB(), aLeft.getEndPoint()); 3210 } 3211 else 3212 { 3213 aRetval.append(aLeft.getEndPoint()); 3214 } 3215 } 3216 3217 // append (evtl. reduced) rest of Segment 3218 if(aSegment.isBezier()) 3219 { 3220 aRetval.appendBezierSegment(aSegment.getControlPointA(), aSegment.getControlPointB(), aSegment.getEndPoint()); 3221 } 3222 else 3223 { 3224 aRetval.append(aSegment.getEndPoint()); 3225 } 3226 } 3227 else 3228 { 3229 // simple edge, append end point 3230 aRetval.append(aSegment.getEndPoint()); 3231 } 3232 3233 // prepare next edge 3234 aSegment.setStartPoint(aSegment.getEndPoint()); 3235 } 3236 3237 // copy closed flag and check for double points 3238 aRetval.setClosed(rCandidate.isClosed()); 3239 aRetval.removeDoublePoints(); 3240 3241 return aRetval; 3242 } 3243 else 3244 { 3245 return rCandidate; 3246 } 3247 } 3248 3249 // #i76891# 3250 B2DPolygon simplifyCurveSegments(const B2DPolygon& rCandidate) 3251 { 3252 const sal_uInt32 nPointCount(rCandidate.count()); 3253 3254 if(nPointCount && rCandidate.areControlPointsUsed()) 3255 { 3256 // prepare loop 3257 const sal_uInt32 nEdgeCount(rCandidate.isClosed() ? nPointCount : nPointCount - 1); 3258 B2DPolygon aRetval; 3259 B2DCubicBezier aBezier; 3260 aBezier.setStartPoint(rCandidate.getB2DPoint(0)); 3261 3262 // try to avoid costly reallocations 3263 aRetval.reserve( nEdgeCount+1); 3264 3265 // add start point 3266 aRetval.append(aBezier.getStartPoint()); 3267 3268 for(sal_uInt32 a(0L); a < nEdgeCount; a++) 3269 { 3270 // get values for edge 3271 const sal_uInt32 nNextIndex((a + 1) % nPointCount); 3272 aBezier.setEndPoint(rCandidate.getB2DPoint(nNextIndex)); 3273 aBezier.setControlPointA(rCandidate.getNextControlPoint(a)); 3274 aBezier.setControlPointB(rCandidate.getPrevControlPoint(nNextIndex)); 3275 aBezier.testAndSolveTrivialBezier(); 3276 3277 // still bezier? 3278 if(aBezier.isBezier()) 3279 { 3280 // add edge with control vectors 3281 aRetval.appendBezierSegment(aBezier.getControlPointA(), aBezier.getControlPointB(), aBezier.getEndPoint()); 3282 } 3283 else 3284 { 3285 // add edge 3286 aRetval.append(aBezier.getEndPoint()); 3287 } 3288 3289 // next point 3290 aBezier.setStartPoint(aBezier.getEndPoint()); 3291 } 3292 3293 if(rCandidate.isClosed()) 3294 { 3295 // set closed flag, rescue control point and correct last double point 3296 closeWithGeometryChange(aRetval); 3297 } 3298 3299 return aRetval; 3300 } 3301 else 3302 { 3303 return rCandidate; 3304 } 3305 } 3306 3307 // makes the given indexed point the new polygon start point. To do that, the points in the 3308 // polygon will be rotated. This is only valid for closed polygons, for non-closed ones 3309 // an assertion will be triggered 3310 B2DPolygon makeStartPoint(const B2DPolygon& rCandidate, sal_uInt32 nIndexOfNewStatPoint) 3311 { 3312 const sal_uInt32 nPointCount(rCandidate.count()); 3313 3314 if(nPointCount > 2 && nIndexOfNewStatPoint != 0 && nIndexOfNewStatPoint < nPointCount) 3315 { 3316 OSL_ENSURE(rCandidate.isClosed(), "makeStartPoint: only valid for closed polygons (!)"); 3317 B2DPolygon aRetval; 3318 3319 for(sal_uInt32 a(0); a < nPointCount; a++) 3320 { 3321 const sal_uInt32 nSourceIndex((a + nIndexOfNewStatPoint) % nPointCount); 3322 aRetval.append(rCandidate.getB2DPoint(nSourceIndex)); 3323 3324 if(rCandidate.areControlPointsUsed()) 3325 { 3326 aRetval.setPrevControlPoint(a, rCandidate.getPrevControlPoint(nSourceIndex)); 3327 aRetval.setNextControlPoint(a, rCandidate.getNextControlPoint(nSourceIndex)); 3328 } 3329 } 3330 3331 return aRetval; 3332 } 3333 3334 return rCandidate; 3335 } 3336 3337 B2DPolygon createEdgesOfGivenLength(const B2DPolygon& rCandidate, double fLength, double fStart, double fEnd) 3338 { 3339 B2DPolygon aRetval; 3340 3341 if(fLength < 0.0) 3342 { 3343 fLength = 0.0; 3344 } 3345 3346 if(!fTools::equalZero(fLength)) 3347 { 3348 if(fStart < 0.0) 3349 { 3350 fStart = 0.0; 3351 } 3352 3353 if(fEnd < 0.0) 3354 { 3355 fEnd = 0.0; 3356 } 3357 3358 if(fEnd < fStart) 3359 { 3360 fEnd = fStart; 3361 } 3362 3363 // iterate and consume pieces with fLength. First subdivide to reduce input to line segments 3364 const B2DPolygon aCandidate(rCandidate.areControlPointsUsed() ? rCandidate.getDefaultAdaptiveSubdivision() : rCandidate); 3365 const sal_uInt32 nPointCount(aCandidate.count()); 3366 3367 if(nPointCount > 1) 3368 { 3369 const bool bEndActive(!fTools::equalZero(fEnd)); 3370 const sal_uInt32 nEdgeCount(aCandidate.isClosed() ? nPointCount : nPointCount - 1); 3371 B2DPoint aCurrent(aCandidate.getB2DPoint(0)); 3372 double fPositionInEdge(fStart); 3373 double fAbsolutePosition(fStart); 3374 3375 for(sal_uInt32 a(0); a < nEdgeCount; a++) 3376 { 3377 const sal_uInt32 nNextIndex((a + 1) % nPointCount); 3378 const B2DPoint aNext(aCandidate.getB2DPoint(nNextIndex)); 3379 const B2DVector aEdge(aNext - aCurrent); 3380 double fEdgeLength(aEdge.getLength()); 3381 3382 if(!fTools::equalZero(fEdgeLength)) 3383 { 3384 while(fTools::less(fPositionInEdge, fEdgeLength)) 3385 { 3386 // move position on edge forward as long as on edge 3387 const double fScalar(fPositionInEdge / fEdgeLength); 3388 aRetval.append(aCurrent + (aEdge * fScalar)); 3389 fPositionInEdge += fLength; 3390 3391 if(bEndActive) 3392 { 3393 fAbsolutePosition += fLength; 3394 3395 if(fTools::more(fAbsolutePosition, fEnd)) 3396 { 3397 break; 3398 } 3399 } 3400 } 3401 3402 // substract length of current edge 3403 fPositionInEdge -= fEdgeLength; 3404 } 3405 3406 if(bEndActive && fTools::more(fAbsolutePosition, fEnd)) 3407 { 3408 break; 3409 } 3410 3411 // prepare next step 3412 aCurrent = aNext; 3413 } 3414 3415 // keep closed state 3416 aRetval.setClosed(aCandidate.isClosed()); 3417 } 3418 else 3419 { 3420 // source polygon has only one point, return unchanged 3421 aRetval = aCandidate; 3422 } 3423 } 3424 3425 return aRetval; 3426 } 3427 3428 B2DPolygon createWaveline(const B2DPolygon& rCandidate, double fWaveWidth, double fWaveHeight) 3429 { 3430 B2DPolygon aRetval; 3431 3432 if(fWaveWidth < 0.0) 3433 { 3434 fWaveWidth = 0.0; 3435 } 3436 3437 if(fWaveHeight < 0.0) 3438 { 3439 fWaveHeight = 0.0; 3440 } 3441 3442 const bool bHasWidth(!fTools::equalZero(fWaveWidth)); 3443 const bool bHasHeight(!fTools::equalZero(fWaveHeight)); 3444 3445 if(bHasWidth) 3446 { 3447 if(bHasHeight) 3448 { 3449 // width and height, create waveline. First subdivide to reduce input to line segments 3450 // of WaveWidth. Last segment may be missing. If this turns out to be a problem, it 3451 // may be added here again using the original last point from rCandidate. It may 3452 // also be the case that rCandidate was closed. To simplify things it is handled here 3453 // as if it was opened. 3454 // Result from createEdgesOfGivenLength contains no curved segments, handle as straight 3455 // edges. 3456 const B2DPolygon aEqualLenghEdges(createEdgesOfGivenLength(rCandidate, fWaveWidth)); 3457 const sal_uInt32 nPointCount(aEqualLenghEdges.count()); 3458 3459 if(nPointCount > 1) 3460 { 3461 // iterate over straight edges, add start point 3462 B2DPoint aCurrent(aEqualLenghEdges.getB2DPoint(0)); 3463 aRetval.append(aCurrent); 3464 3465 for(sal_uInt32 a(0); a < nPointCount - 1; a++) 3466 { 3467 const sal_uInt32 nNextIndex((a + 1) % nPointCount); 3468 const B2DPoint aNext(aEqualLenghEdges.getB2DPoint(nNextIndex)); 3469 const B2DVector aEdge(aNext - aCurrent); 3470 const B2DVector aPerpendicular(getNormalizedPerpendicular(aEdge)); 3471 const B2DVector aControlOffset((aEdge * 0.467308) - (aPerpendicular * fWaveHeight)); 3472 3473 // add curve segment 3474 aRetval.appendBezierSegment( 3475 aCurrent + aControlOffset, 3476 aNext - aControlOffset, 3477 aNext); 3478 3479 // prepare next step 3480 aCurrent = aNext; 3481 } 3482 } 3483 } 3484 else 3485 { 3486 // width but no height -> return original polygon 3487 aRetval = rCandidate; 3488 } 3489 } 3490 else 3491 { 3492 // no width -> no waveline, stay empty and return 3493 } 3494 3495 return aRetval; 3496 } 3497 3498 ////////////////////////////////////////////////////////////////////// 3499 // comparators with tolerance for 2D Polygons 3500 3501 bool equal(const B2DPolygon& rCandidateA, const B2DPolygon& rCandidateB, const double& rfSmallValue) 3502 { 3503 const sal_uInt32 nPointCount(rCandidateA.count()); 3504 3505 if(nPointCount != rCandidateB.count()) 3506 return false; 3507 3508 const bool bClosed(rCandidateA.isClosed()); 3509 3510 if(bClosed != rCandidateB.isClosed()) 3511 return false; 3512 3513 const bool bAreControlPointsUsed(rCandidateA.areControlPointsUsed()); 3514 3515 if(bAreControlPointsUsed != rCandidateB.areControlPointsUsed()) 3516 return false; 3517 3518 for(sal_uInt32 a(0); a < nPointCount; a++) 3519 { 3520 const B2DPoint aPoint(rCandidateA.getB2DPoint(a)); 3521 3522 if(!aPoint.equal(rCandidateB.getB2DPoint(a), rfSmallValue)) 3523 return false; 3524 3525 if(bAreControlPointsUsed) 3526 { 3527 const basegfx::B2DPoint aPrev(rCandidateA.getPrevControlPoint(a)); 3528 3529 if(!aPrev.equal(rCandidateB.getPrevControlPoint(a), rfSmallValue)) 3530 return false; 3531 3532 const basegfx::B2DPoint aNext(rCandidateA.getNextControlPoint(a)); 3533 3534 if(!aNext.equal(rCandidateB.getNextControlPoint(a), rfSmallValue)) 3535 return false; 3536 } 3537 } 3538 3539 return true; 3540 } 3541 3542 bool equal(const B2DPolygon& rCandidateA, const B2DPolygon& rCandidateB) 3543 { 3544 const double fSmallValue(fTools::getSmallValue()); 3545 3546 return equal(rCandidateA, rCandidateB, fSmallValue); 3547 } 3548 3549 // snap points of horizontal or vertical edges to discrete values 3550 B2DPolygon snapPointsOfHorizontalOrVerticalEdges(const B2DPolygon& rCandidate) 3551 { 3552 const sal_uInt32 nPointCount(rCandidate.count()); 3553 3554 if(nPointCount > 1) 3555 { 3556 // Start by copying the source polygon to get a writeable copy. The closed state is 3557 // copied by aRetval's initialisation, too, so no need to copy it in this method 3558 B2DPolygon aRetval(rCandidate); 3559 3560 // prepare geometry data. Get rounded from original 3561 B2ITuple aPrevTuple(basegfx::fround(rCandidate.getB2DPoint(nPointCount - 1))); 3562 B2DPoint aCurrPoint(rCandidate.getB2DPoint(0)); 3563 B2ITuple aCurrTuple(basegfx::fround(aCurrPoint)); 3564 3565 // loop over all points. This will also snap the implicit closing edge 3566 // even when not closed, but that's no problem here 3567 for(sal_uInt32 a(0); a < nPointCount; a++) 3568 { 3569 // get next point. Get rounded from original 3570 const bool bLastRun(a + 1 == nPointCount); 3571 const sal_uInt32 nNextIndex(bLastRun ? 0 : a + 1); 3572 const B2DPoint aNextPoint(rCandidate.getB2DPoint(nNextIndex)); 3573 const B2ITuple aNextTuple(basegfx::fround(aNextPoint)); 3574 3575 // get the states 3576 const bool bPrevVertical(aPrevTuple.getX() == aCurrTuple.getX()); 3577 const bool bNextVertical(aNextTuple.getX() == aCurrTuple.getX()); 3578 const bool bPrevHorizontal(aPrevTuple.getY() == aCurrTuple.getY()); 3579 const bool bNextHorizontal(aNextTuple.getY() == aCurrTuple.getY()); 3580 const bool bSnapX(bPrevVertical || bNextVertical); 3581 const bool bSnapY(bPrevHorizontal || bNextHorizontal); 3582 3583 if(bSnapX || bSnapY) 3584 { 3585 const B2DPoint aSnappedPoint( 3586 bSnapX ? aCurrTuple.getX() : aCurrPoint.getX(), 3587 bSnapY ? aCurrTuple.getY() : aCurrPoint.getY()); 3588 3589 aRetval.setB2DPoint(a, aSnappedPoint); 3590 } 3591 3592 // prepare next point 3593 if(!bLastRun) 3594 { 3595 aPrevTuple = aCurrTuple; 3596 aCurrPoint = aNextPoint; 3597 aCurrTuple = aNextTuple; 3598 } 3599 } 3600 3601 return aRetval; 3602 } 3603 else 3604 { 3605 return rCandidate; 3606 } 3607 } 3608 3609 } // end of namespace tools 3610 } // end of namespace basegfx 3611 3612 ////////////////////////////////////////////////////////////////////////////// 3613 // eof 3614