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 createHalfUnitCircle() 1893 { 1894 static B2DPolygon aUnitHalfCircle; 1895 1896 if(!aUnitHalfCircle.count()) 1897 { 1898 const double fKappa((M_SQRT2 - 1.0) * 4.0 / 3.0); 1899 const double fScaledKappa(fKappa * (1.0 / STEPSPERQUARTER)); 1900 const B2DHomMatrix aRotateMatrix(createRotateB2DHomMatrix(F_PI2 / STEPSPERQUARTER)); 1901 B2DPoint aPoint(1.0, 0.0); 1902 B2DPoint aForward(1.0, fScaledKappa); 1903 B2DPoint aBackward(1.0, -fScaledKappa); 1904 1905 aUnitHalfCircle.append(aPoint); 1906 1907 for(sal_uInt32 a(0); a < STEPSPERQUARTER * 2; a++) 1908 { 1909 aPoint *= aRotateMatrix; 1910 aBackward *= aRotateMatrix; 1911 aUnitHalfCircle.appendBezierSegment(aForward, aBackward, aPoint); 1912 aForward *= aRotateMatrix; 1913 } 1914 } 1915 1916 return aUnitHalfCircle; 1917 } 1918 1919 B2DPolygon createPolygonFromUnitCircle(sal_uInt32 nStartQuadrant) 1920 { 1921 switch(nStartQuadrant % 4) 1922 { 1923 case 1 : 1924 { 1925 static B2DPolygon aUnitCircleStartQuadrantOne; 1926 1927 if(!aUnitCircleStartQuadrantOne.count()) 1928 { 1929 ::osl::Mutex m_mutex; 1930 aUnitCircleStartQuadrantOne = impCreateUnitCircle(1); 1931 } 1932 1933 return aUnitCircleStartQuadrantOne; 1934 } 1935 case 2 : 1936 { 1937 static B2DPolygon aUnitCircleStartQuadrantTwo; 1938 1939 if(!aUnitCircleStartQuadrantTwo.count()) 1940 { 1941 ::osl::Mutex m_mutex; 1942 aUnitCircleStartQuadrantTwo = impCreateUnitCircle(2); 1943 } 1944 1945 return aUnitCircleStartQuadrantTwo; 1946 } 1947 case 3 : 1948 { 1949 static B2DPolygon aUnitCircleStartQuadrantThree; 1950 1951 if(!aUnitCircleStartQuadrantThree.count()) 1952 { 1953 ::osl::Mutex m_mutex; 1954 aUnitCircleStartQuadrantThree = impCreateUnitCircle(3); 1955 } 1956 1957 return aUnitCircleStartQuadrantThree; 1958 } 1959 default : // case 0 : 1960 { 1961 static B2DPolygon aUnitCircleStartQuadrantZero; 1962 1963 if(!aUnitCircleStartQuadrantZero.count()) 1964 { 1965 ::osl::Mutex m_mutex; 1966 aUnitCircleStartQuadrantZero = impCreateUnitCircle(0); 1967 } 1968 1969 return aUnitCircleStartQuadrantZero; 1970 } 1971 } 1972 } 1973 1974 B2DPolygon createPolygonFromEllipse( const B2DPoint& rCenter, double fRadiusX, double fRadiusY ) 1975 { 1976 B2DPolygon aRetval(createPolygonFromUnitCircle()); 1977 const B2DHomMatrix aMatrix(createScaleTranslateB2DHomMatrix(fRadiusX, fRadiusY, rCenter.getX(), rCenter.getY())); 1978 1979 aRetval.transform(aMatrix); 1980 1981 return aRetval; 1982 } 1983 1984 B2DPolygon createPolygonFromUnitEllipseSegment( double fStart, double fEnd ) 1985 { 1986 B2DPolygon aRetval; 1987 1988 // truncate fStart, fEnd to a range of [0.0 .. F_2PI[ where F_2PI 1989 // falls back to 0.0 to ensure a unique definition 1990 if(fTools::less(fStart, 0.0)) 1991 { 1992 fStart = 0.0; 1993 } 1994 1995 if(fTools::moreOrEqual(fStart, F_2PI)) 1996 { 1997 fStart = 0.0; 1998 } 1999 2000 if(fTools::less(fEnd, 0.0)) 2001 { 2002 fEnd = 0.0; 2003 } 2004 2005 if(fTools::moreOrEqual(fEnd, F_2PI)) 2006 { 2007 fEnd = 0.0; 2008 } 2009 2010 if(fTools::equal(fStart, fEnd)) 2011 { 2012 // same start and end angle, add single point 2013 aRetval.append(B2DPoint(cos(fStart), sin(fStart))); 2014 } 2015 else 2016 { 2017 const sal_uInt32 nSegments(STEPSPERQUARTER * 4); 2018 const double fAnglePerSegment(F_PI2 / STEPSPERQUARTER); 2019 const sal_uInt32 nStartSegment(sal_uInt32(fStart / fAnglePerSegment) % nSegments); 2020 const sal_uInt32 nEndSegment(sal_uInt32(fEnd / fAnglePerSegment) % nSegments); 2021 const double fKappa((M_SQRT2 - 1.0) * 4.0 / 3.0); 2022 const double fScaledKappa(fKappa * (1.0 / STEPSPERQUARTER)); 2023 2024 B2DPoint aSegStart(cos(fStart), sin(fStart)); 2025 aRetval.append(aSegStart); 2026 2027 if(nStartSegment == nEndSegment && fTools::more(fEnd, fStart)) 2028 { 2029 // start and end in one sector and in the right order, create in one segment 2030 const B2DPoint aSegEnd(cos(fEnd), sin(fEnd)); 2031 const double fFactor(fScaledKappa * ((fEnd - fStart) / fAnglePerSegment)); 2032 2033 aRetval.appendBezierSegment( 2034 aSegStart + (B2DPoint(-aSegStart.getY(), aSegStart.getX()) * fFactor), 2035 aSegEnd - (B2DPoint(-aSegEnd.getY(), aSegEnd.getX()) * fFactor), 2036 aSegEnd); 2037 } 2038 else 2039 { 2040 double fSegEndRad((nStartSegment + 1) * fAnglePerSegment); 2041 double fFactor(fScaledKappa * ((fSegEndRad - fStart) / fAnglePerSegment)); 2042 B2DPoint aSegEnd(cos(fSegEndRad), sin(fSegEndRad)); 2043 2044 aRetval.appendBezierSegment( 2045 aSegStart + (B2DPoint(-aSegStart.getY(), aSegStart.getX()) * fFactor), 2046 aSegEnd - (B2DPoint(-aSegEnd.getY(), aSegEnd.getX()) * fFactor), 2047 aSegEnd); 2048 2049 sal_uInt32 nSegment((nStartSegment + 1) % nSegments); 2050 aSegStart = aSegEnd; 2051 2052 while(nSegment != nEndSegment) 2053 { 2054 // No end in this sector, add full sector. 2055 fSegEndRad = (nSegment + 1) * fAnglePerSegment; 2056 aSegEnd = B2DPoint(cos(fSegEndRad), sin(fSegEndRad)); 2057 2058 aRetval.appendBezierSegment( 2059 aSegStart + (B2DPoint(-aSegStart.getY(), aSegStart.getX()) * fScaledKappa), 2060 aSegEnd - (B2DPoint(-aSegEnd.getY(), aSegEnd.getX()) * fScaledKappa), 2061 aSegEnd); 2062 2063 nSegment = (nSegment + 1) % nSegments; 2064 aSegStart = aSegEnd; 2065 } 2066 2067 // End in this sector 2068 const double fSegStartRad(nSegment * fAnglePerSegment); 2069 fFactor = fScaledKappa * ((fEnd - fSegStartRad) / fAnglePerSegment); 2070 aSegEnd = B2DPoint(cos(fEnd), sin(fEnd)); 2071 2072 aRetval.appendBezierSegment( 2073 aSegStart + (B2DPoint(-aSegStart.getY(), aSegStart.getX()) * fFactor), 2074 aSegEnd - (B2DPoint(-aSegEnd.getY(), aSegEnd.getX()) * fFactor), 2075 aSegEnd); 2076 } 2077 } 2078 2079 // remove double points between segments created by segmented creation 2080 aRetval.removeDoublePoints(); 2081 2082 return aRetval; 2083 } 2084 2085 B2DPolygon createPolygonFromEllipseSegment( const B2DPoint& rCenter, double fRadiusX, double fRadiusY, double fStart, double fEnd ) 2086 { 2087 B2DPolygon aRetval(createPolygonFromUnitEllipseSegment(fStart, fEnd)); 2088 const B2DHomMatrix aMatrix(createScaleTranslateB2DHomMatrix(fRadiusX, fRadiusY, rCenter.getX(), rCenter.getY())); 2089 2090 aRetval.transform(aMatrix); 2091 2092 return aRetval; 2093 } 2094 2095 bool hasNeutralPoints(const B2DPolygon& rCandidate) 2096 { 2097 OSL_ENSURE(!rCandidate.areControlPointsUsed(), "hasNeutralPoints: ATM works not for curves (!)"); 2098 const sal_uInt32 nPointCount(rCandidate.count()); 2099 2100 if(nPointCount > 2L) 2101 { 2102 B2DPoint aPrevPoint(rCandidate.getB2DPoint(nPointCount - 1L)); 2103 B2DPoint aCurrPoint(rCandidate.getB2DPoint(0L)); 2104 2105 for(sal_uInt32 a(0L); a < nPointCount; a++) 2106 { 2107 const B2DPoint aNextPoint(rCandidate.getB2DPoint((a + 1) % nPointCount)); 2108 const B2DVector aPrevVec(aPrevPoint - aCurrPoint); 2109 const B2DVector aNextVec(aNextPoint - aCurrPoint); 2110 const B2VectorOrientation aOrientation(getOrientation(aNextVec, aPrevVec)); 2111 2112 if(ORIENTATION_NEUTRAL == aOrientation) 2113 { 2114 // current has neutral orientation 2115 return true; 2116 } 2117 else 2118 { 2119 // prepare next 2120 aPrevPoint = aCurrPoint; 2121 aCurrPoint = aNextPoint; 2122 } 2123 } 2124 } 2125 2126 return false; 2127 } 2128 2129 B2DPolygon removeNeutralPoints(const B2DPolygon& rCandidate) 2130 { 2131 if(hasNeutralPoints(rCandidate)) 2132 { 2133 const sal_uInt32 nPointCount(rCandidate.count()); 2134 B2DPolygon aRetval; 2135 B2DPoint aPrevPoint(rCandidate.getB2DPoint(nPointCount - 1L)); 2136 B2DPoint aCurrPoint(rCandidate.getB2DPoint(0L)); 2137 2138 for(sal_uInt32 a(0L); a < nPointCount; a++) 2139 { 2140 const B2DPoint aNextPoint(rCandidate.getB2DPoint((a + 1) % nPointCount)); 2141 const B2DVector aPrevVec(aPrevPoint - aCurrPoint); 2142 const B2DVector aNextVec(aNextPoint - aCurrPoint); 2143 const B2VectorOrientation aOrientation(getOrientation(aNextVec, aPrevVec)); 2144 2145 if(ORIENTATION_NEUTRAL == aOrientation) 2146 { 2147 // current has neutral orientation, leave it out and prepare next 2148 aCurrPoint = aNextPoint; 2149 } 2150 else 2151 { 2152 // add current point 2153 aRetval.append(aCurrPoint); 2154 2155 // prepare next 2156 aPrevPoint = aCurrPoint; 2157 aCurrPoint = aNextPoint; 2158 } 2159 } 2160 2161 while(aRetval.count() && ORIENTATION_NEUTRAL == getOrientationForIndex(aRetval, 0L)) 2162 { 2163 aRetval.remove(0L); 2164 } 2165 2166 // copy closed state 2167 aRetval.setClosed(rCandidate.isClosed()); 2168 2169 return aRetval; 2170 } 2171 else 2172 { 2173 return rCandidate; 2174 } 2175 } 2176 2177 bool isConvex(const B2DPolygon& rCandidate) 2178 { 2179 OSL_ENSURE(!rCandidate.areControlPointsUsed(), "isConvex: ATM works not for curves (!)"); 2180 const sal_uInt32 nPointCount(rCandidate.count()); 2181 2182 if(nPointCount > 2L) 2183 { 2184 const B2DPoint aPrevPoint(rCandidate.getB2DPoint(nPointCount - 1L)); 2185 B2DPoint aCurrPoint(rCandidate.getB2DPoint(0L)); 2186 B2DVector aCurrVec(aPrevPoint - aCurrPoint); 2187 B2VectorOrientation aOrientation(ORIENTATION_NEUTRAL); 2188 2189 for(sal_uInt32 a(0L); a < nPointCount; a++) 2190 { 2191 const B2DPoint aNextPoint(rCandidate.getB2DPoint((a + 1) % nPointCount)); 2192 const B2DVector aNextVec(aNextPoint - aCurrPoint); 2193 const B2VectorOrientation aCurrentOrientation(getOrientation(aNextVec, aCurrVec)); 2194 2195 if(ORIENTATION_NEUTRAL == aOrientation) 2196 { 2197 // set start value, maybe neutral again 2198 aOrientation = aCurrentOrientation; 2199 } 2200 else 2201 { 2202 if(ORIENTATION_NEUTRAL != aCurrentOrientation && aCurrentOrientation != aOrientation) 2203 { 2204 // different orientations found, that's it 2205 return false; 2206 } 2207 } 2208 2209 // prepare next 2210 aCurrPoint = aNextPoint; 2211 aCurrVec = -aNextVec; 2212 } 2213 } 2214 2215 return true; 2216 } 2217 2218 B2VectorOrientation getOrientationForIndex(const B2DPolygon& rCandidate, sal_uInt32 nIndex) 2219 { 2220 OSL_ENSURE(nIndex < rCandidate.count(), "getOrientationForIndex: index out of range (!)"); 2221 const B2DPoint aPrev(rCandidate.getB2DPoint(getIndexOfPredecessor(nIndex, rCandidate))); 2222 const B2DPoint aCurr(rCandidate.getB2DPoint(nIndex)); 2223 const B2DPoint aNext(rCandidate.getB2DPoint(getIndexOfSuccessor(nIndex, rCandidate))); 2224 const B2DVector aBack(aPrev - aCurr); 2225 const B2DVector aForw(aNext - aCurr); 2226 2227 return getOrientation(aForw, aBack); 2228 } 2229 2230 bool isPointOnLine(const B2DPoint& rStart, const B2DPoint& rEnd, const B2DPoint& rCandidate, bool bWithPoints) 2231 { 2232 if(rCandidate.equal(rStart) || rCandidate.equal(rEnd)) 2233 { 2234 // candidate is in epsilon around start or end -> inside 2235 return bWithPoints; 2236 } 2237 else if(rStart.equal(rEnd)) 2238 { 2239 // start and end are equal, but candidate is outside their epsilon -> outside 2240 return false; 2241 } 2242 else 2243 { 2244 const B2DVector aEdgeVector(rEnd - rStart); 2245 const B2DVector aTestVector(rCandidate - rStart); 2246 2247 if(areParallel(aEdgeVector, aTestVector)) 2248 { 2249 const double fZero(0.0); 2250 const double fOne(1.0); 2251 const double fParamTestOnCurr(fabs(aEdgeVector.getX()) > fabs(aEdgeVector.getY()) 2252 ? aTestVector.getX() / aEdgeVector.getX() 2253 : aTestVector.getY() / aEdgeVector.getY()); 2254 2255 if(fTools::more(fParamTestOnCurr, fZero) && fTools::less(fParamTestOnCurr, fOne)) 2256 { 2257 return true; 2258 } 2259 } 2260 2261 return false; 2262 } 2263 } 2264 2265 bool isPointOnPolygon(const B2DPolygon& rCandidate, const B2DPoint& rPoint, bool bWithPoints) 2266 { 2267 const B2DPolygon aCandidate(rCandidate.areControlPointsUsed() ? rCandidate.getDefaultAdaptiveSubdivision() : rCandidate); 2268 const sal_uInt32 nPointCount(aCandidate.count()); 2269 2270 if(nPointCount > 1L) 2271 { 2272 const sal_uInt32 nLoopCount(aCandidate.isClosed() ? nPointCount : nPointCount - 1L); 2273 B2DPoint aCurrentPoint(aCandidate.getB2DPoint(0L)); 2274 2275 for(sal_uInt32 a(0L); a < nLoopCount; a++) 2276 { 2277 const B2DPoint aNextPoint(aCandidate.getB2DPoint((a + 1L) % nPointCount)); 2278 2279 if(isPointOnLine(aCurrentPoint, aNextPoint, rPoint, bWithPoints)) 2280 { 2281 return true; 2282 } 2283 2284 aCurrentPoint = aNextPoint; 2285 } 2286 } 2287 else if(nPointCount && bWithPoints) 2288 { 2289 return rPoint.equal(aCandidate.getB2DPoint(0L)); 2290 } 2291 2292 return false; 2293 } 2294 2295 bool isPointInTriangle(const B2DPoint& rA, const B2DPoint& rB, const B2DPoint& rC, const B2DPoint& rCandidate, bool bWithBorder) 2296 { 2297 if(arePointsOnSameSideOfLine(rA, rB, rC, rCandidate, bWithBorder)) 2298 { 2299 if(arePointsOnSameSideOfLine(rB, rC, rA, rCandidate, bWithBorder)) 2300 { 2301 if(arePointsOnSameSideOfLine(rC, rA, rB, rCandidate, bWithBorder)) 2302 { 2303 return true; 2304 } 2305 } 2306 } 2307 2308 return false; 2309 } 2310 2311 bool arePointsOnSameSideOfLine(const B2DPoint& rStart, const B2DPoint& rEnd, const B2DPoint& rCandidateA, const B2DPoint& rCandidateB, bool bWithLine) 2312 { 2313 const B2DVector aLineVector(rEnd - rStart); 2314 const B2DVector aVectorToA(rEnd - rCandidateA); 2315 const double fCrossA(aLineVector.cross(aVectorToA)); 2316 2317 if(fTools::equalZero(fCrossA)) 2318 { 2319 // one point on the line 2320 return bWithLine; 2321 } 2322 2323 const B2DVector aVectorToB(rEnd - rCandidateB); 2324 const double fCrossB(aLineVector.cross(aVectorToB)); 2325 2326 if(fTools::equalZero(fCrossB)) 2327 { 2328 // one point on the line 2329 return bWithLine; 2330 } 2331 2332 // return true if they both have the same sign 2333 return ((fCrossA > 0.0) == (fCrossB > 0.0)); 2334 } 2335 2336 void addTriangleFan(const B2DPolygon& rCandidate, B2DPolygon& rTarget) 2337 { 2338 const sal_uInt32 nCount(rCandidate.count()); 2339 2340 if(nCount > 2L) 2341 { 2342 const B2DPoint aStart(rCandidate.getB2DPoint(0L)); 2343 B2DPoint aLast(rCandidate.getB2DPoint(1L)); 2344 2345 for(sal_uInt32 a(2L); a < nCount; a++) 2346 { 2347 const B2DPoint aCurrent(rCandidate.getB2DPoint(a)); 2348 rTarget.append(aStart); 2349 rTarget.append(aLast); 2350 rTarget.append(aCurrent); 2351 2352 // prepare next 2353 aLast = aCurrent; 2354 } 2355 } 2356 } 2357 2358 namespace 2359 { 2360 /// return 0 for input of 0, -1 for negative and 1 for positive input 2361 inline int lcl_sgn( const double n ) 2362 { 2363 return n == 0.0 ? 0 : 1 - 2*::rtl::math::isSignBitSet(n); 2364 } 2365 } 2366 2367 bool isRectangle( const B2DPolygon& rPoly ) 2368 { 2369 // polygon must be closed to resemble a rect, and contain 2370 // at least four points. 2371 if( !rPoly.isClosed() || 2372 rPoly.count() < 4 || 2373 rPoly.areControlPointsUsed() ) 2374 { 2375 return false; 2376 } 2377 2378 // number of 90 degree turns the polygon has taken 2379 int nNumTurns(0); 2380 2381 int nVerticalEdgeType=0; 2382 int nHorizontalEdgeType=0; 2383 bool bNullVertex(true); 2384 bool bCWPolygon(false); // when true, polygon is CW 2385 // oriented, when false, CCW 2386 bool bOrientationSet(false); // when false, polygon 2387 // orientation has not yet 2388 // been determined. 2389 2390 // scan all _edges_ (which involves coming back to point 0 2391 // for the last edge - thus the modulo operation below) 2392 const sal_Int32 nCount( rPoly.count() ); 2393 for( sal_Int32 i=0; i<nCount; ++i ) 2394 { 2395 const B2DPoint& rPoint0( rPoly.getB2DPoint(i % nCount) ); 2396 const B2DPoint& rPoint1( rPoly.getB2DPoint((i+1) % nCount) ); 2397 2398 // is 0 for zero direction vector, 1 for south edge and -1 2399 // for north edge (standard screen coordinate system) 2400 int nCurrVerticalEdgeType( lcl_sgn( rPoint1.getY() - rPoint0.getY() ) ); 2401 2402 // is 0 for zero direction vector, 1 for east edge and -1 2403 // for west edge (standard screen coordinate system) 2404 int nCurrHorizontalEdgeType( lcl_sgn(rPoint1.getX() - rPoint0.getX()) ); 2405 2406 if( nCurrVerticalEdgeType && nCurrHorizontalEdgeType ) 2407 return false; // oblique edge - for sure no rect 2408 2409 const bool bCurrNullVertex( !nCurrVerticalEdgeType && !nCurrHorizontalEdgeType ); 2410 2411 // current vertex is equal to previous - just skip, 2412 // until we have a real edge 2413 if( bCurrNullVertex ) 2414 continue; 2415 2416 // if previous edge has two identical points, because 2417 // no previous edge direction was available, simply 2418 // take this first non-null edge as the start 2419 // direction. That's what will happen here, if 2420 // bNullVertex is false 2421 if( !bNullVertex ) 2422 { 2423 // 2D cross product - is 1 for CW and -1 for CCW turns 2424 const int nCrossProduct( nHorizontalEdgeType*nCurrVerticalEdgeType - 2425 nVerticalEdgeType*nCurrHorizontalEdgeType ); 2426 2427 if( !nCrossProduct ) 2428 continue; // no change in orientation - 2429 // collinear edges - just go on 2430 2431 // if polygon orientation is not set, we'll 2432 // determine it now 2433 if( !bOrientationSet ) 2434 { 2435 bCWPolygon = nCrossProduct == 1; 2436 bOrientationSet = true; 2437 } 2438 else 2439 { 2440 // if current turn orientation is not equal 2441 // initial orientation, this is not a 2442 // rectangle (as rectangles have consistent 2443 // orientation). 2444 if( (nCrossProduct == 1) != bCWPolygon ) 2445 return false; 2446 } 2447 2448 ++nNumTurns; 2449 2450 // More than four 90 degree turns are an 2451 // indication that this must not be a rectangle. 2452 if( nNumTurns > 4 ) 2453 return false; 2454 } 2455 2456 // store current state for the next turn 2457 nVerticalEdgeType = nCurrVerticalEdgeType; 2458 nHorizontalEdgeType = nCurrHorizontalEdgeType; 2459 bNullVertex = false; // won't reach this line, 2460 // if bCurrNullVertex is 2461 // true - see above 2462 } 2463 2464 return true; 2465 } 2466 2467 B3DPolygon createB3DPolygonFromB2DPolygon(const B2DPolygon& rCandidate, double fZCoordinate) 2468 { 2469 if(rCandidate.areControlPointsUsed()) 2470 { 2471 // call myself recursively with subdivided input 2472 const B2DPolygon aCandidate(adaptiveSubdivideByAngle(rCandidate)); 2473 return createB3DPolygonFromB2DPolygon(aCandidate, fZCoordinate); 2474 } 2475 else 2476 { 2477 B3DPolygon aRetval; 2478 2479 for(sal_uInt32 a(0L); a < rCandidate.count(); a++) 2480 { 2481 B2DPoint aPoint(rCandidate.getB2DPoint(a)); 2482 aRetval.append(B3DPoint(aPoint.getX(), aPoint.getY(), fZCoordinate)); 2483 } 2484 2485 // copy closed state 2486 aRetval.setClosed(rCandidate.isClosed()); 2487 2488 return aRetval; 2489 } 2490 } 2491 2492 B2DPolygon createB2DPolygonFromB3DPolygon(const B3DPolygon& rCandidate, const B3DHomMatrix& rMat) 2493 { 2494 B2DPolygon aRetval; 2495 const sal_uInt32 nCount(rCandidate.count()); 2496 const bool bIsIdentity(rMat.isIdentity()); 2497 2498 for(sal_uInt32 a(0L); a < nCount; a++) 2499 { 2500 B3DPoint aCandidate(rCandidate.getB3DPoint(a)); 2501 2502 if(!bIsIdentity) 2503 { 2504 aCandidate *= rMat; 2505 } 2506 2507 aRetval.append(B2DPoint(aCandidate.getX(), aCandidate.getY())); 2508 } 2509 2510 // copy closed state 2511 aRetval.setClosed(rCandidate.isClosed()); 2512 2513 return aRetval; 2514 } 2515 2516 double getDistancePointToEndlessRay(const B2DPoint& rPointA, const B2DPoint& rPointB, const B2DPoint& rTestPoint, double& rCut) 2517 { 2518 if(rPointA.equal(rPointB)) 2519 { 2520 rCut = 0.0; 2521 const B2DVector aVector(rTestPoint - rPointA); 2522 return aVector.getLength(); 2523 } 2524 else 2525 { 2526 // get the relative cut value on line vector (Vector1) for cut with perpendicular through TestPoint 2527 const B2DVector aVector1(rPointB - rPointA); 2528 const B2DVector aVector2(rTestPoint - rPointA); 2529 const double fDividend((aVector2.getX() * aVector1.getX()) + (aVector2.getY() * aVector1.getY())); 2530 const double fDivisor((aVector1.getX() * aVector1.getX()) + (aVector1.getY() * aVector1.getY())); 2531 2532 rCut = fDividend / fDivisor; 2533 2534 const B2DPoint aCutPoint(rPointA + rCut * aVector1); 2535 const B2DVector aVector(rTestPoint - aCutPoint); 2536 return aVector.getLength(); 2537 } 2538 } 2539 2540 double getSmallestDistancePointToEdge(const B2DPoint& rPointA, const B2DPoint& rPointB, const B2DPoint& rTestPoint, double& rCut) 2541 { 2542 if(rPointA.equal(rPointB)) 2543 { 2544 rCut = 0.0; 2545 const B2DVector aVector(rTestPoint - rPointA); 2546 return aVector.getLength(); 2547 } 2548 else 2549 { 2550 // get the relative cut value on line vector (Vector1) for cut with perpendicular through TestPoint 2551 const B2DVector aVector1(rPointB - rPointA); 2552 const B2DVector aVector2(rTestPoint - rPointA); 2553 const double fDividend((aVector2.getX() * aVector1.getX()) + (aVector2.getY() * aVector1.getY())); 2554 const double fDivisor((aVector1.getX() * aVector1.getX()) + (aVector1.getY() * aVector1.getY())); 2555 const double fCut(fDividend / fDivisor); 2556 2557 if(fCut < 0.0) 2558 { 2559 // not in line range, get distance to PointA 2560 rCut = 0.0; 2561 return aVector2.getLength(); 2562 } 2563 else if(fCut > 1.0) 2564 { 2565 // not in line range, get distance to PointB 2566 rCut = 1.0; 2567 const B2DVector aVector(rTestPoint - rPointB); 2568 return aVector.getLength(); 2569 } 2570 else 2571 { 2572 // in line range 2573 const B2DPoint aCutPoint(rPointA + fCut * aVector1); 2574 const B2DVector aVector(rTestPoint - aCutPoint); 2575 rCut = fCut; 2576 return aVector.getLength(); 2577 } 2578 } 2579 } 2580 2581 double getSmallestDistancePointToPolygon(const B2DPolygon& rCandidate, const B2DPoint& rTestPoint, sal_uInt32& rEdgeIndex, double& rCut) 2582 { 2583 double fRetval(DBL_MAX); 2584 const sal_uInt32 nPointCount(rCandidate.count()); 2585 2586 if(nPointCount > 1L) 2587 { 2588 const double fZero(0.0); 2589 const sal_uInt32 nEdgeCount(rCandidate.isClosed() ? nPointCount : nPointCount - 1L); 2590 B2DCubicBezier aBezier; 2591 aBezier.setStartPoint(rCandidate.getB2DPoint(0)); 2592 2593 for(sal_uInt32 a(0L); a < nEdgeCount; a++) 2594 { 2595 const sal_uInt32 nNextIndex((a + 1) % nPointCount); 2596 aBezier.setEndPoint(rCandidate.getB2DPoint(nNextIndex)); 2597 double fEdgeDist; 2598 double fNewCut; 2599 bool bEdgeIsCurve(false); 2600 2601 if(rCandidate.areControlPointsUsed()) 2602 { 2603 aBezier.setControlPointA(rCandidate.getNextControlPoint(a)); 2604 aBezier.setControlPointB(rCandidate.getPrevControlPoint(nNextIndex)); 2605 aBezier.testAndSolveTrivialBezier(); 2606 bEdgeIsCurve = aBezier.isBezier(); 2607 } 2608 2609 if(bEdgeIsCurve) 2610 { 2611 fEdgeDist = aBezier.getSmallestDistancePointToBezierSegment(rTestPoint, fNewCut); 2612 } 2613 else 2614 { 2615 fEdgeDist = getSmallestDistancePointToEdge(aBezier.getStartPoint(), aBezier.getEndPoint(), rTestPoint, fNewCut); 2616 } 2617 2618 if(DBL_MAX == fRetval || fEdgeDist < fRetval) 2619 { 2620 fRetval = fEdgeDist; 2621 rEdgeIndex = a; 2622 rCut = fNewCut; 2623 2624 if(fTools::equal(fRetval, fZero)) 2625 { 2626 // already found zero distance, cannot get better. Ensure numerical zero value and end loop. 2627 fRetval = 0.0; 2628 break; 2629 } 2630 } 2631 2632 // prepare next step 2633 aBezier.setStartPoint(aBezier.getEndPoint()); 2634 } 2635 2636 if(1.0 == rCut) 2637 { 2638 // correct rEdgeIndex when not last point 2639 if(rCandidate.isClosed()) 2640 { 2641 rEdgeIndex = getIndexOfSuccessor(rEdgeIndex, rCandidate); 2642 rCut = 0.0; 2643 } 2644 else 2645 { 2646 if(rEdgeIndex != nEdgeCount - 1L) 2647 { 2648 rEdgeIndex++; 2649 rCut = 0.0; 2650 } 2651 } 2652 } 2653 } 2654 2655 return fRetval; 2656 } 2657 2658 B2DPoint distort(const B2DPoint& rCandidate, const B2DRange& rOriginal, const B2DPoint& rTopLeft, const B2DPoint& rTopRight, const B2DPoint& rBottomLeft, const B2DPoint& rBottomRight) 2659 { 2660 if(fTools::equalZero(rOriginal.getWidth()) || fTools::equalZero(rOriginal.getHeight())) 2661 { 2662 return rCandidate; 2663 } 2664 else 2665 { 2666 const double fRelativeX((rCandidate.getX() - rOriginal.getMinX()) / rOriginal.getWidth()); 2667 const double fRelativeY((rCandidate.getY() - rOriginal.getMinY()) / rOriginal.getHeight()); 2668 const double fOneMinusRelativeX(1.0 - fRelativeX); 2669 const double fOneMinusRelativeY(1.0 - fRelativeY); 2670 const double fNewX((fOneMinusRelativeY) * ((fOneMinusRelativeX) * rTopLeft.getX() + fRelativeX * rTopRight.getX()) + 2671 fRelativeY * ((fOneMinusRelativeX) * rBottomLeft.getX() + fRelativeX * rBottomRight.getX())); 2672 const double fNewY((fOneMinusRelativeX) * ((fOneMinusRelativeY) * rTopLeft.getY() + fRelativeY * rBottomLeft.getY()) + 2673 fRelativeX * ((fOneMinusRelativeY) * rTopRight.getY() + fRelativeY * rBottomRight.getY())); 2674 2675 return B2DPoint(fNewX, fNewY); 2676 } 2677 } 2678 2679 B2DPolygon distort(const B2DPolygon& rCandidate, const B2DRange& rOriginal, const B2DPoint& rTopLeft, const B2DPoint& rTopRight, const B2DPoint& rBottomLeft, const B2DPoint& rBottomRight) 2680 { 2681 const sal_uInt32 nPointCount(rCandidate.count()); 2682 2683 if(nPointCount && 0.0 != rOriginal.getWidth() && 0.0 != rOriginal.getHeight()) 2684 { 2685 B2DPolygon aRetval; 2686 2687 for(sal_uInt32 a(0L); a < nPointCount; a++) 2688 { 2689 aRetval.append(distort(rCandidate.getB2DPoint(a), rOriginal, rTopLeft, rTopRight, rBottomLeft, rBottomRight)); 2690 2691 if(rCandidate.areControlPointsUsed()) 2692 { 2693 if(!rCandidate.getPrevControlPoint(a).equalZero()) 2694 { 2695 aRetval.setPrevControlPoint(a, distort(rCandidate.getPrevControlPoint(a), rOriginal, rTopLeft, rTopRight, rBottomLeft, rBottomRight)); 2696 } 2697 2698 if(!rCandidate.getNextControlPoint(a).equalZero()) 2699 { 2700 aRetval.setNextControlPoint(a, distort(rCandidate.getNextControlPoint(a), rOriginal, rTopLeft, rTopRight, rBottomLeft, rBottomRight)); 2701 } 2702 } 2703 } 2704 2705 aRetval.setClosed(rCandidate.isClosed()); 2706 return aRetval; 2707 } 2708 else 2709 { 2710 return rCandidate; 2711 } 2712 } 2713 2714 B2DPolygon rotateAroundPoint(const B2DPolygon& rCandidate, const B2DPoint& rCenter, double fAngle) 2715 { 2716 const sal_uInt32 nPointCount(rCandidate.count()); 2717 B2DPolygon aRetval(rCandidate); 2718 2719 if(nPointCount) 2720 { 2721 const B2DHomMatrix aMatrix(basegfx::tools::createRotateAroundPoint(rCenter, fAngle)); 2722 2723 aRetval.transform(aMatrix); 2724 } 2725 2726 return aRetval; 2727 } 2728 2729 B2DPolygon expandToCurve(const B2DPolygon& rCandidate) 2730 { 2731 B2DPolygon aRetval(rCandidate); 2732 2733 for(sal_uInt32 a(0L); a < rCandidate.count(); a++) 2734 { 2735 expandToCurveInPoint(aRetval, a); 2736 } 2737 2738 return aRetval; 2739 } 2740 2741 bool expandToCurveInPoint(B2DPolygon& rCandidate, sal_uInt32 nIndex) 2742 { 2743 OSL_ENSURE(nIndex < rCandidate.count(), "expandToCurveInPoint: Access to polygon out of range (!)"); 2744 bool bRetval(false); 2745 const sal_uInt32 nPointCount(rCandidate.count()); 2746 2747 if(nPointCount) 2748 { 2749 // predecessor 2750 if(!rCandidate.isPrevControlPointUsed(nIndex)) 2751 { 2752 if(!rCandidate.isClosed() && 0 == nIndex) 2753 { 2754 // do not create previous vector for start point of open polygon 2755 } 2756 else 2757 { 2758 const sal_uInt32 nPrevIndex((nIndex + (nPointCount - 1)) % nPointCount); 2759 rCandidate.setPrevControlPoint(nIndex, interpolate(rCandidate.getB2DPoint(nIndex), rCandidate.getB2DPoint(nPrevIndex), 1.0 / 3.0)); 2760 bRetval = true; 2761 } 2762 } 2763 2764 // successor 2765 if(!rCandidate.isNextControlPointUsed(nIndex)) 2766 { 2767 if(!rCandidate.isClosed() && nIndex + 1 == nPointCount) 2768 { 2769 // do not create next vector for end point of open polygon 2770 } 2771 else 2772 { 2773 const sal_uInt32 nNextIndex((nIndex + 1) % nPointCount); 2774 rCandidate.setNextControlPoint(nIndex, interpolate(rCandidate.getB2DPoint(nIndex), rCandidate.getB2DPoint(nNextIndex), 1.0 / 3.0)); 2775 bRetval = true; 2776 } 2777 } 2778 } 2779 2780 return bRetval; 2781 } 2782 2783 B2DPolygon setContinuity(const B2DPolygon& rCandidate, B2VectorContinuity eContinuity) 2784 { 2785 B2DPolygon aRetval(rCandidate); 2786 2787 for(sal_uInt32 a(0L); a < rCandidate.count(); a++) 2788 { 2789 setContinuityInPoint(aRetval, a, eContinuity); 2790 } 2791 2792 return aRetval; 2793 } 2794 2795 bool setContinuityInPoint(B2DPolygon& rCandidate, sal_uInt32 nIndex, B2VectorContinuity eContinuity) 2796 { 2797 OSL_ENSURE(nIndex < rCandidate.count(), "setContinuityInPoint: Access to polygon out of range (!)"); 2798 bool bRetval(false); 2799 const sal_uInt32 nPointCount(rCandidate.count()); 2800 2801 if(nPointCount) 2802 { 2803 const B2DPoint aCurrentPoint(rCandidate.getB2DPoint(nIndex)); 2804 2805 switch(eContinuity) 2806 { 2807 case CONTINUITY_NONE : 2808 { 2809 if(rCandidate.isPrevControlPointUsed(nIndex)) 2810 { 2811 if(!rCandidate.isClosed() && 0 == nIndex) 2812 { 2813 // remove existing previous vector for start point of open polygon 2814 rCandidate.resetPrevControlPoint(nIndex); 2815 } 2816 else 2817 { 2818 const sal_uInt32 nPrevIndex((nIndex + (nPointCount - 1)) % nPointCount); 2819 rCandidate.setPrevControlPoint(nIndex, interpolate(aCurrentPoint, rCandidate.getB2DPoint(nPrevIndex), 1.0 / 3.0)); 2820 } 2821 2822 bRetval = true; 2823 } 2824 2825 if(rCandidate.isNextControlPointUsed(nIndex)) 2826 { 2827 if(!rCandidate.isClosed() && nIndex == nPointCount + 1) 2828 { 2829 // remove next vector for end point of open polygon 2830 rCandidate.resetNextControlPoint(nIndex); 2831 } 2832 else 2833 { 2834 const sal_uInt32 nNextIndex((nIndex + 1) % nPointCount); 2835 rCandidate.setNextControlPoint(nIndex, interpolate(aCurrentPoint, rCandidate.getB2DPoint(nNextIndex), 1.0 / 3.0)); 2836 } 2837 2838 bRetval = true; 2839 } 2840 2841 break; 2842 } 2843 case CONTINUITY_C1 : 2844 { 2845 if(rCandidate.isPrevControlPointUsed(nIndex) && rCandidate.isNextControlPointUsed(nIndex)) 2846 { 2847 // lengths both exist since both are used 2848 B2DVector aVectorPrev(rCandidate.getPrevControlPoint(nIndex) - aCurrentPoint); 2849 B2DVector aVectorNext(rCandidate.getNextControlPoint(nIndex) - aCurrentPoint); 2850 const double fLenPrev(aVectorPrev.getLength()); 2851 const double fLenNext(aVectorNext.getLength()); 2852 aVectorPrev.normalize(); 2853 aVectorNext.normalize(); 2854 const B2VectorOrientation aOrientation(getOrientation(aVectorPrev, aVectorNext)); 2855 2856 if(ORIENTATION_NEUTRAL == aOrientation && aVectorPrev.scalar(aVectorNext) < 0.0) 2857 { 2858 // parallel and opposite direction; check length 2859 if(fTools::equal(fLenPrev, fLenNext)) 2860 { 2861 // this would be even C2, but we want C1. Use the lengths of the corresponding edges. 2862 const sal_uInt32 nPrevIndex((nIndex + (nPointCount - 1)) % nPointCount); 2863 const sal_uInt32 nNextIndex((nIndex + 1) % nPointCount); 2864 const double fLenPrevEdge(B2DVector(rCandidate.getB2DPoint(nPrevIndex) - aCurrentPoint).getLength() * (1.0 / 3.0)); 2865 const double fLenNextEdge(B2DVector(rCandidate.getB2DPoint(nNextIndex) - aCurrentPoint).getLength() * (1.0 / 3.0)); 2866 2867 rCandidate.setControlPoints(nIndex, 2868 aCurrentPoint + (aVectorPrev * fLenPrevEdge), 2869 aCurrentPoint + (aVectorNext * fLenNextEdge)); 2870 bRetval = true; 2871 } 2872 } 2873 else 2874 { 2875 // not parallel or same direction, set vectors and length 2876 const B2DVector aNormalizedPerpendicular(getNormalizedPerpendicular(aVectorPrev + aVectorNext)); 2877 2878 if(ORIENTATION_POSITIVE == aOrientation) 2879 { 2880 rCandidate.setControlPoints(nIndex, 2881 aCurrentPoint - (aNormalizedPerpendicular * fLenPrev), 2882 aCurrentPoint + (aNormalizedPerpendicular * fLenNext)); 2883 } 2884 else 2885 { 2886 rCandidate.setControlPoints(nIndex, 2887 aCurrentPoint + (aNormalizedPerpendicular * fLenPrev), 2888 aCurrentPoint - (aNormalizedPerpendicular * fLenNext)); 2889 } 2890 2891 bRetval = true; 2892 } 2893 } 2894 break; 2895 } 2896 case CONTINUITY_C2 : 2897 { 2898 if(rCandidate.isPrevControlPointUsed(nIndex) && rCandidate.isNextControlPointUsed(nIndex)) 2899 { 2900 // lengths both exist since both are used 2901 B2DVector aVectorPrev(rCandidate.getPrevControlPoint(nIndex) - aCurrentPoint); 2902 B2DVector aVectorNext(rCandidate.getNextControlPoint(nIndex) - aCurrentPoint); 2903 const double fCommonLength((aVectorPrev.getLength() + aVectorNext.getLength()) / 2.0); 2904 aVectorPrev.normalize(); 2905 aVectorNext.normalize(); 2906 const B2VectorOrientation aOrientation(getOrientation(aVectorPrev, aVectorNext)); 2907 2908 if(ORIENTATION_NEUTRAL == aOrientation && aVectorPrev.scalar(aVectorNext) < 0.0) 2909 { 2910 // parallel and opposite direction; set length. Use one direction for better numerical correctness 2911 const B2DVector aScaledDirection(aVectorPrev * fCommonLength); 2912 2913 rCandidate.setControlPoints(nIndex, 2914 aCurrentPoint + aScaledDirection, 2915 aCurrentPoint - aScaledDirection); 2916 } 2917 else 2918 { 2919 // not parallel or same direction, set vectors and length 2920 const B2DVector aNormalizedPerpendicular(getNormalizedPerpendicular(aVectorPrev + aVectorNext)); 2921 const B2DVector aPerpendicular(aNormalizedPerpendicular * fCommonLength); 2922 2923 if(ORIENTATION_POSITIVE == aOrientation) 2924 { 2925 rCandidate.setControlPoints(nIndex, 2926 aCurrentPoint - aPerpendicular, 2927 aCurrentPoint + aPerpendicular); 2928 } 2929 else 2930 { 2931 rCandidate.setControlPoints(nIndex, 2932 aCurrentPoint + aPerpendicular, 2933 aCurrentPoint - aPerpendicular); 2934 } 2935 } 2936 2937 bRetval = true; 2938 } 2939 break; 2940 } 2941 } 2942 } 2943 2944 return bRetval; 2945 } 2946 2947 B2DPolygon growInNormalDirection(const B2DPolygon& rCandidate, double fValue) 2948 { 2949 if(0.0 != fValue) 2950 { 2951 if(rCandidate.areControlPointsUsed()) 2952 { 2953 // call myself recursively with subdivided input 2954 const B2DPolygon aCandidate(adaptiveSubdivideByAngle(rCandidate)); 2955 return growInNormalDirection(aCandidate, fValue); 2956 } 2957 else 2958 { 2959 B2DPolygon aRetval; 2960 const sal_uInt32 nPointCount(rCandidate.count()); 2961 2962 if(nPointCount) 2963 { 2964 B2DPoint aPrev(rCandidate.getB2DPoint(nPointCount - 1L)); 2965 B2DPoint aCurrent(rCandidate.getB2DPoint(0L)); 2966 2967 for(sal_uInt32 a(0L); a < nPointCount; a++) 2968 { 2969 const B2DPoint aNext(rCandidate.getB2DPoint(a + 1L == nPointCount ? 0L : a + 1L)); 2970 const B2DVector aBack(aPrev - aCurrent); 2971 const B2DVector aForw(aNext - aCurrent); 2972 const B2DVector aPerpBack(getNormalizedPerpendicular(aBack)); 2973 const B2DVector aPerpForw(getNormalizedPerpendicular(aForw)); 2974 B2DVector aDirection(aPerpBack - aPerpForw); 2975 aDirection.normalize(); 2976 aDirection *= fValue; 2977 aRetval.append(aCurrent + aDirection); 2978 2979 // prepare next step 2980 aPrev = aCurrent; 2981 aCurrent = aNext; 2982 } 2983 } 2984 2985 // copy closed state 2986 aRetval.setClosed(rCandidate.isClosed()); 2987 2988 return aRetval; 2989 } 2990 } 2991 else 2992 { 2993 return rCandidate; 2994 } 2995 } 2996 2997 B2DPolygon reSegmentPolygon(const B2DPolygon& rCandidate, sal_uInt32 nSegments) 2998 { 2999 B2DPolygon aRetval; 3000 const sal_uInt32 nPointCount(rCandidate.count()); 3001 3002 if(nPointCount && nSegments) 3003 { 3004 // get current segment count 3005 const sal_uInt32 nSegmentCount(rCandidate.isClosed() ? nPointCount : nPointCount - 1L); 3006 3007 if(nSegmentCount == nSegments) 3008 { 3009 aRetval = rCandidate; 3010 } 3011 else 3012 { 3013 const double fLength(getLength(rCandidate)); 3014 const sal_uInt32 nLoopCount(rCandidate.isClosed() ? nSegments : nSegments + 1L); 3015 3016 for(sal_uInt32 a(0L); a < nLoopCount; a++) 3017 { 3018 const double fRelativePos((double)a / (double)nSegments); // 0.0 .. 1.0 3019 const B2DPoint aNewPoint(getPositionRelative(rCandidate, fRelativePos, fLength)); 3020 aRetval.append(aNewPoint); 3021 } 3022 3023 // copy closed flag 3024 aRetval.setClosed(rCandidate.isClosed()); 3025 } 3026 } 3027 3028 return aRetval; 3029 } 3030 3031 B2DPolygon reSegmentPolygonEdges(const B2DPolygon& rCandidate, sal_uInt32 nSubEdges, bool bHandleCurvedEdges, bool bHandleStraightEdges) 3032 { 3033 const sal_uInt32 nPointCount(rCandidate.count()); 3034 3035 if(nPointCount < 2 || nSubEdges < 2 || (!bHandleCurvedEdges && !bHandleStraightEdges)) 3036 { 3037 // nothing to do: 3038 // - less than two points -> no edge at all 3039 // - less than two nSubEdges -> no resegment necessary 3040 // - neither bHandleCurvedEdges nor bHandleStraightEdges -> nothing to do 3041 return rCandidate; 3042 } 3043 else 3044 { 3045 B2DPolygon aRetval; 3046 const sal_uInt32 nEdgeCount(rCandidate.isClosed() ? nPointCount : nPointCount - 1); 3047 B2DCubicBezier aCurrentEdge; 3048 3049 // prepare first edge and add start point to target 3050 aCurrentEdge.setStartPoint(rCandidate.getB2DPoint(0)); 3051 aRetval.append(aCurrentEdge.getStartPoint()); 3052 3053 for(sal_uInt32 a(0); a < nEdgeCount; a++) 3054 { 3055 // fill edge 3056 const sal_uInt32 nNextIndex((a + 1) % nPointCount); 3057 aCurrentEdge.setControlPointA(rCandidate.getNextControlPoint(a)); 3058 aCurrentEdge.setControlPointB(rCandidate.getPrevControlPoint(nNextIndex)); 3059 aCurrentEdge.setEndPoint(rCandidate.getB2DPoint(nNextIndex)); 3060 3061 if(aCurrentEdge.isBezier()) 3062 { 3063 if(bHandleCurvedEdges) 3064 { 3065 for(sal_uInt32 b(nSubEdges); b > 1; b--) 3066 { 3067 const double fSplitPoint(1.0 / b); 3068 B2DCubicBezier aLeftPart; 3069 3070 aCurrentEdge.split(fSplitPoint, &aLeftPart, &aCurrentEdge); 3071 aRetval.appendBezierSegment(aLeftPart.getControlPointA(), aLeftPart.getControlPointB(), aLeftPart.getEndPoint()); 3072 } 3073 } 3074 3075 // copy remaining segment to target 3076 aRetval.appendBezierSegment(aCurrentEdge.getControlPointA(), aCurrentEdge.getControlPointB(), aCurrentEdge.getEndPoint()); 3077 } 3078 else 3079 { 3080 if(bHandleStraightEdges) 3081 { 3082 for(sal_uInt32 b(nSubEdges); b > 1; b--) 3083 { 3084 const double fSplitPoint(1.0 / b); 3085 const B2DPoint aSplitPoint(interpolate(aCurrentEdge.getStartPoint(), aCurrentEdge.getEndPoint(), fSplitPoint)); 3086 3087 aRetval.append(aSplitPoint); 3088 aCurrentEdge.setStartPoint(aSplitPoint); 3089 } 3090 } 3091 3092 // copy remaining segment to target 3093 aRetval.append(aCurrentEdge.getEndPoint()); 3094 } 3095 3096 // prepare next step 3097 aCurrentEdge.setStartPoint(aCurrentEdge.getEndPoint()); 3098 } 3099 3100 // copy closed flag and return 3101 aRetval.setClosed(rCandidate.isClosed()); 3102 return aRetval; 3103 } 3104 } 3105 3106 B2DPolygon interpolate(const B2DPolygon& rOld1, const B2DPolygon& rOld2, double t) 3107 { 3108 OSL_ENSURE(rOld1.count() == rOld2.count(), "B2DPolygon interpolate: Different geometry (!)"); 3109 3110 if(fTools::lessOrEqual(t, 0.0) || rOld1 == rOld2) 3111 { 3112 return rOld1; 3113 } 3114 else if(fTools::moreOrEqual(t, 1.0)) 3115 { 3116 return rOld2; 3117 } 3118 else 3119 { 3120 B2DPolygon aRetval; 3121 const bool bInterpolateVectors(rOld1.areControlPointsUsed() || rOld2.areControlPointsUsed()); 3122 aRetval.setClosed(rOld1.isClosed() && rOld2.isClosed()); 3123 3124 for(sal_uInt32 a(0L); a < rOld1.count(); a++) 3125 { 3126 aRetval.append(interpolate(rOld1.getB2DPoint(a), rOld2.getB2DPoint(a), t)); 3127 3128 if(bInterpolateVectors) 3129 { 3130 aRetval.setPrevControlPoint(a, interpolate(rOld1.getPrevControlPoint(a), rOld2.getPrevControlPoint(a), t)); 3131 aRetval.setNextControlPoint(a, interpolate(rOld1.getNextControlPoint(a), rOld2.getNextControlPoint(a), t)); 3132 } 3133 } 3134 3135 return aRetval; 3136 } 3137 } 3138 3139 bool isPolyPolygonEqualRectangle( const B2DPolyPolygon& rPolyPoly, 3140 const B2DRange& rRect ) 3141 { 3142 // exclude some cheap cases first 3143 if( rPolyPoly.count() != 1 ) 3144 return false; 3145 3146 // fill array with rectangle vertices 3147 const B2DPoint aPoints[] = 3148 { 3149 B2DPoint(rRect.getMinX(),rRect.getMinY()), 3150 B2DPoint(rRect.getMaxX(),rRect.getMinY()), 3151 B2DPoint(rRect.getMaxX(),rRect.getMaxY()), 3152 B2DPoint(rRect.getMinX(),rRect.getMaxY()) 3153 }; 3154 3155 const B2DPolygon& rPoly( rPolyPoly.getB2DPolygon(0) ); 3156 const sal_uInt32 nCount( rPoly.count() ); 3157 const double epsilon = ::std::numeric_limits<double>::epsilon(); 3158 3159 for(unsigned int j=0; j<4; ++j) 3160 { 3161 const B2DPoint &p1 = aPoints[j]; 3162 const B2DPoint &p2 = aPoints[(j+1)%4]; 3163 bool bPointOnBoundary = false; 3164 for( sal_uInt32 i=0; i<nCount; ++i ) 3165 { 3166 const B2DPoint p(rPoly.getB2DPoint(i)); 3167 3168 // 1 | x0 y0 1 | 3169 // A = - | x1 y1 1 | 3170 // 2 | x2 y2 1 | 3171 double fDoubleArea = p2.getX()*p.getY() - 3172 p2.getY()*p.getX() - 3173 p1.getX()*p.getY() + 3174 p1.getY()*p.getX() + 3175 p1.getX()*p2.getY() - 3176 p1.getY()*p2.getX(); 3177 3178 if(fDoubleArea < epsilon) 3179 { 3180 bPointOnBoundary=true; 3181 break; 3182 } 3183 } 3184 if(!(bPointOnBoundary)) 3185 return false; 3186 } 3187 3188 return true; 3189 } 3190 3191 3192 // create simplified version of the original polygon by 3193 // replacing segments with spikes/loops and self intersections 3194 // by several trivial sub-segments 3195 B2DPolygon createSimplifiedPolygon( const B2DPolygon& rCandidate ) 3196 { 3197 const sal_uInt32 nCount(rCandidate.count()); 3198 3199 if(nCount && rCandidate.areControlPointsUsed()) 3200 { 3201 const sal_uInt32 nEdgeCount(rCandidate.isClosed() ? nCount : nCount - 1); 3202 B2DPolygon aRetval; 3203 B2DCubicBezier aSegment; 3204 3205 aSegment.setStartPoint(rCandidate.getB2DPoint(0)); 3206 aRetval.append(aSegment.getStartPoint()); 3207 3208 for(sal_uInt32 a(0); a < nEdgeCount; a++) 3209 { 3210 // fill edge 3211 const sal_uInt32 nNextIndex((a + 1) % nCount); 3212 aSegment.setControlPointA(rCandidate.getNextControlPoint(a)); 3213 aSegment.setControlPointB(rCandidate.getPrevControlPoint(nNextIndex)); 3214 aSegment.setEndPoint(rCandidate.getB2DPoint(nNextIndex)); 3215 3216 if(aSegment.isBezier()) 3217 { 3218 double fExtremumPos(0.0); 3219 sal_uInt32 nExtremumCounter(4); 3220 3221 while(nExtremumCounter-- && aSegment.isBezier() && aSegment.getMinimumExtremumPosition(fExtremumPos)) 3222 { 3223 // split off left, now extremum-free part and append 3224 B2DCubicBezier aLeft; 3225 3226 aSegment.split(fExtremumPos, &aLeft, &aSegment); 3227 aLeft.testAndSolveTrivialBezier(); 3228 aSegment.testAndSolveTrivialBezier(); 3229 3230 if(aLeft.isBezier()) 3231 { 3232 aRetval.appendBezierSegment(aLeft.getControlPointA(), aLeft.getControlPointB(), aLeft.getEndPoint()); 3233 } 3234 else 3235 { 3236 aRetval.append(aLeft.getEndPoint()); 3237 } 3238 } 3239 3240 // append (evtl. reduced) rest of Segment 3241 if(aSegment.isBezier()) 3242 { 3243 aRetval.appendBezierSegment(aSegment.getControlPointA(), aSegment.getControlPointB(), aSegment.getEndPoint()); 3244 } 3245 else 3246 { 3247 aRetval.append(aSegment.getEndPoint()); 3248 } 3249 } 3250 else 3251 { 3252 // simple edge, append end point 3253 aRetval.append(aSegment.getEndPoint()); 3254 } 3255 3256 // prepare next edge 3257 aSegment.setStartPoint(aSegment.getEndPoint()); 3258 } 3259 3260 // copy closed flag and check for double points 3261 aRetval.setClosed(rCandidate.isClosed()); 3262 aRetval.removeDoublePoints(); 3263 3264 return aRetval; 3265 } 3266 else 3267 { 3268 return rCandidate; 3269 } 3270 } 3271 3272 // #i76891# 3273 B2DPolygon simplifyCurveSegments(const B2DPolygon& rCandidate) 3274 { 3275 const sal_uInt32 nPointCount(rCandidate.count()); 3276 3277 if(nPointCount && rCandidate.areControlPointsUsed()) 3278 { 3279 // prepare loop 3280 const sal_uInt32 nEdgeCount(rCandidate.isClosed() ? nPointCount : nPointCount - 1); 3281 B2DPolygon aRetval; 3282 B2DCubicBezier aBezier; 3283 aBezier.setStartPoint(rCandidate.getB2DPoint(0)); 3284 3285 // try to avoid costly reallocations 3286 aRetval.reserve( nEdgeCount+1); 3287 3288 // add start point 3289 aRetval.append(aBezier.getStartPoint()); 3290 3291 for(sal_uInt32 a(0L); a < nEdgeCount; a++) 3292 { 3293 // get values for edge 3294 const sal_uInt32 nNextIndex((a + 1) % nPointCount); 3295 aBezier.setEndPoint(rCandidate.getB2DPoint(nNextIndex)); 3296 aBezier.setControlPointA(rCandidate.getNextControlPoint(a)); 3297 aBezier.setControlPointB(rCandidate.getPrevControlPoint(nNextIndex)); 3298 aBezier.testAndSolveTrivialBezier(); 3299 3300 // still bezier? 3301 if(aBezier.isBezier()) 3302 { 3303 // add edge with control vectors 3304 aRetval.appendBezierSegment(aBezier.getControlPointA(), aBezier.getControlPointB(), aBezier.getEndPoint()); 3305 } 3306 else 3307 { 3308 // add edge 3309 aRetval.append(aBezier.getEndPoint()); 3310 } 3311 3312 // next point 3313 aBezier.setStartPoint(aBezier.getEndPoint()); 3314 } 3315 3316 if(rCandidate.isClosed()) 3317 { 3318 // set closed flag, rescue control point and correct last double point 3319 closeWithGeometryChange(aRetval); 3320 } 3321 3322 return aRetval; 3323 } 3324 else 3325 { 3326 return rCandidate; 3327 } 3328 } 3329 3330 // makes the given indexed point the new polygon start point. To do that, the points in the 3331 // polygon will be rotated. This is only valid for closed polygons, for non-closed ones 3332 // an assertion will be triggered 3333 B2DPolygon makeStartPoint(const B2DPolygon& rCandidate, sal_uInt32 nIndexOfNewStatPoint) 3334 { 3335 const sal_uInt32 nPointCount(rCandidate.count()); 3336 3337 if(nPointCount > 2 && nIndexOfNewStatPoint != 0 && nIndexOfNewStatPoint < nPointCount) 3338 { 3339 OSL_ENSURE(rCandidate.isClosed(), "makeStartPoint: only valid for closed polygons (!)"); 3340 B2DPolygon aRetval; 3341 3342 for(sal_uInt32 a(0); a < nPointCount; a++) 3343 { 3344 const sal_uInt32 nSourceIndex((a + nIndexOfNewStatPoint) % nPointCount); 3345 aRetval.append(rCandidate.getB2DPoint(nSourceIndex)); 3346 3347 if(rCandidate.areControlPointsUsed()) 3348 { 3349 aRetval.setPrevControlPoint(a, rCandidate.getPrevControlPoint(nSourceIndex)); 3350 aRetval.setNextControlPoint(a, rCandidate.getNextControlPoint(nSourceIndex)); 3351 } 3352 } 3353 3354 return aRetval; 3355 } 3356 3357 return rCandidate; 3358 } 3359 3360 B2DPolygon createEdgesOfGivenLength(const B2DPolygon& rCandidate, double fLength, double fStart, double fEnd) 3361 { 3362 B2DPolygon aRetval; 3363 3364 if(fLength < 0.0) 3365 { 3366 fLength = 0.0; 3367 } 3368 3369 if(!fTools::equalZero(fLength)) 3370 { 3371 if(fStart < 0.0) 3372 { 3373 fStart = 0.0; 3374 } 3375 3376 if(fEnd < 0.0) 3377 { 3378 fEnd = 0.0; 3379 } 3380 3381 if(fEnd < fStart) 3382 { 3383 fEnd = fStart; 3384 } 3385 3386 // iterate and consume pieces with fLength. First subdivide to reduce input to line segments 3387 const B2DPolygon aCandidate(rCandidate.areControlPointsUsed() ? rCandidate.getDefaultAdaptiveSubdivision() : rCandidate); 3388 const sal_uInt32 nPointCount(aCandidate.count()); 3389 3390 if(nPointCount > 1) 3391 { 3392 const bool bEndActive(!fTools::equalZero(fEnd)); 3393 const sal_uInt32 nEdgeCount(aCandidate.isClosed() ? nPointCount : nPointCount - 1); 3394 B2DPoint aCurrent(aCandidate.getB2DPoint(0)); 3395 double fPositionInEdge(fStart); 3396 double fAbsolutePosition(fStart); 3397 3398 for(sal_uInt32 a(0); a < nEdgeCount; a++) 3399 { 3400 const sal_uInt32 nNextIndex((a + 1) % nPointCount); 3401 const B2DPoint aNext(aCandidate.getB2DPoint(nNextIndex)); 3402 const B2DVector aEdge(aNext - aCurrent); 3403 double fEdgeLength(aEdge.getLength()); 3404 3405 if(!fTools::equalZero(fEdgeLength)) 3406 { 3407 while(fTools::less(fPositionInEdge, fEdgeLength)) 3408 { 3409 // move position on edge forward as long as on edge 3410 const double fScalar(fPositionInEdge / fEdgeLength); 3411 aRetval.append(aCurrent + (aEdge * fScalar)); 3412 fPositionInEdge += fLength; 3413 3414 if(bEndActive) 3415 { 3416 fAbsolutePosition += fLength; 3417 3418 if(fTools::more(fAbsolutePosition, fEnd)) 3419 { 3420 break; 3421 } 3422 } 3423 } 3424 3425 // substract length of current edge 3426 fPositionInEdge -= fEdgeLength; 3427 } 3428 3429 if(bEndActive && fTools::more(fAbsolutePosition, fEnd)) 3430 { 3431 break; 3432 } 3433 3434 // prepare next step 3435 aCurrent = aNext; 3436 } 3437 3438 // keep closed state 3439 aRetval.setClosed(aCandidate.isClosed()); 3440 } 3441 else 3442 { 3443 // source polygon has only one point, return unchanged 3444 aRetval = aCandidate; 3445 } 3446 } 3447 3448 return aRetval; 3449 } 3450 3451 B2DPolygon createWaveline(const B2DPolygon& rCandidate, double fWaveWidth, double fWaveHeight) 3452 { 3453 B2DPolygon aRetval; 3454 3455 if(fWaveWidth < 0.0) 3456 { 3457 fWaveWidth = 0.0; 3458 } 3459 3460 if(fWaveHeight < 0.0) 3461 { 3462 fWaveHeight = 0.0; 3463 } 3464 3465 const bool bHasWidth(!fTools::equalZero(fWaveWidth)); 3466 const bool bHasHeight(!fTools::equalZero(fWaveHeight)); 3467 3468 if(bHasWidth) 3469 { 3470 if(bHasHeight) 3471 { 3472 // width and height, create waveline. First subdivide to reduce input to line segments 3473 // of WaveWidth. Last segment may be missing. If this turns out to be a problem, it 3474 // may be added here again using the original last point from rCandidate. It may 3475 // also be the case that rCandidate was closed. To simplify things it is handled here 3476 // as if it was opened. 3477 // Result from createEdgesOfGivenLength contains no curved segments, handle as straight 3478 // edges. 3479 const B2DPolygon aEqualLenghEdges(createEdgesOfGivenLength(rCandidate, fWaveWidth)); 3480 const sal_uInt32 nPointCount(aEqualLenghEdges.count()); 3481 3482 if(nPointCount > 1) 3483 { 3484 // iterate over straight edges, add start point 3485 B2DPoint aCurrent(aEqualLenghEdges.getB2DPoint(0)); 3486 aRetval.append(aCurrent); 3487 3488 for(sal_uInt32 a(0); a < nPointCount - 1; a++) 3489 { 3490 const sal_uInt32 nNextIndex((a + 1) % nPointCount); 3491 const B2DPoint aNext(aEqualLenghEdges.getB2DPoint(nNextIndex)); 3492 const B2DVector aEdge(aNext - aCurrent); 3493 const B2DVector aPerpendicular(getNormalizedPerpendicular(aEdge)); 3494 const B2DVector aControlOffset((aEdge * 0.467308) - (aPerpendicular * fWaveHeight)); 3495 3496 // add curve segment 3497 aRetval.appendBezierSegment( 3498 aCurrent + aControlOffset, 3499 aNext - aControlOffset, 3500 aNext); 3501 3502 // prepare next step 3503 aCurrent = aNext; 3504 } 3505 } 3506 } 3507 else 3508 { 3509 // width but no height -> return original polygon 3510 aRetval = rCandidate; 3511 } 3512 } 3513 else 3514 { 3515 // no width -> no waveline, stay empty and return 3516 } 3517 3518 return aRetval; 3519 } 3520 3521 ////////////////////////////////////////////////////////////////////// 3522 // comparators with tolerance for 2D Polygons 3523 3524 bool equal(const B2DPolygon& rCandidateA, const B2DPolygon& rCandidateB, const double& rfSmallValue) 3525 { 3526 const sal_uInt32 nPointCount(rCandidateA.count()); 3527 3528 if(nPointCount != rCandidateB.count()) 3529 return false; 3530 3531 const bool bClosed(rCandidateA.isClosed()); 3532 3533 if(bClosed != rCandidateB.isClosed()) 3534 return false; 3535 3536 const bool bAreControlPointsUsed(rCandidateA.areControlPointsUsed()); 3537 3538 if(bAreControlPointsUsed != rCandidateB.areControlPointsUsed()) 3539 return false; 3540 3541 for(sal_uInt32 a(0); a < nPointCount; a++) 3542 { 3543 const B2DPoint aPoint(rCandidateA.getB2DPoint(a)); 3544 3545 if(!aPoint.equal(rCandidateB.getB2DPoint(a), rfSmallValue)) 3546 return false; 3547 3548 if(bAreControlPointsUsed) 3549 { 3550 const basegfx::B2DPoint aPrev(rCandidateA.getPrevControlPoint(a)); 3551 3552 if(!aPrev.equal(rCandidateB.getPrevControlPoint(a), rfSmallValue)) 3553 return false; 3554 3555 const basegfx::B2DPoint aNext(rCandidateA.getNextControlPoint(a)); 3556 3557 if(!aNext.equal(rCandidateB.getNextControlPoint(a), rfSmallValue)) 3558 return false; 3559 } 3560 } 3561 3562 return true; 3563 } 3564 3565 bool equal(const B2DPolygon& rCandidateA, const B2DPolygon& rCandidateB) 3566 { 3567 const double fSmallValue(fTools::getSmallValue()); 3568 3569 return equal(rCandidateA, rCandidateB, fSmallValue); 3570 } 3571 3572 // snap points of horizontal or vertical edges to discrete values 3573 B2DPolygon snapPointsOfHorizontalOrVerticalEdges(const B2DPolygon& rCandidate) 3574 { 3575 const sal_uInt32 nPointCount(rCandidate.count()); 3576 3577 if(nPointCount > 1) 3578 { 3579 // Start by copying the source polygon to get a writeable copy. The closed state is 3580 // copied by aRetval's initialisation, too, so no need to copy it in this method 3581 B2DPolygon aRetval(rCandidate); 3582 3583 // prepare geometry data. Get rounded from original 3584 B2ITuple aPrevTuple(basegfx::fround(rCandidate.getB2DPoint(nPointCount - 1))); 3585 B2DPoint aCurrPoint(rCandidate.getB2DPoint(0)); 3586 B2ITuple aCurrTuple(basegfx::fround(aCurrPoint)); 3587 3588 // loop over all points. This will also snap the implicit closing edge 3589 // even when not closed, but that's no problem here 3590 for(sal_uInt32 a(0); a < nPointCount; a++) 3591 { 3592 // get next point. Get rounded from original 3593 const bool bLastRun(a + 1 == nPointCount); 3594 const sal_uInt32 nNextIndex(bLastRun ? 0 : a + 1); 3595 const B2DPoint aNextPoint(rCandidate.getB2DPoint(nNextIndex)); 3596 const B2ITuple aNextTuple(basegfx::fround(aNextPoint)); 3597 3598 // get the states 3599 const bool bPrevVertical(aPrevTuple.getX() == aCurrTuple.getX()); 3600 const bool bNextVertical(aNextTuple.getX() == aCurrTuple.getX()); 3601 const bool bPrevHorizontal(aPrevTuple.getY() == aCurrTuple.getY()); 3602 const bool bNextHorizontal(aNextTuple.getY() == aCurrTuple.getY()); 3603 const bool bSnapX(bPrevVertical || bNextVertical); 3604 const bool bSnapY(bPrevHorizontal || bNextHorizontal); 3605 3606 if(bSnapX || bSnapY) 3607 { 3608 const B2DPoint aSnappedPoint( 3609 bSnapX ? aCurrTuple.getX() : aCurrPoint.getX(), 3610 bSnapY ? aCurrTuple.getY() : aCurrPoint.getY()); 3611 3612 aRetval.setB2DPoint(a, aSnappedPoint); 3613 } 3614 3615 // prepare next point 3616 if(!bLastRun) 3617 { 3618 aPrevTuple = aCurrTuple; 3619 aCurrPoint = aNextPoint; 3620 aCurrTuple = aNextTuple; 3621 } 3622 } 3623 3624 return aRetval; 3625 } 3626 else 3627 { 3628 return rCandidate; 3629 } 3630 } 3631 3632 } // end of namespace tools 3633 } // end of namespace basegfx 3634 3635 ////////////////////////////////////////////////////////////////////////////// 3636 // eof 3637