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