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 { openWithGeometryChange(B2DPolygon & rCandidate)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 closeWithGeometryChange(B2DPolygon & rCandidate)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 checkClosed(B2DPolygon & rCandidate)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. getIndexOfPredecessor(sal_uInt32 nIndex,const B2DPolygon & rCandidate)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 getIndexOfSuccessor(sal_uInt32 nIndex,const B2DPolygon & rCandidate)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 getOrientation(const B2DPolygon & rCandidate)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 getContinuityInPoint(const B2DPolygon & rCandidate,sal_uInt32 nIndex)171 B2VectorContinuity getContinuityInPoint(const B2DPolygon& rCandidate, sal_uInt32 nIndex) 172 { 173 return rCandidate.getContinuityInPoint(nIndex); 174 } 175 adaptiveSubdivideByDistance(const B2DPolygon & rCandidate,double fDistanceBound)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 adaptiveSubdivideByAngle(const B2DPolygon & rCandidate,double fAngleBound)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 adaptiveSubdivideByCount(const B2DPolygon & rCandidate,sal_uInt32 nCount)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 isInside(const B2DPolygon & rCandidate,const B2DPoint & rPoint,bool bWithBorder)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 isInside(const B2DPolygon & rCandidate,const B2DPolygon & rPolygon,bool bWithBorder)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 getRangeWithControlPoints(const B2DPolygon & rCandidate)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 getRange(const B2DPolygon & rCandidate)499 B2DRange getRange(const B2DPolygon& rCandidate) 500 { 501 // changed to use internally buffered version at B2DPolygon 502 return rCandidate.getB2DRange(); 503 } 504 getSignedArea(const B2DPolygon & rCandidate)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 // correct to zero if small enough. Also test the quadratic 523 // of the result since the precision is near quadratic due to 524 // the algorithm 525 if(fTools::equalZero(fRetval) || fTools::equalZero(fRetval * fRetval)) 526 { 527 fRetval = 0.0; 528 } 529 } 530 531 return fRetval; 532 } 533 getArea(const B2DPolygon & rCandidate)534 double getArea(const B2DPolygon& rCandidate) 535 { 536 double fRetval(0.0); 537 538 if(rCandidate.count() > 2 || rCandidate.areControlPointsUsed()) 539 { 540 fRetval = getSignedArea(rCandidate); 541 const double fZero(0.0); 542 543 if(fTools::less(fRetval, fZero)) 544 { 545 fRetval = -fRetval; 546 } 547 } 548 549 return fRetval; 550 } 551 getEdgeLength(const B2DPolygon & rCandidate,sal_uInt32 nIndex)552 double getEdgeLength(const B2DPolygon& rCandidate, sal_uInt32 nIndex) 553 { 554 const sal_uInt32 nPointCount(rCandidate.count()); 555 OSL_ENSURE(nIndex < nPointCount, "getEdgeLength: Access to polygon out of range (!)"); 556 double fRetval(0.0); 557 558 if(nPointCount) 559 { 560 const sal_uInt32 nNextIndex((nIndex + 1) % nPointCount); 561 562 if(rCandidate.areControlPointsUsed()) 563 { 564 B2DCubicBezier aEdge; 565 566 aEdge.setStartPoint(rCandidate.getB2DPoint(nIndex)); 567 aEdge.setControlPointA(rCandidate.getNextControlPoint(nIndex)); 568 aEdge.setControlPointB(rCandidate.getPrevControlPoint(nNextIndex)); 569 aEdge.setEndPoint(rCandidate.getB2DPoint(nNextIndex)); 570 571 fRetval = aEdge.getLength(); 572 } 573 else 574 { 575 const B2DPoint aCurrent(rCandidate.getB2DPoint(nIndex)); 576 const B2DPoint aNext(rCandidate.getB2DPoint(nNextIndex)); 577 578 fRetval = B2DVector(aNext - aCurrent).getLength(); 579 } 580 } 581 582 return fRetval; 583 } 584 getLength(const B2DPolygon & rCandidate)585 double getLength(const B2DPolygon& rCandidate) 586 { 587 double fRetval(0.0); 588 const sal_uInt32 nPointCount(rCandidate.count()); 589 590 if(nPointCount) 591 { 592 const sal_uInt32 nEdgeCount(rCandidate.isClosed() ? nPointCount : nPointCount - 1L); 593 594 if(rCandidate.areControlPointsUsed()) 595 { 596 B2DCubicBezier aEdge; 597 aEdge.setStartPoint(rCandidate.getB2DPoint(0)); 598 599 for(sal_uInt32 a(0); a < nEdgeCount; a++) 600 { 601 const sal_uInt32 nNextIndex((a + 1) % nPointCount); 602 aEdge.setControlPointA(rCandidate.getNextControlPoint(a)); 603 aEdge.setControlPointB(rCandidate.getPrevControlPoint(nNextIndex)); 604 aEdge.setEndPoint(rCandidate.getB2DPoint(nNextIndex)); 605 606 fRetval += aEdge.getLength(); 607 aEdge.setStartPoint(aEdge.getEndPoint()); 608 } 609 } 610 else 611 { 612 B2DPoint aCurrent(rCandidate.getB2DPoint(0)); 613 614 for(sal_uInt32 a(0); a < nEdgeCount; a++) 615 { 616 const sal_uInt32 nNextIndex((a + 1) % nPointCount); 617 const B2DPoint aNext(rCandidate.getB2DPoint(nNextIndex)); 618 619 fRetval += B2DVector(aNext - aCurrent).getLength(); 620 aCurrent = aNext; 621 } 622 } 623 } 624 625 return fRetval; 626 } 627 getPositionAbsolute(const B2DPolygon & rCandidate,double fDistance,double fLength)628 B2DPoint getPositionAbsolute(const B2DPolygon& rCandidate, double fDistance, double fLength) 629 { 630 B2DPoint aRetval; 631 const sal_uInt32 nPointCount(rCandidate.count()); 632 633 if( 1L == nPointCount ) 634 { 635 // only one point (i.e. no edge) - simply take that point 636 aRetval = rCandidate.getB2DPoint(0); 637 } 638 else if(nPointCount > 1L) 639 { 640 const sal_uInt32 nEdgeCount(rCandidate.isClosed() ? nPointCount : nPointCount - 1); 641 sal_uInt32 nIndex(0L); 642 bool bIndexDone(false); 643 644 // get length if not given 645 if(fTools::equalZero(fLength)) 646 { 647 fLength = getLength(rCandidate); 648 } 649 650 if(fTools::less(fDistance, 0.0)) 651 { 652 // handle fDistance < 0.0 653 if(rCandidate.isClosed()) 654 { 655 // if fDistance < 0.0 increment with multiple of fLength 656 sal_uInt32 nCount(sal_uInt32(-fDistance / fLength)); 657 fDistance += double(nCount + 1L) * fLength; 658 } 659 else 660 { 661 // crop to polygon start 662 fDistance = 0.0; 663 bIndexDone = true; 664 } 665 } 666 else if(fTools::moreOrEqual(fDistance, fLength)) 667 { 668 // handle fDistance >= fLength 669 if(rCandidate.isClosed()) 670 { 671 // if fDistance >= fLength decrement with multiple of fLength 672 sal_uInt32 nCount(sal_uInt32(fDistance / fLength)); 673 fDistance -= (double)(nCount) * fLength; 674 } 675 else 676 { 677 // crop to polygon end 678 fDistance = 0.0; 679 nIndex = nEdgeCount; 680 bIndexDone = true; 681 } 682 } 683 684 // look for correct index. fDistance is now [0.0 .. fLength[ 685 double fEdgeLength(getEdgeLength(rCandidate, nIndex)); 686 687 while(!bIndexDone) 688 { 689 // edge found must be on the half-open range 690 // [0,fEdgeLength). 691 // Note that in theory, we cannot move beyond 692 // the last polygon point, since fDistance>=fLength 693 // is checked above. Unfortunately, with floating- 694 // point calculations, this case might happen. 695 // Handled by nIndex check below 696 if(nIndex < nEdgeCount && fTools::moreOrEqual(fDistance, fEdgeLength)) 697 { 698 // go to next edge 699 fDistance -= fEdgeLength; 700 fEdgeLength = getEdgeLength(rCandidate, ++nIndex); 701 } 702 else 703 { 704 // it's on this edge, stop 705 bIndexDone = true; 706 } 707 } 708 709 // get the point using nIndex 710 aRetval = rCandidate.getB2DPoint(nIndex); 711 712 // if fDistance != 0.0, move that length on the edge. The edge 713 // length is in fEdgeLength. 714 if(!fTools::equalZero(fDistance)) 715 { 716 if(fTools::moreOrEqual(fDistance, fEdgeLength)) 717 { 718 // end point of choosen edge 719 const sal_uInt32 nNextIndex((nIndex + 1) % nPointCount); 720 aRetval = rCandidate.getB2DPoint(nNextIndex); 721 } 722 else if(fTools::equalZero(fDistance)) 723 { 724 // start point of choosen edge 725 aRetval = aRetval; 726 } 727 else 728 { 729 // inside edge 730 const sal_uInt32 nNextIndex((nIndex + 1) % nPointCount); 731 const B2DPoint aNextPoint(rCandidate.getB2DPoint(nNextIndex)); 732 bool bDone(false); 733 734 // add calculated average value to the return value 735 if(rCandidate.areControlPointsUsed()) 736 { 737 // get as bezier segment 738 const B2DCubicBezier aBezierSegment( 739 aRetval, rCandidate.getNextControlPoint(nIndex), 740 rCandidate.getPrevControlPoint(nNextIndex), aNextPoint); 741 742 if(aBezierSegment.isBezier()) 743 { 744 // use B2DCubicBezierHelper to bridge the non-linear gap between 745 // length and bezier distances 746 const B2DCubicBezierHelper aBezierSegmentHelper(aBezierSegment); 747 const double fBezierDistance(aBezierSegmentHelper.distanceToRelative(fDistance)); 748 749 aRetval = aBezierSegment.interpolatePoint(fBezierDistance); 750 bDone = true; 751 } 752 } 753 754 if(!bDone) 755 { 756 const double fRelativeInEdge(fDistance / fEdgeLength); 757 aRetval = interpolate(aRetval, aNextPoint, fRelativeInEdge); 758 } 759 } 760 } 761 } 762 763 return aRetval; 764 } 765 getPositionRelative(const B2DPolygon & rCandidate,double fDistance,double fLength)766 B2DPoint getPositionRelative(const B2DPolygon& rCandidate, double fDistance, double fLength) 767 { 768 // get length if not given 769 if(fTools::equalZero(fLength)) 770 { 771 fLength = getLength(rCandidate); 772 } 773 774 // multiply fDistance with real length to get absolute position and 775 // use getPositionAbsolute 776 return getPositionAbsolute(rCandidate, fDistance * fLength, fLength); 777 } 778 getSnippetAbsolute(const B2DPolygon & rCandidate,double fFrom,double fTo,double fLength)779 B2DPolygon getSnippetAbsolute(const B2DPolygon& rCandidate, double fFrom, double fTo, double fLength) 780 { 781 const sal_uInt32 nPointCount(rCandidate.count()); 782 783 if(nPointCount) 784 { 785 // get length if not given 786 if(fTools::equalZero(fLength)) 787 { 788 fLength = getLength(rCandidate); 789 } 790 791 // test and correct fFrom 792 if(fTools::less(fFrom, 0.0)) 793 { 794 fFrom = 0.0; 795 } 796 797 // test and correct fTo 798 if(fTools::more(fTo, fLength)) 799 { 800 fTo = fLength; 801 } 802 803 // test and correct relationship of fFrom, fTo 804 if(fTools::more(fFrom, fTo)) 805 { 806 fFrom = fTo = (fFrom + fTo) / 2.0; 807 } 808 809 if(fTools::equalZero(fFrom) && fTools::equal(fTo, fLength)) 810 { 811 // no change, result is the whole polygon 812 return rCandidate; 813 } 814 else 815 { 816 B2DPolygon aRetval; 817 const sal_uInt32 nEdgeCount(rCandidate.isClosed() ? nPointCount : nPointCount - 1); 818 double fPositionOfStart(0.0); 819 bool bStartDone(false); 820 bool bEndDone(false); 821 822 for(sal_uInt32 a(0L); !(bStartDone && bEndDone) && a < nEdgeCount; a++) 823 { 824 const double fEdgeLength(getEdgeLength(rCandidate, a)); 825 826 if(!bStartDone) 827 { 828 if(fTools::equalZero(fFrom)) 829 { 830 aRetval.append(rCandidate.getB2DPoint(a)); 831 832 if(rCandidate.areControlPointsUsed()) 833 { 834 aRetval.setNextControlPoint(aRetval.count() - 1, rCandidate.getNextControlPoint(a)); 835 } 836 837 bStartDone = true; 838 } 839 else if(fTools::moreOrEqual(fFrom, fPositionOfStart) && fTools::less(fFrom, fPositionOfStart + fEdgeLength)) 840 { 841 // calculate and add start point 842 if(fTools::equalZero(fEdgeLength)) 843 { 844 aRetval.append(rCandidate.getB2DPoint(a)); 845 846 if(rCandidate.areControlPointsUsed()) 847 { 848 aRetval.setNextControlPoint(aRetval.count() - 1, rCandidate.getNextControlPoint(a)); 849 } 850 } 851 else 852 { 853 const sal_uInt32 nNextIndex((a + 1) % nPointCount); 854 const B2DPoint aStart(rCandidate.getB2DPoint(a)); 855 const B2DPoint aEnd(rCandidate.getB2DPoint(nNextIndex)); 856 bool bDone(false); 857 858 if(rCandidate.areControlPointsUsed()) 859 { 860 const B2DCubicBezier aBezierSegment( 861 aStart, rCandidate.getNextControlPoint(a), 862 rCandidate.getPrevControlPoint(nNextIndex), aEnd); 863 864 if(aBezierSegment.isBezier()) 865 { 866 // use B2DCubicBezierHelper to bridge the non-linear gap between 867 // length and bezier distances 868 const B2DCubicBezierHelper aBezierSegmentHelper(aBezierSegment); 869 const double fBezierDistance(aBezierSegmentHelper.distanceToRelative(fFrom - fPositionOfStart)); 870 B2DCubicBezier aRight; 871 872 aBezierSegment.split(fBezierDistance, 0, &aRight); 873 aRetval.append(aRight.getStartPoint()); 874 aRetval.setNextControlPoint(aRetval.count() - 1, aRight.getControlPointA()); 875 bDone = true; 876 } 877 } 878 879 if(!bDone) 880 { 881 const double fRelValue((fFrom - fPositionOfStart) / fEdgeLength); 882 aRetval.append(interpolate(aStart, aEnd, fRelValue)); 883 } 884 } 885 886 bStartDone = true; 887 888 // if same point, end is done, too. 889 if(fFrom == fTo) 890 { 891 bEndDone = true; 892 } 893 } 894 } 895 896 if(!bEndDone && fTools::moreOrEqual(fTo, fPositionOfStart) && fTools::less(fTo, fPositionOfStart + fEdgeLength)) 897 { 898 // calculate and add end point 899 if(fTools::equalZero(fEdgeLength)) 900 { 901 const sal_uInt32 nNextIndex((a + 1) % nPointCount); 902 aRetval.append(rCandidate.getB2DPoint(nNextIndex)); 903 904 if(rCandidate.areControlPointsUsed()) 905 { 906 aRetval.setPrevControlPoint(aRetval.count() - 1, rCandidate.getPrevControlPoint(nNextIndex)); 907 } 908 } 909 else 910 { 911 const sal_uInt32 nNextIndex((a + 1) % nPointCount); 912 const B2DPoint aStart(rCandidate.getB2DPoint(a)); 913 const B2DPoint aEnd(rCandidate.getB2DPoint(nNextIndex)); 914 bool bDone(false); 915 916 if(rCandidate.areControlPointsUsed()) 917 { 918 const B2DCubicBezier aBezierSegment( 919 aStart, rCandidate.getNextControlPoint(a), 920 rCandidate.getPrevControlPoint(nNextIndex), aEnd); 921 922 if(aBezierSegment.isBezier()) 923 { 924 // use B2DCubicBezierHelper to bridge the non-linear gap between 925 // length and bezier distances 926 const B2DCubicBezierHelper aBezierSegmentHelper(aBezierSegment); 927 const double fBezierDistance(aBezierSegmentHelper.distanceToRelative(fTo - fPositionOfStart)); 928 B2DCubicBezier aLeft; 929 930 aBezierSegment.split(fBezierDistance, &aLeft, 0); 931 aRetval.append(aLeft.getEndPoint()); 932 aRetval.setPrevControlPoint(aRetval.count() - 1, aLeft.getControlPointB()); 933 bDone = true; 934 } 935 } 936 937 if(!bDone) 938 { 939 const double fRelValue((fTo - fPositionOfStart) / fEdgeLength); 940 aRetval.append(interpolate(aStart, aEnd, fRelValue)); 941 } 942 } 943 944 bEndDone = true; 945 } 946 947 if(!bEndDone) 948 { 949 if(bStartDone) 950 { 951 // add segments end point 952 const sal_uInt32 nNextIndex((a + 1) % nPointCount); 953 aRetval.append(rCandidate.getB2DPoint(nNextIndex)); 954 955 if(rCandidate.areControlPointsUsed()) 956 { 957 aRetval.setPrevControlPoint(aRetval.count() - 1, rCandidate.getPrevControlPoint(nNextIndex)); 958 aRetval.setNextControlPoint(aRetval.count() - 1, rCandidate.getNextControlPoint(nNextIndex)); 959 } 960 } 961 962 // increment fPositionOfStart 963 fPositionOfStart += fEdgeLength; 964 } 965 } 966 return aRetval; 967 } 968 } 969 else 970 { 971 return rCandidate; 972 } 973 } 974 getSnippetRelative(const B2DPolygon & rCandidate,double fFrom,double fTo,double fLength)975 B2DPolygon getSnippetRelative(const B2DPolygon& rCandidate, double fFrom, double fTo, double fLength) 976 { 977 // get length if not given 978 if(fTools::equalZero(fLength)) 979 { 980 fLength = getLength(rCandidate); 981 } 982 983 // multiply distances with real length to get absolute position and 984 // use getSnippetAbsolute 985 return getSnippetAbsolute(rCandidate, fFrom * fLength, fTo * fLength, fLength); 986 } 987 findCut(const B2DPolygon & rCandidate,sal_uInt32 nIndex1,sal_uInt32 nIndex2,CutFlagValue aCutFlags,double * pCut1,double * pCut2)988 CutFlagValue findCut( 989 const B2DPolygon& rCandidate, 990 sal_uInt32 nIndex1, sal_uInt32 nIndex2, 991 CutFlagValue aCutFlags, 992 double* pCut1, double* pCut2) 993 { 994 CutFlagValue aRetval(CUTFLAG_NONE); 995 const sal_uInt32 nPointCount(rCandidate.count()); 996 997 if(nIndex1 < nPointCount && nIndex2 < nPointCount && nIndex1 != nIndex2) 998 { 999 sal_uInt32 nEnd1(getIndexOfSuccessor(nIndex1, rCandidate)); 1000 sal_uInt32 nEnd2(getIndexOfSuccessor(nIndex2, rCandidate)); 1001 1002 const B2DPoint aStart1(rCandidate.getB2DPoint(nIndex1)); 1003 const B2DPoint aEnd1(rCandidate.getB2DPoint(nEnd1)); 1004 const B2DVector aVector1(aEnd1 - aStart1); 1005 1006 const B2DPoint aStart2(rCandidate.getB2DPoint(nIndex2)); 1007 const B2DPoint aEnd2(rCandidate.getB2DPoint(nEnd2)); 1008 const B2DVector aVector2(aEnd2 - aStart2); 1009 1010 aRetval = findCut( 1011 aStart1, aVector1, aStart2, aVector2, 1012 aCutFlags, pCut1, pCut2); 1013 } 1014 1015 return aRetval; 1016 } 1017 findCut(const B2DPolygon & rCandidate1,sal_uInt32 nIndex1,const B2DPolygon & rCandidate2,sal_uInt32 nIndex2,CutFlagValue aCutFlags,double * pCut1,double * pCut2)1018 CutFlagValue findCut( 1019 const B2DPolygon& rCandidate1, sal_uInt32 nIndex1, 1020 const B2DPolygon& rCandidate2, sal_uInt32 nIndex2, 1021 CutFlagValue aCutFlags, 1022 double* pCut1, double* pCut2) 1023 { 1024 CutFlagValue aRetval(CUTFLAG_NONE); 1025 const sal_uInt32 nPointCount1(rCandidate1.count()); 1026 const sal_uInt32 nPointCount2(rCandidate2.count()); 1027 1028 if(nIndex1 < nPointCount1 && nIndex2 < nPointCount2) 1029 { 1030 sal_uInt32 nEnd1(getIndexOfSuccessor(nIndex1, rCandidate1)); 1031 sal_uInt32 nEnd2(getIndexOfSuccessor(nIndex2, rCandidate2)); 1032 1033 const B2DPoint aStart1(rCandidate1.getB2DPoint(nIndex1)); 1034 const B2DPoint aEnd1(rCandidate1.getB2DPoint(nEnd1)); 1035 const B2DVector aVector1(aEnd1 - aStart1); 1036 1037 const B2DPoint aStart2(rCandidate2.getB2DPoint(nIndex2)); 1038 const B2DPoint aEnd2(rCandidate2.getB2DPoint(nEnd2)); 1039 const B2DVector aVector2(aEnd2 - aStart2); 1040 1041 aRetval = findCut( 1042 aStart1, aVector1, aStart2, aVector2, 1043 aCutFlags, pCut1, pCut2); 1044 } 1045 1046 return aRetval; 1047 } 1048 findCut(const B2DPoint & rEdge1Start,const B2DVector & rEdge1Delta,const B2DPoint & rEdge2Start,const B2DVector & rEdge2Delta,CutFlagValue aCutFlags,double * pCut1,double * pCut2)1049 CutFlagValue findCut( 1050 const B2DPoint& rEdge1Start, const B2DVector& rEdge1Delta, 1051 const B2DPoint& rEdge2Start, const B2DVector& rEdge2Delta, 1052 CutFlagValue aCutFlags, 1053 double* pCut1, double* pCut2) 1054 { 1055 CutFlagValue aRetval(CUTFLAG_NONE); 1056 double fCut1(0.0); 1057 double fCut2(0.0); 1058 bool bFinished(!((bool)(aCutFlags & CUTFLAG_ALL))); 1059 1060 // test for same points? 1061 if(!bFinished 1062 && (aCutFlags & (CUTFLAG_START1|CUTFLAG_END1)) 1063 && (aCutFlags & (CUTFLAG_START2|CUTFLAG_END2))) 1064 { 1065 // same startpoint? 1066 if(!bFinished && (aCutFlags & (CUTFLAG_START1|CUTFLAG_START2)) == (CUTFLAG_START1|CUTFLAG_START2)) 1067 { 1068 if(rEdge1Start.equal(rEdge2Start)) 1069 { 1070 bFinished = true; 1071 aRetval = (CUTFLAG_START1|CUTFLAG_START2); 1072 } 1073 } 1074 1075 // same endpoint? 1076 if(!bFinished && (aCutFlags & (CUTFLAG_END1|CUTFLAG_END2)) == (CUTFLAG_END1|CUTFLAG_END2)) 1077 { 1078 const B2DPoint aEnd1(rEdge1Start + rEdge1Delta); 1079 const B2DPoint aEnd2(rEdge2Start + rEdge2Delta); 1080 1081 if(aEnd1.equal(aEnd2)) 1082 { 1083 bFinished = true; 1084 aRetval = (CUTFLAG_END1|CUTFLAG_END2); 1085 fCut1 = fCut2 = 1.0; 1086 } 1087 } 1088 1089 // startpoint1 == endpoint2? 1090 if(!bFinished && (aCutFlags & (CUTFLAG_START1|CUTFLAG_END2)) == (CUTFLAG_START1|CUTFLAG_END2)) 1091 { 1092 const B2DPoint aEnd2(rEdge2Start + rEdge2Delta); 1093 1094 if(rEdge1Start.equal(aEnd2)) 1095 { 1096 bFinished = true; 1097 aRetval = (CUTFLAG_START1|CUTFLAG_END2); 1098 fCut1 = 0.0; 1099 fCut2 = 1.0; 1100 } 1101 } 1102 1103 // startpoint2 == endpoint1? 1104 if(!bFinished&& (aCutFlags & (CUTFLAG_START2|CUTFLAG_END1)) == (CUTFLAG_START2|CUTFLAG_END1)) 1105 { 1106 const B2DPoint aEnd1(rEdge1Start + rEdge1Delta); 1107 1108 if(rEdge2Start.equal(aEnd1)) 1109 { 1110 bFinished = true; 1111 aRetval = (CUTFLAG_START2|CUTFLAG_END1); 1112 fCut1 = 1.0; 1113 fCut2 = 0.0; 1114 } 1115 } 1116 } 1117 1118 if(!bFinished && (aCutFlags & CUTFLAG_LINE)) 1119 { 1120 if(!bFinished && (aCutFlags & CUTFLAG_START1)) 1121 { 1122 // start1 on line 2 ? 1123 if(isPointOnEdge(rEdge1Start, rEdge2Start, rEdge2Delta, &fCut2)) 1124 { 1125 bFinished = true; 1126 aRetval = (CUTFLAG_LINE|CUTFLAG_START1); 1127 } 1128 } 1129 1130 if(!bFinished && (aCutFlags & CUTFLAG_START2)) 1131 { 1132 // start2 on line 1 ? 1133 if(isPointOnEdge(rEdge2Start, rEdge1Start, rEdge1Delta, &fCut1)) 1134 { 1135 bFinished = true; 1136 aRetval = (CUTFLAG_LINE|CUTFLAG_START2); 1137 } 1138 } 1139 1140 if(!bFinished && (aCutFlags & CUTFLAG_END1)) 1141 { 1142 // end1 on line 2 ? 1143 const B2DPoint aEnd1(rEdge1Start + rEdge1Delta); 1144 1145 if(isPointOnEdge(aEnd1, rEdge2Start, rEdge2Delta, &fCut2)) 1146 { 1147 bFinished = true; 1148 aRetval = (CUTFLAG_LINE|CUTFLAG_END1); 1149 } 1150 } 1151 1152 if(!bFinished && (aCutFlags & CUTFLAG_END2)) 1153 { 1154 // end2 on line 1 ? 1155 const B2DPoint aEnd2(rEdge2Start + rEdge2Delta); 1156 1157 if(isPointOnEdge(aEnd2, rEdge1Start, rEdge1Delta, &fCut1)) 1158 { 1159 bFinished = true; 1160 aRetval = (CUTFLAG_LINE|CUTFLAG_END2); 1161 } 1162 } 1163 1164 if(!bFinished) 1165 { 1166 // cut in line1, line2 ? 1167 fCut1 = (rEdge1Delta.getX() * rEdge2Delta.getY()) - (rEdge1Delta.getY() * rEdge2Delta.getX()); 1168 1169 if(!fTools::equalZero(fCut1)) 1170 { 1171 fCut1 = (rEdge2Delta.getY() * (rEdge2Start.getX() - rEdge1Start.getX()) 1172 + rEdge2Delta.getX() * (rEdge1Start.getY() - rEdge2Start.getY())) / fCut1; 1173 1174 const double fZero(0.0); 1175 const double fOne(1.0); 1176 1177 // inside parameter range edge1 AND fCut2 is calcable 1178 if(fTools::more(fCut1, fZero) && fTools::less(fCut1, fOne) 1179 && (!fTools::equalZero(rEdge2Delta.getX()) || !fTools::equalZero(rEdge2Delta.getY()))) 1180 { 1181 // take the mopre precise calculation of the two possible 1182 if(fabs(rEdge2Delta.getX()) > fabs(rEdge2Delta.getY())) 1183 { 1184 fCut2 = (rEdge1Start.getX() + fCut1 1185 * rEdge1Delta.getX() - rEdge2Start.getX()) / rEdge2Delta.getX(); 1186 } 1187 else 1188 { 1189 fCut2 = (rEdge1Start.getY() + fCut1 1190 * rEdge1Delta.getY() - rEdge2Start.getY()) / rEdge2Delta.getY(); 1191 } 1192 1193 // inside parameter range edge2, too 1194 if(fTools::more(fCut2, fZero) && fTools::less(fCut2, fOne)) 1195 { 1196 bFinished = true; 1197 aRetval = CUTFLAG_LINE; 1198 } 1199 } 1200 } 1201 } 1202 } 1203 1204 // copy values if wanted 1205 if(pCut1) 1206 { 1207 *pCut1 = fCut1; 1208 } 1209 1210 if(pCut2) 1211 { 1212 *pCut2 = fCut2; 1213 } 1214 1215 return aRetval; 1216 } 1217 isPointOnEdge(const B2DPoint & rPoint,const B2DPoint & rEdgeStart,const B2DVector & rEdgeDelta,double * pCut)1218 bool isPointOnEdge( 1219 const B2DPoint& rPoint, 1220 const B2DPoint& rEdgeStart, 1221 const B2DVector& rEdgeDelta, 1222 double* pCut) 1223 { 1224 bool bDeltaXIsZero(fTools::equalZero(rEdgeDelta.getX())); 1225 bool bDeltaYIsZero(fTools::equalZero(rEdgeDelta.getY())); 1226 const double fZero(0.0); 1227 const double fOne(1.0); 1228 1229 if(bDeltaXIsZero && bDeltaYIsZero) 1230 { 1231 // no line, just a point 1232 return false; 1233 } 1234 else if(bDeltaXIsZero) 1235 { 1236 // vertical line 1237 if(fTools::equal(rPoint.getX(), rEdgeStart.getX())) 1238 { 1239 double fValue = (rPoint.getY() - rEdgeStart.getY()) / rEdgeDelta.getY(); 1240 1241 if(fTools::more(fValue, fZero) && fTools::less(fValue, fOne)) 1242 { 1243 if(pCut) 1244 { 1245 *pCut = fValue; 1246 } 1247 1248 return true; 1249 } 1250 } 1251 } 1252 else if(bDeltaYIsZero) 1253 { 1254 // horizontal line 1255 if(fTools::equal(rPoint.getY(), rEdgeStart.getY())) 1256 { 1257 double fValue = (rPoint.getX() - rEdgeStart.getX()) / rEdgeDelta.getX(); 1258 1259 if(fTools::more(fValue, fZero) && fTools::less(fValue, fOne)) 1260 { 1261 if(pCut) 1262 { 1263 *pCut = fValue; 1264 } 1265 1266 return true; 1267 } 1268 } 1269 } 1270 else 1271 { 1272 // any angle line 1273 double fTOne = (rPoint.getX() - rEdgeStart.getX()) / rEdgeDelta.getX(); 1274 double fTTwo = (rPoint.getY() - rEdgeStart.getY()) / rEdgeDelta.getY(); 1275 1276 if(fTools::equal(fTOne, fTTwo)) 1277 { 1278 // same parameter representation, point is on line. Take 1279 // middle value for better results 1280 double fValue = (fTOne + fTTwo) / 2.0; 1281 1282 if(fTools::more(fValue, fZero) && fTools::less(fValue, fOne)) 1283 { 1284 // point is inside line bounds, too 1285 if(pCut) 1286 { 1287 *pCut = fValue; 1288 } 1289 1290 return true; 1291 } 1292 } 1293 } 1294 1295 return false; 1296 } 1297 applyLineDashing(const B2DPolygon & rCandidate,const::std::vector<double> & rDotDashArray,B2DPolyPolygon * pLineTarget,B2DPolyPolygon * pGapTarget,double fDotDashLength)1298 void applyLineDashing(const B2DPolygon& rCandidate, const ::std::vector<double>& rDotDashArray, B2DPolyPolygon* pLineTarget, B2DPolyPolygon* pGapTarget, double fDotDashLength) 1299 { 1300 const sal_uInt32 nPointCount(rCandidate.count()); 1301 const sal_uInt32 nDotDashCount(rDotDashArray.size()); 1302 1303 if(fTools::lessOrEqual(fDotDashLength, 0.0)) 1304 { 1305 fDotDashLength = ::std::accumulate(rDotDashArray.begin(), rDotDashArray.end(), 0.0); 1306 } 1307 1308 if(fTools::more(fDotDashLength, 0.0) && (pLineTarget || pGapTarget) && nPointCount) 1309 { 1310 // clear targets 1311 if(pLineTarget) 1312 { 1313 pLineTarget->clear(); 1314 } 1315 1316 if(pGapTarget) 1317 { 1318 pGapTarget->clear(); 1319 } 1320 1321 // prepare current edge's start 1322 B2DCubicBezier aCurrentEdge; 1323 const sal_uInt32 nEdgeCount(rCandidate.isClosed() ? nPointCount : nPointCount - 1); 1324 aCurrentEdge.setStartPoint(rCandidate.getB2DPoint(0)); 1325 1326 // prepare DotDashArray iteration and the line/gap switching bool 1327 sal_uInt32 nDotDashIndex(0); 1328 bool bIsLine(true); 1329 double fDotDashMovingLength(rDotDashArray[0]); 1330 B2DPolygon aSnippet; 1331 1332 // iterate over all edges 1333 for(sal_uInt32 a(0); a < nEdgeCount; a++) 1334 { 1335 // update current edge (fill in C1, C2 and end point) 1336 double fLastDotDashMovingLength(0.0); 1337 const sal_uInt32 nNextIndex((a + 1) % nPointCount); 1338 aCurrentEdge.setControlPointA(rCandidate.getNextControlPoint(a)); 1339 aCurrentEdge.setControlPointB(rCandidate.getPrevControlPoint(nNextIndex)); 1340 aCurrentEdge.setEndPoint(rCandidate.getB2DPoint(nNextIndex)); 1341 1342 // check if we have a trivial bezier segment -> possible fallback to edge 1343 aCurrentEdge.testAndSolveTrivialBezier(); 1344 1345 if(aCurrentEdge.isBezier()) 1346 { 1347 // bezier segment 1348 const B2DCubicBezierHelper aCubicBezierHelper(aCurrentEdge); 1349 const double fEdgeLength(aCubicBezierHelper.getLength()); 1350 1351 if(!fTools::equalZero(fEdgeLength)) 1352 { 1353 while(fTools::less(fDotDashMovingLength, fEdgeLength)) 1354 { 1355 // new split is inside edge, create and append snippet [fLastDotDashMovingLength, fDotDashMovingLength] 1356 const bool bHandleLine(bIsLine && pLineTarget); 1357 const bool bHandleGap(!bIsLine && pGapTarget); 1358 1359 if(bHandleLine || bHandleGap) 1360 { 1361 const double fBezierSplitStart(aCubicBezierHelper.distanceToRelative(fLastDotDashMovingLength)); 1362 const double fBezierSplitEnd(aCubicBezierHelper.distanceToRelative(fDotDashMovingLength)); 1363 B2DCubicBezier aBezierSnippet(aCurrentEdge.snippet(fBezierSplitStart, fBezierSplitEnd)); 1364 1365 if(!aSnippet.count()) 1366 { 1367 aSnippet.append(aBezierSnippet.getStartPoint()); 1368 } 1369 1370 aSnippet.appendBezierSegment(aBezierSnippet.getControlPointA(), aBezierSnippet.getControlPointB(), aBezierSnippet.getEndPoint()); 1371 1372 if(bHandleLine) 1373 { 1374 pLineTarget->append(aSnippet); 1375 } 1376 else 1377 { 1378 pGapTarget->append(aSnippet); 1379 } 1380 1381 aSnippet.clear(); 1382 } 1383 1384 // prepare next DotDashArray step and flip line/gap flag 1385 fLastDotDashMovingLength = fDotDashMovingLength; 1386 fDotDashMovingLength += rDotDashArray[(++nDotDashIndex) % nDotDashCount]; 1387 bIsLine = !bIsLine; 1388 } 1389 1390 // append closing snippet [fLastDotDashMovingLength, fEdgeLength] 1391 const bool bHandleLine(bIsLine && pLineTarget); 1392 const bool bHandleGap(!bIsLine && pGapTarget); 1393 1394 if(bHandleLine || bHandleGap) 1395 { 1396 B2DCubicBezier aRight; 1397 const double fBezierSplit(aCubicBezierHelper.distanceToRelative(fLastDotDashMovingLength)); 1398 1399 aCurrentEdge.split(fBezierSplit, 0, &aRight); 1400 1401 if(!aSnippet.count()) 1402 { 1403 aSnippet.append(aRight.getStartPoint()); 1404 } 1405 1406 aSnippet.appendBezierSegment(aRight.getControlPointA(), aRight.getControlPointB(), aRight.getEndPoint()); 1407 } 1408 1409 // prepare move to next edge 1410 fDotDashMovingLength -= fEdgeLength; 1411 } 1412 } 1413 else 1414 { 1415 // simple edge 1416 const double fEdgeLength(aCurrentEdge.getEdgeLength()); 1417 1418 if(!fTools::equalZero(fEdgeLength)) 1419 { 1420 while(fTools::less(fDotDashMovingLength, fEdgeLength)) 1421 { 1422 // new split is inside edge, create and append snippet [fLastDotDashMovingLength, fDotDashMovingLength] 1423 const bool bHandleLine(bIsLine && pLineTarget); 1424 const bool bHandleGap(!bIsLine && pGapTarget); 1425 1426 if(bHandleLine || bHandleGap) 1427 { 1428 if(!aSnippet.count()) 1429 { 1430 aSnippet.append(interpolate(aCurrentEdge.getStartPoint(), aCurrentEdge.getEndPoint(), fLastDotDashMovingLength / fEdgeLength)); 1431 } 1432 1433 aSnippet.append(interpolate(aCurrentEdge.getStartPoint(), aCurrentEdge.getEndPoint(), fDotDashMovingLength / fEdgeLength)); 1434 1435 if(bHandleLine) 1436 { 1437 pLineTarget->append(aSnippet); 1438 } 1439 else 1440 { 1441 pGapTarget->append(aSnippet); 1442 } 1443 1444 aSnippet.clear(); 1445 } 1446 1447 // prepare next DotDashArray step and flip line/gap flag 1448 fLastDotDashMovingLength = fDotDashMovingLength; 1449 fDotDashMovingLength += rDotDashArray[(++nDotDashIndex) % nDotDashCount]; 1450 bIsLine = !bIsLine; 1451 } 1452 1453 // append snippet [fLastDotDashMovingLength, fEdgeLength] 1454 const bool bHandleLine(bIsLine && pLineTarget); 1455 const bool bHandleGap(!bIsLine && pGapTarget); 1456 1457 if(bHandleLine || bHandleGap) 1458 { 1459 if(!aSnippet.count()) 1460 { 1461 aSnippet.append(interpolate(aCurrentEdge.getStartPoint(), aCurrentEdge.getEndPoint(), fLastDotDashMovingLength / fEdgeLength)); 1462 } 1463 1464 aSnippet.append(aCurrentEdge.getEndPoint()); 1465 } 1466 1467 // prepare move to next edge 1468 fDotDashMovingLength -= fEdgeLength; 1469 } 1470 } 1471 1472 // prepare next edge step (end point gets new start point) 1473 aCurrentEdge.setStartPoint(aCurrentEdge.getEndPoint()); 1474 } 1475 1476 // append last intermediate results (if exists) 1477 if(aSnippet.count()) 1478 { 1479 if(bIsLine && pLineTarget) 1480 { 1481 pLineTarget->append(aSnippet); 1482 } 1483 else if(!bIsLine && pGapTarget) 1484 { 1485 pGapTarget->append(aSnippet); 1486 } 1487 } 1488 1489 // check if start and end polygon may be merged 1490 if(pLineTarget) 1491 { 1492 const sal_uInt32 nCount(pLineTarget->count()); 1493 1494 if(nCount > 1) 1495 { 1496 // these polygons were created above, there exists none with less than two points, 1497 // thus dircet point access below is allowed 1498 const B2DPolygon aFirst(pLineTarget->getB2DPolygon(0)); 1499 B2DPolygon aLast(pLineTarget->getB2DPolygon(nCount - 1)); 1500 1501 if(aFirst.getB2DPoint(0).equal(aLast.getB2DPoint(aLast.count() - 1))) 1502 { 1503 // start of first and end of last are the same -> merge them 1504 aLast.append(aFirst); 1505 aLast.removeDoublePoints(); 1506 pLineTarget->setB2DPolygon(0, aLast); 1507 pLineTarget->remove(nCount - 1); 1508 } 1509 } 1510 } 1511 1512 if(pGapTarget) 1513 { 1514 const sal_uInt32 nCount(pGapTarget->count()); 1515 1516 if(nCount > 1) 1517 { 1518 // these polygons were created above, there exists none with less than two points, 1519 // thus dircet point access below is allowed 1520 const B2DPolygon aFirst(pGapTarget->getB2DPolygon(0)); 1521 B2DPolygon aLast(pGapTarget->getB2DPolygon(nCount - 1)); 1522 1523 if(aFirst.getB2DPoint(0).equal(aLast.getB2DPoint(aLast.count() - 1))) 1524 { 1525 // start of first and end of last are the same -> merge them 1526 aLast.append(aFirst); 1527 aLast.removeDoublePoints(); 1528 pGapTarget->setB2DPolygon(0, aLast); 1529 pGapTarget->remove(nCount - 1); 1530 } 1531 } 1532 } 1533 } 1534 else 1535 { 1536 // parameters make no sense, just add source to targets 1537 if(pLineTarget) 1538 { 1539 pLineTarget->append(rCandidate); 1540 } 1541 1542 if(pGapTarget) 1543 { 1544 pGapTarget->append(rCandidate); 1545 } 1546 } 1547 } 1548 1549 // test if point is inside epsilon-range around an edge defined 1550 // by the two given points. Can be used for HitTesting. The epsilon-range 1551 // is defined to be the rectangle centered to the given edge, using height 1552 // 2 x fDistance, and the circle around both points with radius fDistance. isInEpsilonRange(const B2DPoint & rEdgeStart,const B2DPoint & rEdgeEnd,const B2DPoint & rTestPosition,double fDistance)1553 bool isInEpsilonRange(const B2DPoint& rEdgeStart, const B2DPoint& rEdgeEnd, const B2DPoint& rTestPosition, double fDistance) 1554 { 1555 // build edge vector 1556 const B2DVector aEdge(rEdgeEnd - rEdgeStart); 1557 bool bDoDistanceTestStart(false); 1558 bool bDoDistanceTestEnd(false); 1559 1560 if(aEdge.equalZero()) 1561 { 1562 // no edge, just a point. Do one of the distance tests. 1563 bDoDistanceTestStart = true; 1564 } 1565 else 1566 { 1567 // edge has a length. Create perpendicular vector. 1568 const B2DVector aPerpend(getPerpendicular(aEdge)); 1569 double fCut( 1570 (aPerpend.getY() * (rTestPosition.getX() - rEdgeStart.getX()) 1571 + aPerpend.getX() * (rEdgeStart.getY() - rTestPosition.getY())) / 1572 (aEdge.getX() * aEdge.getX() + aEdge.getY() * aEdge.getY())); 1573 const double fZero(0.0); 1574 const double fOne(1.0); 1575 1576 if(fTools::less(fCut, fZero)) 1577 { 1578 // left of rEdgeStart 1579 bDoDistanceTestStart = true; 1580 } 1581 else if(fTools::more(fCut, fOne)) 1582 { 1583 // right of rEdgeEnd 1584 bDoDistanceTestEnd = true; 1585 } 1586 else 1587 { 1588 // inside line [0.0 .. 1.0] 1589 const B2DPoint aCutPoint(interpolate(rEdgeStart, rEdgeEnd, fCut)); 1590 const B2DVector aDelta(rTestPosition - aCutPoint); 1591 const double fDistanceSquare(aDelta.scalar(aDelta)); 1592 1593 if(fDistanceSquare <= fDistance * fDistance) 1594 { 1595 return true; 1596 } 1597 else 1598 { 1599 return false; 1600 } 1601 } 1602 } 1603 1604 if(bDoDistanceTestStart) 1605 { 1606 const B2DVector aDelta(rTestPosition - rEdgeStart); 1607 const double fDistanceSquare(aDelta.scalar(aDelta)); 1608 1609 if(fDistanceSquare <= fDistance * fDistance) 1610 { 1611 return true; 1612 } 1613 } 1614 else if(bDoDistanceTestEnd) 1615 { 1616 const B2DVector aDelta(rTestPosition - rEdgeEnd); 1617 const double fDistanceSquare(aDelta.scalar(aDelta)); 1618 1619 if(fDistanceSquare <= fDistance * fDistance) 1620 { 1621 return true; 1622 } 1623 } 1624 1625 return false; 1626 } 1627 1628 // test if point is inside epsilon-range around the given Polygon. Can be used 1629 // for HitTesting. The epsilon-range is defined to be the tube around the polygon 1630 // with distance fDistance and rounded edges (start and end point). isInEpsilonRange(const B2DPolygon & rCandidate,const B2DPoint & rTestPosition,double fDistance)1631 bool isInEpsilonRange(const B2DPolygon& rCandidate, const B2DPoint& rTestPosition, double fDistance) 1632 { 1633 // force to non-bezier polygon 1634 const B2DPolygon aCandidate(rCandidate.getDefaultAdaptiveSubdivision()); 1635 const sal_uInt32 nPointCount(aCandidate.count()); 1636 1637 if(nPointCount) 1638 { 1639 const sal_uInt32 nEdgeCount(aCandidate.isClosed() ? nPointCount : nPointCount - 1L); 1640 B2DPoint aCurrent(aCandidate.getB2DPoint(0)); 1641 1642 if(nEdgeCount) 1643 { 1644 // edges 1645 for(sal_uInt32 a(0); a < nEdgeCount; a++) 1646 { 1647 const sal_uInt32 nNextIndex((a + 1) % nPointCount); 1648 const B2DPoint aNext(aCandidate.getB2DPoint(nNextIndex)); 1649 1650 if(isInEpsilonRange(aCurrent, aNext, rTestPosition, fDistance)) 1651 { 1652 return true; 1653 } 1654 1655 // prepare next step 1656 aCurrent = aNext; 1657 } 1658 } 1659 else 1660 { 1661 // no edges, but points -> not closed. Check single point. Just 1662 // use isInEpsilonRange with twice the same point, it handles those well 1663 if(isInEpsilonRange(aCurrent, aCurrent, rTestPosition, fDistance)) 1664 { 1665 return true; 1666 } 1667 } 1668 } 1669 1670 return false; 1671 } 1672 createPolygonFromRect(const B2DRectangle & rRect,double fRadius)1673 B2DPolygon createPolygonFromRect( const B2DRectangle& rRect, double fRadius ) 1674 { 1675 const double fZero(0.0); 1676 const double fOne(1.0); 1677 1678 if(fTools::lessOrEqual(fRadius, fZero)) 1679 { 1680 // no radius, use rectangle 1681 return createPolygonFromRect( rRect ); 1682 } 1683 else if(fTools::moreOrEqual(fRadius, fOne)) 1684 { 1685 // full radius, use ellipse 1686 const B2DPoint aCenter(rRect.getCenter()); 1687 const double fRadiusX(rRect.getWidth() / 2.0); 1688 const double fRadiusY(rRect.getHeight() / 2.0); 1689 1690 return createPolygonFromEllipse( aCenter, fRadiusX, fRadiusY ); 1691 } 1692 else 1693 { 1694 // create rectangle with two radii between ]0.0 .. 1.0[ 1695 return createPolygonFromRect( rRect, fRadius, fRadius ); 1696 } 1697 } 1698 createPolygonFromRect(const B2DRectangle & rRect,double fRadiusX,double fRadiusY)1699 B2DPolygon createPolygonFromRect( const B2DRectangle& rRect, double fRadiusX, double fRadiusY ) 1700 { 1701 const double fZero(0.0); 1702 const double fOne(1.0); 1703 1704 // crop to useful values 1705 if(fTools::less(fRadiusX, fZero)) 1706 { 1707 fRadiusX = fZero; 1708 } 1709 else if(fTools::more(fRadiusX, fOne)) 1710 { 1711 fRadiusX = fOne; 1712 } 1713 1714 if(fTools::less(fRadiusY, fZero)) 1715 { 1716 fRadiusY = fZero; 1717 } 1718 else if(fTools::more(fRadiusY, fOne)) 1719 { 1720 fRadiusY = fOne; 1721 } 1722 1723 if(fZero == fRadiusX || fZero == fRadiusY) 1724 { 1725 B2DPolygon aRetval; 1726 1727 // at least in one direction no radius, use rectangle. 1728 // Do not use createPolygonFromRect() here since original 1729 // creator (historical reasons) still creates a start point at the 1730 // bottom center, so do the same here to get the same line patterns. 1731 // Due to this the order of points is different, too. 1732 const B2DPoint aBottomCenter(rRect.getCenter().getX(), rRect.getMaxY()); 1733 aRetval.append(aBottomCenter); 1734 1735 aRetval.append( B2DPoint( rRect.getMinX(), rRect.getMaxY() ) ); 1736 aRetval.append( B2DPoint( rRect.getMinX(), rRect.getMinY() ) ); 1737 aRetval.append( B2DPoint( rRect.getMaxX(), rRect.getMinY() ) ); 1738 aRetval.append( B2DPoint( rRect.getMaxX(), rRect.getMaxY() ) ); 1739 1740 // close 1741 aRetval.setClosed( true ); 1742 1743 return aRetval; 1744 } 1745 else if(fOne == fRadiusX && fOne == fRadiusY) 1746 { 1747 // in both directions full radius, use ellipse 1748 const B2DPoint aCenter(rRect.getCenter()); 1749 const double fRectRadiusX(rRect.getWidth() / 2.0); 1750 const double fRectRadiusY(rRect.getHeight() / 2.0); 1751 1752 return createPolygonFromEllipse( aCenter, fRectRadiusX, fRectRadiusY ); 1753 } 1754 else 1755 { 1756 B2DPolygon aRetval; 1757 const double fBowX((rRect.getWidth() / 2.0) * fRadiusX); 1758 const double fBowY((rRect.getHeight() / 2.0) * fRadiusY); 1759 const double fKappa((M_SQRT2 - 1.0) * 4.0 / 3.0); 1760 1761 // create start point at bottom center 1762 if(fOne != fRadiusX) 1763 { 1764 const B2DPoint aBottomCenter(rRect.getCenter().getX(), rRect.getMaxY()); 1765 aRetval.append(aBottomCenter); 1766 } 1767 1768 // create first bow 1769 { 1770 const B2DPoint aBottomRight(rRect.getMaxX(), rRect.getMaxY()); 1771 const B2DPoint aStart(aBottomRight + B2DPoint(-fBowX, 0.0)); 1772 const B2DPoint aStop(aBottomRight + B2DPoint(0.0, -fBowY)); 1773 aRetval.append(aStart); 1774 aRetval.appendBezierSegment(interpolate(aStart, aBottomRight, fKappa), interpolate(aStop, aBottomRight, fKappa), aStop); 1775 } 1776 1777 // create second bow 1778 { 1779 const B2DPoint aTopRight(rRect.getMaxX(), rRect.getMinY()); 1780 const B2DPoint aStart(aTopRight + B2DPoint(0.0, fBowY)); 1781 const B2DPoint aStop(aTopRight + B2DPoint(-fBowX, 0.0)); 1782 aRetval.append(aStart); 1783 aRetval.appendBezierSegment(interpolate(aStart, aTopRight, fKappa), interpolate(aStop, aTopRight, fKappa), aStop); 1784 } 1785 1786 // create third bow 1787 { 1788 const B2DPoint aTopLeft(rRect.getMinX(), rRect.getMinY()); 1789 const B2DPoint aStart(aTopLeft + B2DPoint(fBowX, 0.0)); 1790 const B2DPoint aStop(aTopLeft + B2DPoint(0.0, fBowY)); 1791 aRetval.append(aStart); 1792 aRetval.appendBezierSegment(interpolate(aStart, aTopLeft, fKappa), interpolate(aStop, aTopLeft, fKappa), aStop); 1793 } 1794 1795 // create forth bow 1796 { 1797 const B2DPoint aBottomLeft(rRect.getMinX(), rRect.getMaxY()); 1798 const B2DPoint aStart(aBottomLeft + B2DPoint(0.0, -fBowY)); 1799 const B2DPoint aStop(aBottomLeft + B2DPoint(fBowX, 0.0)); 1800 aRetval.append(aStart); 1801 aRetval.appendBezierSegment(interpolate(aStart, aBottomLeft, fKappa), interpolate(aStop, aBottomLeft, fKappa), aStop); 1802 } 1803 1804 // close 1805 aRetval.setClosed( true ); 1806 1807 // remove double created points if there are extreme radii envolved 1808 if(fOne == fRadiusX || fOne == fRadiusY) 1809 { 1810 aRetval.removeDoublePoints(); 1811 } 1812 1813 return aRetval; 1814 } 1815 } 1816 createPolygonFromRect(const B2DRectangle & rRect)1817 B2DPolygon createPolygonFromRect( const B2DRectangle& rRect ) 1818 { 1819 B2DPolygon aRetval; 1820 1821 aRetval.append( B2DPoint( rRect.getMinX(), rRect.getMinY() ) ); 1822 aRetval.append( B2DPoint( rRect.getMaxX(), rRect.getMinY() ) ); 1823 aRetval.append( B2DPoint( rRect.getMaxX(), rRect.getMaxY() ) ); 1824 aRetval.append( B2DPoint( rRect.getMinX(), rRect.getMaxY() ) ); 1825 1826 // close 1827 aRetval.setClosed( true ); 1828 1829 return aRetval; 1830 } 1831 createUnitPolygon()1832 B2DPolygon createUnitPolygon() 1833 { 1834 static B2DPolygon aRetval; 1835 1836 if(!aRetval.count()) 1837 { 1838 aRetval.append( B2DPoint( 0.0, 0.0 ) ); 1839 aRetval.append( B2DPoint( 1.0, 0.0 ) ); 1840 aRetval.append( B2DPoint( 1.0, 1.0 ) ); 1841 aRetval.append( B2DPoint( 0.0, 1.0 ) ); 1842 1843 // close 1844 aRetval.setClosed( true ); 1845 } 1846 1847 return aRetval; 1848 } 1849 createPolygonFromCircle(const B2DPoint & rCenter,double fRadius)1850 B2DPolygon createPolygonFromCircle( const B2DPoint& rCenter, double fRadius ) 1851 { 1852 return createPolygonFromEllipse( rCenter, fRadius, fRadius ); 1853 } 1854 impCreateUnitCircle(sal_uInt32 nStartQuadrant)1855 B2DPolygon impCreateUnitCircle(sal_uInt32 nStartQuadrant) 1856 { 1857 B2DPolygon aUnitCircle; 1858 const double fKappa((M_SQRT2 - 1.0) * 4.0 / 3.0); 1859 const double fScaledKappa(fKappa * (1.0 / STEPSPERQUARTER)); 1860 const B2DHomMatrix aRotateMatrix(createRotateB2DHomMatrix(F_PI2 / STEPSPERQUARTER)); 1861 1862 B2DPoint aPoint(1.0, 0.0); 1863 B2DPoint aForward(1.0, fScaledKappa); 1864 B2DPoint aBackward(1.0, -fScaledKappa); 1865 1866 if(0 != nStartQuadrant) 1867 { 1868 const B2DHomMatrix aQuadrantMatrix(createRotateB2DHomMatrix(F_PI2 * (nStartQuadrant % 4))); 1869 aPoint *= aQuadrantMatrix; 1870 aBackward *= aQuadrantMatrix; 1871 aForward *= aQuadrantMatrix; 1872 } 1873 1874 aUnitCircle.append(aPoint); 1875 1876 for(sal_uInt32 a(0); a < STEPSPERQUARTER * 4; a++) 1877 { 1878 aPoint *= aRotateMatrix; 1879 aBackward *= aRotateMatrix; 1880 aUnitCircle.appendBezierSegment(aForward, aBackward, aPoint); 1881 aForward *= aRotateMatrix; 1882 } 1883 1884 aUnitCircle.setClosed(true); 1885 aUnitCircle.removeDoublePoints(); 1886 1887 return aUnitCircle; 1888 } 1889 createHalfUnitCircle()1890 B2DPolygon createHalfUnitCircle() 1891 { 1892 static B2DPolygon aUnitHalfCircle; 1893 1894 if(!aUnitHalfCircle.count()) 1895 { 1896 const double fKappa((M_SQRT2 - 1.0) * 4.0 / 3.0); 1897 const double fScaledKappa(fKappa * (1.0 / STEPSPERQUARTER)); 1898 const B2DHomMatrix aRotateMatrix(createRotateB2DHomMatrix(F_PI2 / STEPSPERQUARTER)); 1899 B2DPoint aPoint(1.0, 0.0); 1900 B2DPoint aForward(1.0, fScaledKappa); 1901 B2DPoint aBackward(1.0, -fScaledKappa); 1902 1903 aUnitHalfCircle.append(aPoint); 1904 1905 for(sal_uInt32 a(0); a < STEPSPERQUARTER * 2; a++) 1906 { 1907 aPoint *= aRotateMatrix; 1908 aBackward *= aRotateMatrix; 1909 aUnitHalfCircle.appendBezierSegment(aForward, aBackward, aPoint); 1910 aForward *= aRotateMatrix; 1911 } 1912 } 1913 1914 return aUnitHalfCircle; 1915 } 1916 createPolygonFromUnitCircle(sal_uInt32 nStartQuadrant)1917 B2DPolygon createPolygonFromUnitCircle(sal_uInt32 nStartQuadrant) 1918 { 1919 switch(nStartQuadrant % 4) 1920 { 1921 case 1 : 1922 { 1923 static B2DPolygon aUnitCircleStartQuadrantOne; 1924 1925 if(!aUnitCircleStartQuadrantOne.count()) 1926 { 1927 ::osl::Mutex m_mutex; 1928 aUnitCircleStartQuadrantOne = impCreateUnitCircle(1); 1929 } 1930 1931 return aUnitCircleStartQuadrantOne; 1932 } 1933 case 2 : 1934 { 1935 static B2DPolygon aUnitCircleStartQuadrantTwo; 1936 1937 if(!aUnitCircleStartQuadrantTwo.count()) 1938 { 1939 ::osl::Mutex m_mutex; 1940 aUnitCircleStartQuadrantTwo = impCreateUnitCircle(2); 1941 } 1942 1943 return aUnitCircleStartQuadrantTwo; 1944 } 1945 case 3 : 1946 { 1947 static B2DPolygon aUnitCircleStartQuadrantThree; 1948 1949 if(!aUnitCircleStartQuadrantThree.count()) 1950 { 1951 ::osl::Mutex m_mutex; 1952 aUnitCircleStartQuadrantThree = impCreateUnitCircle(3); 1953 } 1954 1955 return aUnitCircleStartQuadrantThree; 1956 } 1957 default : // case 0 : 1958 { 1959 static B2DPolygon aUnitCircleStartQuadrantZero; 1960 1961 if(!aUnitCircleStartQuadrantZero.count()) 1962 { 1963 ::osl::Mutex m_mutex; 1964 aUnitCircleStartQuadrantZero = impCreateUnitCircle(0); 1965 } 1966 1967 return aUnitCircleStartQuadrantZero; 1968 } 1969 } 1970 } 1971 createPolygonFromEllipse(const B2DPoint & rCenter,double fRadiusX,double fRadiusY)1972 B2DPolygon createPolygonFromEllipse( const B2DPoint& rCenter, double fRadiusX, double fRadiusY ) 1973 { 1974 B2DPolygon aRetval(createPolygonFromUnitCircle()); 1975 const B2DHomMatrix aMatrix(createScaleTranslateB2DHomMatrix(fRadiusX, fRadiusY, rCenter.getX(), rCenter.getY())); 1976 1977 aRetval.transform(aMatrix); 1978 1979 return aRetval; 1980 } 1981 createPolygonFromUnitEllipseSegment(double fStart,double fEnd)1982 B2DPolygon createPolygonFromUnitEllipseSegment( double fStart, double fEnd ) 1983 { 1984 B2DPolygon aRetval; 1985 1986 // truncate fStart, fEnd to a range of [0.0 .. F_2PI[ where F_2PI 1987 // falls back to 0.0 to ensure a unique definition 1988 if(fTools::less(fStart, 0.0)) 1989 { 1990 fStart = 0.0; 1991 } 1992 1993 if(fTools::moreOrEqual(fStart, F_2PI)) 1994 { 1995 fStart = 0.0; 1996 } 1997 1998 if(fTools::less(fEnd, 0.0)) 1999 { 2000 fEnd = 0.0; 2001 } 2002 2003 if(fTools::moreOrEqual(fEnd, F_2PI)) 2004 { 2005 fEnd = 0.0; 2006 } 2007 2008 if(fTools::equal(fStart, fEnd)) 2009 { 2010 // same start and end angle, add single point 2011 aRetval.append(B2DPoint(cos(fStart), sin(fStart))); 2012 } 2013 else 2014 { 2015 const sal_uInt32 nSegments(STEPSPERQUARTER * 4); 2016 const double fAnglePerSegment(F_PI2 / STEPSPERQUARTER); 2017 const sal_uInt32 nStartSegment(sal_uInt32(fStart / fAnglePerSegment) % nSegments); 2018 const sal_uInt32 nEndSegment(sal_uInt32(fEnd / fAnglePerSegment) % nSegments); 2019 const double fKappa((M_SQRT2 - 1.0) * 4.0 / 3.0); 2020 const double fScaledKappa(fKappa * (1.0 / STEPSPERQUARTER)); 2021 2022 B2DPoint aSegStart(cos(fStart), sin(fStart)); 2023 aRetval.append(aSegStart); 2024 2025 if(nStartSegment == nEndSegment && fTools::more(fEnd, fStart)) 2026 { 2027 // start and end in one sector and in the right order, create in one segment 2028 const B2DPoint aSegEnd(cos(fEnd), sin(fEnd)); 2029 const double fFactor(fScaledKappa * ((fEnd - fStart) / fAnglePerSegment)); 2030 2031 aRetval.appendBezierSegment( 2032 aSegStart + (B2DPoint(-aSegStart.getY(), aSegStart.getX()) * fFactor), 2033 aSegEnd - (B2DPoint(-aSegEnd.getY(), aSegEnd.getX()) * fFactor), 2034 aSegEnd); 2035 } 2036 else 2037 { 2038 double fSegEndRad((nStartSegment + 1) * fAnglePerSegment); 2039 double fFactor(fScaledKappa * ((fSegEndRad - fStart) / fAnglePerSegment)); 2040 B2DPoint aSegEnd(cos(fSegEndRad), sin(fSegEndRad)); 2041 2042 aRetval.appendBezierSegment( 2043 aSegStart + (B2DPoint(-aSegStart.getY(), aSegStart.getX()) * fFactor), 2044 aSegEnd - (B2DPoint(-aSegEnd.getY(), aSegEnd.getX()) * fFactor), 2045 aSegEnd); 2046 2047 sal_uInt32 nSegment((nStartSegment + 1) % nSegments); 2048 aSegStart = aSegEnd; 2049 2050 while(nSegment != nEndSegment) 2051 { 2052 // No end in this sector, add full sector. 2053 fSegEndRad = (nSegment + 1) * fAnglePerSegment; 2054 aSegEnd = B2DPoint(cos(fSegEndRad), sin(fSegEndRad)); 2055 2056 aRetval.appendBezierSegment( 2057 aSegStart + (B2DPoint(-aSegStart.getY(), aSegStart.getX()) * fScaledKappa), 2058 aSegEnd - (B2DPoint(-aSegEnd.getY(), aSegEnd.getX()) * fScaledKappa), 2059 aSegEnd); 2060 2061 nSegment = (nSegment + 1) % nSegments; 2062 aSegStart = aSegEnd; 2063 } 2064 2065 // End in this sector 2066 const double fSegStartRad(nSegment * fAnglePerSegment); 2067 fFactor = fScaledKappa * ((fEnd - fSegStartRad) / fAnglePerSegment); 2068 aSegEnd = B2DPoint(cos(fEnd), sin(fEnd)); 2069 2070 aRetval.appendBezierSegment( 2071 aSegStart + (B2DPoint(-aSegStart.getY(), aSegStart.getX()) * fFactor), 2072 aSegEnd - (B2DPoint(-aSegEnd.getY(), aSegEnd.getX()) * fFactor), 2073 aSegEnd); 2074 } 2075 } 2076 2077 // remove double points between segments created by segmented creation 2078 aRetval.removeDoublePoints(); 2079 2080 return aRetval; 2081 } 2082 createPolygonFromEllipseSegment(const B2DPoint & rCenter,double fRadiusX,double fRadiusY,double fStart,double fEnd)2083 B2DPolygon createPolygonFromEllipseSegment( const B2DPoint& rCenter, double fRadiusX, double fRadiusY, double fStart, double fEnd ) 2084 { 2085 B2DPolygon aRetval(createPolygonFromUnitEllipseSegment(fStart, fEnd)); 2086 const B2DHomMatrix aMatrix(createScaleTranslateB2DHomMatrix(fRadiusX, fRadiusY, rCenter.getX(), rCenter.getY())); 2087 2088 aRetval.transform(aMatrix); 2089 2090 return aRetval; 2091 } 2092 hasNeutralPoints(const B2DPolygon & rCandidate)2093 bool hasNeutralPoints(const B2DPolygon& rCandidate) 2094 { 2095 OSL_ENSURE(!rCandidate.areControlPointsUsed(), "hasNeutralPoints: ATM works not for curves (!)"); 2096 const sal_uInt32 nPointCount(rCandidate.count()); 2097 2098 if(nPointCount > 2L) 2099 { 2100 B2DPoint aPrevPoint(rCandidate.getB2DPoint(nPointCount - 1L)); 2101 B2DPoint aCurrPoint(rCandidate.getB2DPoint(0L)); 2102 2103 for(sal_uInt32 a(0L); a < nPointCount; a++) 2104 { 2105 const B2DPoint aNextPoint(rCandidate.getB2DPoint((a + 1) % nPointCount)); 2106 const B2DVector aPrevVec(aPrevPoint - aCurrPoint); 2107 const B2DVector aNextVec(aNextPoint - aCurrPoint); 2108 const B2VectorOrientation aOrientation(getOrientation(aNextVec, aPrevVec)); 2109 2110 if(ORIENTATION_NEUTRAL == aOrientation) 2111 { 2112 // current has neutral orientation 2113 return true; 2114 } 2115 else 2116 { 2117 // prepare next 2118 aPrevPoint = aCurrPoint; 2119 aCurrPoint = aNextPoint; 2120 } 2121 } 2122 } 2123 2124 return false; 2125 } 2126 removeNeutralPoints(const B2DPolygon & rCandidate)2127 B2DPolygon removeNeutralPoints(const B2DPolygon& rCandidate) 2128 { 2129 if(hasNeutralPoints(rCandidate)) 2130 { 2131 const sal_uInt32 nPointCount(rCandidate.count()); 2132 B2DPolygon aRetval; 2133 B2DPoint aPrevPoint(rCandidate.getB2DPoint(nPointCount - 1L)); 2134 B2DPoint aCurrPoint(rCandidate.getB2DPoint(0L)); 2135 2136 for(sal_uInt32 a(0L); a < nPointCount; a++) 2137 { 2138 const B2DPoint aNextPoint(rCandidate.getB2DPoint((a + 1) % nPointCount)); 2139 const B2DVector aPrevVec(aPrevPoint - aCurrPoint); 2140 const B2DVector aNextVec(aNextPoint - aCurrPoint); 2141 const B2VectorOrientation aOrientation(getOrientation(aNextVec, aPrevVec)); 2142 2143 if(ORIENTATION_NEUTRAL == aOrientation) 2144 { 2145 // current has neutral orientation, leave it out and prepare next 2146 aCurrPoint = aNextPoint; 2147 } 2148 else 2149 { 2150 // add current point 2151 aRetval.append(aCurrPoint); 2152 2153 // prepare next 2154 aPrevPoint = aCurrPoint; 2155 aCurrPoint = aNextPoint; 2156 } 2157 } 2158 2159 while(aRetval.count() && ORIENTATION_NEUTRAL == getOrientationForIndex(aRetval, 0L)) 2160 { 2161 aRetval.remove(0L); 2162 } 2163 2164 // copy closed state 2165 aRetval.setClosed(rCandidate.isClosed()); 2166 2167 return aRetval; 2168 } 2169 else 2170 { 2171 return rCandidate; 2172 } 2173 } 2174 isConvex(const B2DPolygon & rCandidate)2175 bool isConvex(const B2DPolygon& rCandidate) 2176 { 2177 OSL_ENSURE(!rCandidate.areControlPointsUsed(), "isConvex: ATM works not for curves (!)"); 2178 const sal_uInt32 nPointCount(rCandidate.count()); 2179 2180 if(nPointCount > 2L) 2181 { 2182 const B2DPoint aPrevPoint(rCandidate.getB2DPoint(nPointCount - 1L)); 2183 B2DPoint aCurrPoint(rCandidate.getB2DPoint(0L)); 2184 B2DVector aCurrVec(aPrevPoint - aCurrPoint); 2185 B2VectorOrientation aOrientation(ORIENTATION_NEUTRAL); 2186 2187 for(sal_uInt32 a(0L); a < nPointCount; a++) 2188 { 2189 const B2DPoint aNextPoint(rCandidate.getB2DPoint((a + 1) % nPointCount)); 2190 const B2DVector aNextVec(aNextPoint - aCurrPoint); 2191 const B2VectorOrientation aCurrentOrientation(getOrientation(aNextVec, aCurrVec)); 2192 2193 if(ORIENTATION_NEUTRAL == aOrientation) 2194 { 2195 // set start value, maybe neutral again 2196 aOrientation = aCurrentOrientation; 2197 } 2198 else 2199 { 2200 if(ORIENTATION_NEUTRAL != aCurrentOrientation && aCurrentOrientation != aOrientation) 2201 { 2202 // different orientations found, that's it 2203 return false; 2204 } 2205 } 2206 2207 // prepare next 2208 aCurrPoint = aNextPoint; 2209 aCurrVec = -aNextVec; 2210 } 2211 } 2212 2213 return true; 2214 } 2215 getOrientationForIndex(const B2DPolygon & rCandidate,sal_uInt32 nIndex)2216 B2VectorOrientation getOrientationForIndex(const B2DPolygon& rCandidate, sal_uInt32 nIndex) 2217 { 2218 OSL_ENSURE(nIndex < rCandidate.count(), "getOrientationForIndex: index out of range (!)"); 2219 const B2DPoint aPrev(rCandidate.getB2DPoint(getIndexOfPredecessor(nIndex, rCandidate))); 2220 const B2DPoint aCurr(rCandidate.getB2DPoint(nIndex)); 2221 const B2DPoint aNext(rCandidate.getB2DPoint(getIndexOfSuccessor(nIndex, rCandidate))); 2222 const B2DVector aBack(aPrev - aCurr); 2223 const B2DVector aForw(aNext - aCurr); 2224 2225 return getOrientation(aForw, aBack); 2226 } 2227 isPointOnLine(const B2DPoint & rStart,const B2DPoint & rEnd,const B2DPoint & rCandidate,bool bWithPoints)2228 bool isPointOnLine(const B2DPoint& rStart, const B2DPoint& rEnd, const B2DPoint& rCandidate, bool bWithPoints) 2229 { 2230 if(rCandidate.equal(rStart) || rCandidate.equal(rEnd)) 2231 { 2232 // candidate is in epsilon around start or end -> inside 2233 return bWithPoints; 2234 } 2235 else if(rStart.equal(rEnd)) 2236 { 2237 // start and end are equal, but candidate is outside their epsilon -> outside 2238 return false; 2239 } 2240 else 2241 { 2242 const B2DVector aEdgeVector(rEnd - rStart); 2243 const B2DVector aTestVector(rCandidate - rStart); 2244 2245 if(areParallel(aEdgeVector, aTestVector)) 2246 { 2247 const double fZero(0.0); 2248 const double fOne(1.0); 2249 const double fParamTestOnCurr(fabs(aEdgeVector.getX()) > fabs(aEdgeVector.getY()) 2250 ? aTestVector.getX() / aEdgeVector.getX() 2251 : aTestVector.getY() / aEdgeVector.getY()); 2252 2253 if(fTools::more(fParamTestOnCurr, fZero) && fTools::less(fParamTestOnCurr, fOne)) 2254 { 2255 return true; 2256 } 2257 } 2258 2259 return false; 2260 } 2261 } 2262 isPointOnPolygon(const B2DPolygon & rCandidate,const B2DPoint & rPoint,bool bWithPoints)2263 bool isPointOnPolygon(const B2DPolygon& rCandidate, const B2DPoint& rPoint, bool bWithPoints) 2264 { 2265 const B2DPolygon aCandidate(rCandidate.areControlPointsUsed() ? rCandidate.getDefaultAdaptiveSubdivision() : rCandidate); 2266 const sal_uInt32 nPointCount(aCandidate.count()); 2267 2268 if(nPointCount > 1L) 2269 { 2270 const sal_uInt32 nLoopCount(aCandidate.isClosed() ? nPointCount : nPointCount - 1L); 2271 B2DPoint aCurrentPoint(aCandidate.getB2DPoint(0L)); 2272 2273 for(sal_uInt32 a(0L); a < nLoopCount; a++) 2274 { 2275 const B2DPoint aNextPoint(aCandidate.getB2DPoint((a + 1L) % nPointCount)); 2276 2277 if(isPointOnLine(aCurrentPoint, aNextPoint, rPoint, bWithPoints)) 2278 { 2279 return true; 2280 } 2281 2282 aCurrentPoint = aNextPoint; 2283 } 2284 } 2285 else if(nPointCount && bWithPoints) 2286 { 2287 return rPoint.equal(aCandidate.getB2DPoint(0L)); 2288 } 2289 2290 return false; 2291 } 2292 isPointInTriangle(const B2DPoint & rA,const B2DPoint & rB,const B2DPoint & rC,const B2DPoint & rCandidate,bool bWithBorder)2293 bool isPointInTriangle(const B2DPoint& rA, const B2DPoint& rB, const B2DPoint& rC, const B2DPoint& rCandidate, bool bWithBorder) 2294 { 2295 if(arePointsOnSameSideOfLine(rA, rB, rC, rCandidate, bWithBorder)) 2296 { 2297 if(arePointsOnSameSideOfLine(rB, rC, rA, rCandidate, bWithBorder)) 2298 { 2299 if(arePointsOnSameSideOfLine(rC, rA, rB, rCandidate, bWithBorder)) 2300 { 2301 return true; 2302 } 2303 } 2304 } 2305 2306 return false; 2307 } 2308 arePointsOnSameSideOfLine(const B2DPoint & rStart,const B2DPoint & rEnd,const B2DPoint & rCandidateA,const B2DPoint & rCandidateB,bool bWithLine)2309 bool arePointsOnSameSideOfLine(const B2DPoint& rStart, const B2DPoint& rEnd, const B2DPoint& rCandidateA, const B2DPoint& rCandidateB, bool bWithLine) 2310 { 2311 const B2DVector aLineVector(rEnd - rStart); 2312 const B2DVector aVectorToA(rEnd - rCandidateA); 2313 const double fCrossA(aLineVector.cross(aVectorToA)); 2314 2315 if(fTools::equalZero(fCrossA)) 2316 { 2317 // one point on the line 2318 return bWithLine; 2319 } 2320 2321 const B2DVector aVectorToB(rEnd - rCandidateB); 2322 const double fCrossB(aLineVector.cross(aVectorToB)); 2323 2324 if(fTools::equalZero(fCrossB)) 2325 { 2326 // one point on the line 2327 return bWithLine; 2328 } 2329 2330 // return true if they both have the same sign 2331 return ((fCrossA > 0.0) == (fCrossB > 0.0)); 2332 } 2333 addTriangleFan(const B2DPolygon & rCandidate,B2DPolygon & rTarget)2334 void addTriangleFan(const B2DPolygon& rCandidate, B2DPolygon& rTarget) 2335 { 2336 const sal_uInt32 nCount(rCandidate.count()); 2337 2338 if(nCount > 2L) 2339 { 2340 const B2DPoint aStart(rCandidate.getB2DPoint(0L)); 2341 B2DPoint aLast(rCandidate.getB2DPoint(1L)); 2342 2343 for(sal_uInt32 a(2L); a < nCount; a++) 2344 { 2345 const B2DPoint aCurrent(rCandidate.getB2DPoint(a)); 2346 rTarget.append(aStart); 2347 rTarget.append(aLast); 2348 rTarget.append(aCurrent); 2349 2350 // prepare next 2351 aLast = aCurrent; 2352 } 2353 } 2354 } 2355 2356 namespace 2357 { 2358 /// return 0 for input of 0, -1 for negative and 1 for positive input lcl_sgn(const double n)2359 inline int lcl_sgn( const double n ) 2360 { 2361 return n == 0.0 ? 0 : 1 - 2*::rtl::math::isSignBitSet(n); 2362 } 2363 } 2364 isRectangle(const B2DPolygon & rPoly)2365 bool isRectangle( const B2DPolygon& rPoly ) 2366 { 2367 // polygon must be closed to resemble a rect, and contain 2368 // at least four points. 2369 if( !rPoly.isClosed() || 2370 rPoly.count() < 4 || 2371 rPoly.areControlPointsUsed() ) 2372 { 2373 return false; 2374 } 2375 2376 // number of 90 degree turns the polygon has taken 2377 int nNumTurns(0); 2378 2379 int nVerticalEdgeType=0; 2380 int nHorizontalEdgeType=0; 2381 bool bNullVertex(true); 2382 bool bCWPolygon(false); // when true, polygon is CW 2383 // oriented, when false, CCW 2384 bool bOrientationSet(false); // when false, polygon 2385 // orientation has not yet 2386 // been determined. 2387 2388 // scan all _edges_ (which involves coming back to point 0 2389 // for the last edge - thus the modulo operation below) 2390 const sal_Int32 nCount( rPoly.count() ); 2391 for( sal_Int32 i=0; i<nCount; ++i ) 2392 { 2393 const B2DPoint& rPoint0( rPoly.getB2DPoint(i % nCount) ); 2394 const B2DPoint& rPoint1( rPoly.getB2DPoint((i+1) % nCount) ); 2395 2396 // is 0 for zero direction vector, 1 for south edge and -1 2397 // for north edge (standard screen coordinate system) 2398 int nCurrVerticalEdgeType( lcl_sgn( rPoint1.getY() - rPoint0.getY() ) ); 2399 2400 // is 0 for zero direction vector, 1 for east edge and -1 2401 // for west edge (standard screen coordinate system) 2402 int nCurrHorizontalEdgeType( lcl_sgn(rPoint1.getX() - rPoint0.getX()) ); 2403 2404 if( nCurrVerticalEdgeType && nCurrHorizontalEdgeType ) 2405 return false; // oblique edge - for sure no rect 2406 2407 const bool bCurrNullVertex( !nCurrVerticalEdgeType && !nCurrHorizontalEdgeType ); 2408 2409 // current vertex is equal to previous - just skip, 2410 // until we have a real edge 2411 if( bCurrNullVertex ) 2412 continue; 2413 2414 // if previous edge has two identical points, because 2415 // no previous edge direction was available, simply 2416 // take this first non-null edge as the start 2417 // direction. That's what will happen here, if 2418 // bNullVertex is false 2419 if( !bNullVertex ) 2420 { 2421 // 2D cross product - is 1 for CW and -1 for CCW turns 2422 const int nCrossProduct( nHorizontalEdgeType*nCurrVerticalEdgeType - 2423 nVerticalEdgeType*nCurrHorizontalEdgeType ); 2424 2425 if( !nCrossProduct ) 2426 continue; // no change in orientation - 2427 // collinear edges - just go on 2428 2429 // if polygon orientation is not set, we'll 2430 // determine it now 2431 if( !bOrientationSet ) 2432 { 2433 bCWPolygon = nCrossProduct == 1; 2434 bOrientationSet = true; 2435 } 2436 else 2437 { 2438 // if current turn orientation is not equal 2439 // initial orientation, this is not a 2440 // rectangle (as rectangles have consistent 2441 // orientation). 2442 if( (nCrossProduct == 1) != bCWPolygon ) 2443 return false; 2444 } 2445 2446 ++nNumTurns; 2447 2448 // More than four 90 degree turns are an 2449 // indication that this must not be a rectangle. 2450 if( nNumTurns > 4 ) 2451 return false; 2452 } 2453 2454 // store current state for the next turn 2455 nVerticalEdgeType = nCurrVerticalEdgeType; 2456 nHorizontalEdgeType = nCurrHorizontalEdgeType; 2457 bNullVertex = false; // won't reach this line, 2458 // if bCurrNullVertex is 2459 // true - see above 2460 } 2461 2462 return true; 2463 } 2464 createB3DPolygonFromB2DPolygon(const B2DPolygon & rCandidate,double fZCoordinate)2465 B3DPolygon createB3DPolygonFromB2DPolygon(const B2DPolygon& rCandidate, double fZCoordinate) 2466 { 2467 if(rCandidate.areControlPointsUsed()) 2468 { 2469 // call myself recursively with subdivided input 2470 const B2DPolygon aCandidate(adaptiveSubdivideByAngle(rCandidate)); 2471 return createB3DPolygonFromB2DPolygon(aCandidate, fZCoordinate); 2472 } 2473 else 2474 { 2475 B3DPolygon aRetval; 2476 2477 for(sal_uInt32 a(0L); a < rCandidate.count(); a++) 2478 { 2479 B2DPoint aPoint(rCandidate.getB2DPoint(a)); 2480 aRetval.append(B3DPoint(aPoint.getX(), aPoint.getY(), fZCoordinate)); 2481 } 2482 2483 // copy closed state 2484 aRetval.setClosed(rCandidate.isClosed()); 2485 2486 return aRetval; 2487 } 2488 } 2489 createB2DPolygonFromB3DPolygon(const B3DPolygon & rCandidate,const B3DHomMatrix & rMat)2490 B2DPolygon createB2DPolygonFromB3DPolygon(const B3DPolygon& rCandidate, const B3DHomMatrix& rMat) 2491 { 2492 B2DPolygon aRetval; 2493 const sal_uInt32 nCount(rCandidate.count()); 2494 const bool bIsIdentity(rMat.isIdentity()); 2495 2496 for(sal_uInt32 a(0L); a < nCount; a++) 2497 { 2498 B3DPoint aCandidate(rCandidate.getB3DPoint(a)); 2499 2500 if(!bIsIdentity) 2501 { 2502 aCandidate *= rMat; 2503 } 2504 2505 aRetval.append(B2DPoint(aCandidate.getX(), aCandidate.getY())); 2506 } 2507 2508 // copy closed state 2509 aRetval.setClosed(rCandidate.isClosed()); 2510 2511 return aRetval; 2512 } 2513 getDistancePointToEndlessRay(const B2DPoint & rPointA,const B2DPoint & rPointB,const B2DPoint & rTestPoint,double & rCut)2514 double getDistancePointToEndlessRay(const B2DPoint& rPointA, const B2DPoint& rPointB, const B2DPoint& rTestPoint, double& rCut) 2515 { 2516 if(rPointA.equal(rPointB)) 2517 { 2518 rCut = 0.0; 2519 const B2DVector aVector(rTestPoint - rPointA); 2520 return aVector.getLength(); 2521 } 2522 else 2523 { 2524 // get the relative cut value on line vector (Vector1) for cut with perpendicular through TestPoint 2525 const B2DVector aVector1(rPointB - rPointA); 2526 const B2DVector aVector2(rTestPoint - rPointA); 2527 const double fDividend((aVector2.getX() * aVector1.getX()) + (aVector2.getY() * aVector1.getY())); 2528 const double fDivisor((aVector1.getX() * aVector1.getX()) + (aVector1.getY() * aVector1.getY())); 2529 2530 rCut = fDividend / fDivisor; 2531 2532 const B2DPoint aCutPoint(rPointA + rCut * aVector1); 2533 const B2DVector aVector(rTestPoint - aCutPoint); 2534 return aVector.getLength(); 2535 } 2536 } 2537 getSmallestDistancePointToEdge(const B2DPoint & rPointA,const B2DPoint & rPointB,const B2DPoint & rTestPoint,double & rCut)2538 double getSmallestDistancePointToEdge(const B2DPoint& rPointA, const B2DPoint& rPointB, const B2DPoint& rTestPoint, double& rCut) 2539 { 2540 if(rPointA.equal(rPointB)) 2541 { 2542 rCut = 0.0; 2543 const B2DVector aVector(rTestPoint - rPointA); 2544 return aVector.getLength(); 2545 } 2546 else 2547 { 2548 // get the relative cut value on line vector (Vector1) for cut with perpendicular through TestPoint 2549 const B2DVector aVector1(rPointB - rPointA); 2550 const B2DVector aVector2(rTestPoint - rPointA); 2551 const double fDividend((aVector2.getX() * aVector1.getX()) + (aVector2.getY() * aVector1.getY())); 2552 const double fDivisor((aVector1.getX() * aVector1.getX()) + (aVector1.getY() * aVector1.getY())); 2553 const double fCut(fDividend / fDivisor); 2554 2555 if(fCut < 0.0) 2556 { 2557 // not in line range, get distance to PointA 2558 rCut = 0.0; 2559 return aVector2.getLength(); 2560 } 2561 else if(fCut > 1.0) 2562 { 2563 // not in line range, get distance to PointB 2564 rCut = 1.0; 2565 const B2DVector aVector(rTestPoint - rPointB); 2566 return aVector.getLength(); 2567 } 2568 else 2569 { 2570 // in line range 2571 const B2DPoint aCutPoint(rPointA + fCut * aVector1); 2572 const B2DVector aVector(rTestPoint - aCutPoint); 2573 rCut = fCut; 2574 return aVector.getLength(); 2575 } 2576 } 2577 } 2578 getSmallestDistancePointToPolygon(const B2DPolygon & rCandidate,const B2DPoint & rTestPoint,sal_uInt32 & rEdgeIndex,double & rCut)2579 double getSmallestDistancePointToPolygon(const B2DPolygon& rCandidate, const B2DPoint& rTestPoint, sal_uInt32& rEdgeIndex, double& rCut) 2580 { 2581 double fRetval(DBL_MAX); 2582 const sal_uInt32 nPointCount(rCandidate.count()); 2583 2584 if(nPointCount > 1L) 2585 { 2586 const double fZero(0.0); 2587 const sal_uInt32 nEdgeCount(rCandidate.isClosed() ? nPointCount : nPointCount - 1L); 2588 B2DCubicBezier aBezier; 2589 aBezier.setStartPoint(rCandidate.getB2DPoint(0)); 2590 2591 for(sal_uInt32 a(0L); a < nEdgeCount; a++) 2592 { 2593 const sal_uInt32 nNextIndex((a + 1) % nPointCount); 2594 aBezier.setEndPoint(rCandidate.getB2DPoint(nNextIndex)); 2595 double fEdgeDist; 2596 double fNewCut; 2597 bool bEdgeIsCurve(false); 2598 2599 if(rCandidate.areControlPointsUsed()) 2600 { 2601 aBezier.setControlPointA(rCandidate.getNextControlPoint(a)); 2602 aBezier.setControlPointB(rCandidate.getPrevControlPoint(nNextIndex)); 2603 aBezier.testAndSolveTrivialBezier(); 2604 bEdgeIsCurve = aBezier.isBezier(); 2605 } 2606 2607 if(bEdgeIsCurve) 2608 { 2609 fEdgeDist = aBezier.getSmallestDistancePointToBezierSegment(rTestPoint, fNewCut); 2610 } 2611 else 2612 { 2613 fEdgeDist = getSmallestDistancePointToEdge(aBezier.getStartPoint(), aBezier.getEndPoint(), rTestPoint, fNewCut); 2614 } 2615 2616 if(DBL_MAX == fRetval || fEdgeDist < fRetval) 2617 { 2618 fRetval = fEdgeDist; 2619 rEdgeIndex = a; 2620 rCut = fNewCut; 2621 2622 if(fTools::equal(fRetval, fZero)) 2623 { 2624 // already found zero distance, cannot get better. Ensure numerical zero value and end loop. 2625 fRetval = 0.0; 2626 break; 2627 } 2628 } 2629 2630 // prepare next step 2631 aBezier.setStartPoint(aBezier.getEndPoint()); 2632 } 2633 2634 if(1.0 == rCut) 2635 { 2636 // correct rEdgeIndex when not last point 2637 if(rCandidate.isClosed()) 2638 { 2639 rEdgeIndex = getIndexOfSuccessor(rEdgeIndex, rCandidate); 2640 rCut = 0.0; 2641 } 2642 else 2643 { 2644 if(rEdgeIndex != nEdgeCount - 1L) 2645 { 2646 rEdgeIndex++; 2647 rCut = 0.0; 2648 } 2649 } 2650 } 2651 } 2652 2653 return fRetval; 2654 } 2655 distort(const B2DPoint & rCandidate,const B2DRange & rOriginal,const B2DPoint & rTopLeft,const B2DPoint & rTopRight,const B2DPoint & rBottomLeft,const B2DPoint & rBottomRight)2656 B2DPoint distort(const B2DPoint& rCandidate, const B2DRange& rOriginal, const B2DPoint& rTopLeft, const B2DPoint& rTopRight, const B2DPoint& rBottomLeft, const B2DPoint& rBottomRight) 2657 { 2658 if(fTools::equalZero(rOriginal.getWidth()) || fTools::equalZero(rOriginal.getHeight())) 2659 { 2660 return rCandidate; 2661 } 2662 else 2663 { 2664 const double fRelativeX((rCandidate.getX() - rOriginal.getMinX()) / rOriginal.getWidth()); 2665 const double fRelativeY((rCandidate.getY() - rOriginal.getMinY()) / rOriginal.getHeight()); 2666 const double fOneMinusRelativeX(1.0 - fRelativeX); 2667 const double fOneMinusRelativeY(1.0 - fRelativeY); 2668 const double fNewX((fOneMinusRelativeY) * ((fOneMinusRelativeX) * rTopLeft.getX() + fRelativeX * rTopRight.getX()) + 2669 fRelativeY * ((fOneMinusRelativeX) * rBottomLeft.getX() + fRelativeX * rBottomRight.getX())); 2670 const double fNewY((fOneMinusRelativeX) * ((fOneMinusRelativeY) * rTopLeft.getY() + fRelativeY * rBottomLeft.getY()) + 2671 fRelativeX * ((fOneMinusRelativeY) * rTopRight.getY() + fRelativeY * rBottomRight.getY())); 2672 2673 return B2DPoint(fNewX, fNewY); 2674 } 2675 } 2676 distort(const B2DPolygon & rCandidate,const B2DRange & rOriginal,const B2DPoint & rTopLeft,const B2DPoint & rTopRight,const B2DPoint & rBottomLeft,const B2DPoint & rBottomRight)2677 B2DPolygon distort(const B2DPolygon& rCandidate, const B2DRange& rOriginal, const B2DPoint& rTopLeft, const B2DPoint& rTopRight, const B2DPoint& rBottomLeft, const B2DPoint& rBottomRight) 2678 { 2679 const sal_uInt32 nPointCount(rCandidate.count()); 2680 2681 if(nPointCount && 0.0 != rOriginal.getWidth() && 0.0 != rOriginal.getHeight()) 2682 { 2683 B2DPolygon aRetval; 2684 2685 for(sal_uInt32 a(0L); a < nPointCount; a++) 2686 { 2687 aRetval.append(distort(rCandidate.getB2DPoint(a), rOriginal, rTopLeft, rTopRight, rBottomLeft, rBottomRight)); 2688 2689 if(rCandidate.areControlPointsUsed()) 2690 { 2691 if(!rCandidate.getPrevControlPoint(a).equalZero()) 2692 { 2693 aRetval.setPrevControlPoint(a, distort(rCandidate.getPrevControlPoint(a), rOriginal, rTopLeft, rTopRight, rBottomLeft, rBottomRight)); 2694 } 2695 2696 if(!rCandidate.getNextControlPoint(a).equalZero()) 2697 { 2698 aRetval.setNextControlPoint(a, distort(rCandidate.getNextControlPoint(a), rOriginal, rTopLeft, rTopRight, rBottomLeft, rBottomRight)); 2699 } 2700 } 2701 } 2702 2703 aRetval.setClosed(rCandidate.isClosed()); 2704 return aRetval; 2705 } 2706 else 2707 { 2708 return rCandidate; 2709 } 2710 } 2711 rotateAroundPoint(const B2DPolygon & rCandidate,const B2DPoint & rCenter,double fAngle)2712 B2DPolygon rotateAroundPoint(const B2DPolygon& rCandidate, const B2DPoint& rCenter, double fAngle) 2713 { 2714 const sal_uInt32 nPointCount(rCandidate.count()); 2715 B2DPolygon aRetval(rCandidate); 2716 2717 if(nPointCount) 2718 { 2719 const B2DHomMatrix aMatrix(basegfx::tools::createRotateAroundPoint(rCenter, fAngle)); 2720 2721 aRetval.transform(aMatrix); 2722 } 2723 2724 return aRetval; 2725 } 2726 expandToCurve(const B2DPolygon & rCandidate)2727 B2DPolygon expandToCurve(const B2DPolygon& rCandidate) 2728 { 2729 B2DPolygon aRetval(rCandidate); 2730 2731 for(sal_uInt32 a(0L); a < rCandidate.count(); a++) 2732 { 2733 expandToCurveInPoint(aRetval, a); 2734 } 2735 2736 return aRetval; 2737 } 2738 expandToCurveInPoint(B2DPolygon & rCandidate,sal_uInt32 nIndex)2739 bool expandToCurveInPoint(B2DPolygon& rCandidate, sal_uInt32 nIndex) 2740 { 2741 OSL_ENSURE(nIndex < rCandidate.count(), "expandToCurveInPoint: Access to polygon out of range (!)"); 2742 bool bRetval(false); 2743 const sal_uInt32 nPointCount(rCandidate.count()); 2744 2745 if(nPointCount) 2746 { 2747 // predecessor 2748 if(!rCandidate.isPrevControlPointUsed(nIndex)) 2749 { 2750 if(!rCandidate.isClosed() && 0 == nIndex) 2751 { 2752 // do not create previous vector for start point of open polygon 2753 } 2754 else 2755 { 2756 const sal_uInt32 nPrevIndex((nIndex + (nPointCount - 1)) % nPointCount); 2757 rCandidate.setPrevControlPoint(nIndex, interpolate(rCandidate.getB2DPoint(nIndex), rCandidate.getB2DPoint(nPrevIndex), 1.0 / 3.0)); 2758 bRetval = true; 2759 } 2760 } 2761 2762 // successor 2763 if(!rCandidate.isNextControlPointUsed(nIndex)) 2764 { 2765 if(!rCandidate.isClosed() && nIndex + 1 == nPointCount) 2766 { 2767 // do not create next vector for end point of open polygon 2768 } 2769 else 2770 { 2771 const sal_uInt32 nNextIndex((nIndex + 1) % nPointCount); 2772 rCandidate.setNextControlPoint(nIndex, interpolate(rCandidate.getB2DPoint(nIndex), rCandidate.getB2DPoint(nNextIndex), 1.0 / 3.0)); 2773 bRetval = true; 2774 } 2775 } 2776 } 2777 2778 return bRetval; 2779 } 2780 setContinuity(const B2DPolygon & rCandidate,B2VectorContinuity eContinuity)2781 B2DPolygon setContinuity(const B2DPolygon& rCandidate, B2VectorContinuity eContinuity) 2782 { 2783 B2DPolygon aRetval(rCandidate); 2784 2785 for(sal_uInt32 a(0L); a < rCandidate.count(); a++) 2786 { 2787 setContinuityInPoint(aRetval, a, eContinuity); 2788 } 2789 2790 return aRetval; 2791 } 2792 setContinuityInPoint(B2DPolygon & rCandidate,sal_uInt32 nIndex,B2VectorContinuity eContinuity)2793 bool setContinuityInPoint(B2DPolygon& rCandidate, sal_uInt32 nIndex, B2VectorContinuity eContinuity) 2794 { 2795 OSL_ENSURE(nIndex < rCandidate.count(), "setContinuityInPoint: Access to polygon out of range (!)"); 2796 bool bRetval(false); 2797 const sal_uInt32 nPointCount(rCandidate.count()); 2798 2799 if(nPointCount) 2800 { 2801 const B2DPoint aCurrentPoint(rCandidate.getB2DPoint(nIndex)); 2802 2803 switch(eContinuity) 2804 { 2805 case CONTINUITY_NONE : 2806 { 2807 if(rCandidate.isPrevControlPointUsed(nIndex)) 2808 { 2809 if(!rCandidate.isClosed() && 0 == nIndex) 2810 { 2811 // remove existing previous vector for start point of open polygon 2812 rCandidate.resetPrevControlPoint(nIndex); 2813 } 2814 else 2815 { 2816 const sal_uInt32 nPrevIndex((nIndex + (nPointCount - 1)) % nPointCount); 2817 rCandidate.setPrevControlPoint(nIndex, interpolate(aCurrentPoint, rCandidate.getB2DPoint(nPrevIndex), 1.0 / 3.0)); 2818 } 2819 2820 bRetval = true; 2821 } 2822 2823 if(rCandidate.isNextControlPointUsed(nIndex)) 2824 { 2825 if(!rCandidate.isClosed() && nIndex == nPointCount + 1) 2826 { 2827 // remove next vector for end point of open polygon 2828 rCandidate.resetNextControlPoint(nIndex); 2829 } 2830 else 2831 { 2832 const sal_uInt32 nNextIndex((nIndex + 1) % nPointCount); 2833 rCandidate.setNextControlPoint(nIndex, interpolate(aCurrentPoint, rCandidate.getB2DPoint(nNextIndex), 1.0 / 3.0)); 2834 } 2835 2836 bRetval = true; 2837 } 2838 2839 break; 2840 } 2841 case CONTINUITY_C1 : 2842 { 2843 if(rCandidate.isPrevControlPointUsed(nIndex) && rCandidate.isNextControlPointUsed(nIndex)) 2844 { 2845 // lengths both exist since both are used 2846 B2DVector aVectorPrev(rCandidate.getPrevControlPoint(nIndex) - aCurrentPoint); 2847 B2DVector aVectorNext(rCandidate.getNextControlPoint(nIndex) - aCurrentPoint); 2848 const double fLenPrev(aVectorPrev.getLength()); 2849 const double fLenNext(aVectorNext.getLength()); 2850 aVectorPrev.normalize(); 2851 aVectorNext.normalize(); 2852 const B2VectorOrientation aOrientation(getOrientation(aVectorPrev, aVectorNext)); 2853 2854 if(ORIENTATION_NEUTRAL == aOrientation && aVectorPrev.scalar(aVectorNext) < 0.0) 2855 { 2856 // parallel and opposite direction; check length 2857 if(fTools::equal(fLenPrev, fLenNext)) 2858 { 2859 // this would be even C2, but we want C1. Use the lengths of the corresponding edges. 2860 const sal_uInt32 nPrevIndex((nIndex + (nPointCount - 1)) % nPointCount); 2861 const sal_uInt32 nNextIndex((nIndex + 1) % nPointCount); 2862 const double fLenPrevEdge(B2DVector(rCandidate.getB2DPoint(nPrevIndex) - aCurrentPoint).getLength() * (1.0 / 3.0)); 2863 const double fLenNextEdge(B2DVector(rCandidate.getB2DPoint(nNextIndex) - aCurrentPoint).getLength() * (1.0 / 3.0)); 2864 2865 rCandidate.setControlPoints(nIndex, 2866 aCurrentPoint + (aVectorPrev * fLenPrevEdge), 2867 aCurrentPoint + (aVectorNext * fLenNextEdge)); 2868 bRetval = true; 2869 } 2870 } 2871 else 2872 { 2873 // not parallel or same direction, set vectors and length 2874 const B2DVector aNormalizedPerpendicular(getNormalizedPerpendicular(aVectorPrev + aVectorNext)); 2875 2876 if(ORIENTATION_POSITIVE == aOrientation) 2877 { 2878 rCandidate.setControlPoints(nIndex, 2879 aCurrentPoint - (aNormalizedPerpendicular * fLenPrev), 2880 aCurrentPoint + (aNormalizedPerpendicular * fLenNext)); 2881 } 2882 else 2883 { 2884 rCandidate.setControlPoints(nIndex, 2885 aCurrentPoint + (aNormalizedPerpendicular * fLenPrev), 2886 aCurrentPoint - (aNormalizedPerpendicular * fLenNext)); 2887 } 2888 2889 bRetval = true; 2890 } 2891 } 2892 break; 2893 } 2894 case CONTINUITY_C2 : 2895 { 2896 if(rCandidate.isPrevControlPointUsed(nIndex) && rCandidate.isNextControlPointUsed(nIndex)) 2897 { 2898 // lengths both exist since both are used 2899 B2DVector aVectorPrev(rCandidate.getPrevControlPoint(nIndex) - aCurrentPoint); 2900 B2DVector aVectorNext(rCandidate.getNextControlPoint(nIndex) - aCurrentPoint); 2901 const double fCommonLength((aVectorPrev.getLength() + aVectorNext.getLength()) / 2.0); 2902 aVectorPrev.normalize(); 2903 aVectorNext.normalize(); 2904 const B2VectorOrientation aOrientation(getOrientation(aVectorPrev, aVectorNext)); 2905 2906 if(ORIENTATION_NEUTRAL == aOrientation && aVectorPrev.scalar(aVectorNext) < 0.0) 2907 { 2908 // parallel and opposite direction; set length. Use one direction for better numerical correctness 2909 const B2DVector aScaledDirection(aVectorPrev * fCommonLength); 2910 2911 rCandidate.setControlPoints(nIndex, 2912 aCurrentPoint + aScaledDirection, 2913 aCurrentPoint - aScaledDirection); 2914 } 2915 else 2916 { 2917 // not parallel or same direction, set vectors and length 2918 const B2DVector aNormalizedPerpendicular(getNormalizedPerpendicular(aVectorPrev + aVectorNext)); 2919 const B2DVector aPerpendicular(aNormalizedPerpendicular * fCommonLength); 2920 2921 if(ORIENTATION_POSITIVE == aOrientation) 2922 { 2923 rCandidate.setControlPoints(nIndex, 2924 aCurrentPoint - aPerpendicular, 2925 aCurrentPoint + aPerpendicular); 2926 } 2927 else 2928 { 2929 rCandidate.setControlPoints(nIndex, 2930 aCurrentPoint + aPerpendicular, 2931 aCurrentPoint - aPerpendicular); 2932 } 2933 } 2934 2935 bRetval = true; 2936 } 2937 break; 2938 } 2939 } 2940 } 2941 2942 return bRetval; 2943 } 2944 growInNormalDirection(const B2DPolygon & rCandidate,double fValue)2945 B2DPolygon growInNormalDirection(const B2DPolygon& rCandidate, double fValue) 2946 { 2947 if(0.0 != fValue) 2948 { 2949 if(rCandidate.areControlPointsUsed()) 2950 { 2951 // call myself recursively with subdivided input 2952 const B2DPolygon aCandidate(adaptiveSubdivideByAngle(rCandidate)); 2953 return growInNormalDirection(aCandidate, fValue); 2954 } 2955 else 2956 { 2957 B2DPolygon aRetval; 2958 const sal_uInt32 nPointCount(rCandidate.count()); 2959 2960 if(nPointCount) 2961 { 2962 B2DPoint aPrev(rCandidate.getB2DPoint(nPointCount - 1L)); 2963 B2DPoint aCurrent(rCandidate.getB2DPoint(0L)); 2964 2965 for(sal_uInt32 a(0L); a < nPointCount; a++) 2966 { 2967 const B2DPoint aNext(rCandidate.getB2DPoint(a + 1L == nPointCount ? 0L : a + 1L)); 2968 const B2DVector aBack(aPrev - aCurrent); 2969 const B2DVector aForw(aNext - aCurrent); 2970 const B2DVector aPerpBack(getNormalizedPerpendicular(aBack)); 2971 const B2DVector aPerpForw(getNormalizedPerpendicular(aForw)); 2972 B2DVector aDirection(aPerpBack - aPerpForw); 2973 aDirection.normalize(); 2974 aDirection *= fValue; 2975 aRetval.append(aCurrent + aDirection); 2976 2977 // prepare next step 2978 aPrev = aCurrent; 2979 aCurrent = aNext; 2980 } 2981 } 2982 2983 // copy closed state 2984 aRetval.setClosed(rCandidate.isClosed()); 2985 2986 return aRetval; 2987 } 2988 } 2989 else 2990 { 2991 return rCandidate; 2992 } 2993 } 2994 reSegmentPolygon(const B2DPolygon & rCandidate,sal_uInt32 nSegments)2995 B2DPolygon reSegmentPolygon(const B2DPolygon& rCandidate, sal_uInt32 nSegments) 2996 { 2997 B2DPolygon aRetval; 2998 const sal_uInt32 nPointCount(rCandidate.count()); 2999 3000 if(nPointCount && nSegments) 3001 { 3002 // get current segment count 3003 const sal_uInt32 nSegmentCount(rCandidate.isClosed() ? nPointCount : nPointCount - 1L); 3004 3005 if(nSegmentCount == nSegments) 3006 { 3007 aRetval = rCandidate; 3008 } 3009 else 3010 { 3011 const double fLength(getLength(rCandidate)); 3012 const sal_uInt32 nLoopCount(rCandidate.isClosed() ? nSegments : nSegments + 1L); 3013 3014 for(sal_uInt32 a(0L); a < nLoopCount; a++) 3015 { 3016 const double fRelativePos((double)a / (double)nSegments); // 0.0 .. 1.0 3017 const B2DPoint aNewPoint(getPositionRelative(rCandidate, fRelativePos, fLength)); 3018 aRetval.append(aNewPoint); 3019 } 3020 3021 // copy closed flag 3022 aRetval.setClosed(rCandidate.isClosed()); 3023 } 3024 } 3025 3026 return aRetval; 3027 } 3028 reSegmentPolygonEdges(const B2DPolygon & rCandidate,sal_uInt32 nSubEdges,bool bHandleCurvedEdges,bool bHandleStraightEdges)3029 B2DPolygon reSegmentPolygonEdges(const B2DPolygon& rCandidate, sal_uInt32 nSubEdges, bool bHandleCurvedEdges, bool bHandleStraightEdges) 3030 { 3031 const sal_uInt32 nPointCount(rCandidate.count()); 3032 3033 if(nPointCount < 2 || nSubEdges < 2 || (!bHandleCurvedEdges && !bHandleStraightEdges)) 3034 { 3035 // nothing to do: 3036 // - less than two points -> no edge at all 3037 // - less than two nSubEdges -> no resegment necessary 3038 // - neither bHandleCurvedEdges nor bHandleStraightEdges -> nothing to do 3039 return rCandidate; 3040 } 3041 else 3042 { 3043 B2DPolygon aRetval; 3044 const sal_uInt32 nEdgeCount(rCandidate.isClosed() ? nPointCount : nPointCount - 1); 3045 B2DCubicBezier aCurrentEdge; 3046 3047 // prepare first edge and add start point to target 3048 aCurrentEdge.setStartPoint(rCandidate.getB2DPoint(0)); 3049 aRetval.append(aCurrentEdge.getStartPoint()); 3050 3051 for(sal_uInt32 a(0); a < nEdgeCount; a++) 3052 { 3053 // fill edge 3054 const sal_uInt32 nNextIndex((a + 1) % nPointCount); 3055 aCurrentEdge.setControlPointA(rCandidate.getNextControlPoint(a)); 3056 aCurrentEdge.setControlPointB(rCandidate.getPrevControlPoint(nNextIndex)); 3057 aCurrentEdge.setEndPoint(rCandidate.getB2DPoint(nNextIndex)); 3058 3059 if(aCurrentEdge.isBezier()) 3060 { 3061 if(bHandleCurvedEdges) 3062 { 3063 for(sal_uInt32 b(nSubEdges); b > 1; b--) 3064 { 3065 const double fSplitPoint(1.0 / b); 3066 B2DCubicBezier aLeftPart; 3067 3068 aCurrentEdge.split(fSplitPoint, &aLeftPart, &aCurrentEdge); 3069 aRetval.appendBezierSegment(aLeftPart.getControlPointA(), aLeftPart.getControlPointB(), aLeftPart.getEndPoint()); 3070 } 3071 } 3072 3073 // copy remaining segment to target 3074 aRetval.appendBezierSegment(aCurrentEdge.getControlPointA(), aCurrentEdge.getControlPointB(), aCurrentEdge.getEndPoint()); 3075 } 3076 else 3077 { 3078 if(bHandleStraightEdges) 3079 { 3080 for(sal_uInt32 b(nSubEdges); b > 1; b--) 3081 { 3082 const double fSplitPoint(1.0 / b); 3083 const B2DPoint aSplitPoint(interpolate(aCurrentEdge.getStartPoint(), aCurrentEdge.getEndPoint(), fSplitPoint)); 3084 3085 aRetval.append(aSplitPoint); 3086 aCurrentEdge.setStartPoint(aSplitPoint); 3087 } 3088 } 3089 3090 // copy remaining segment to target 3091 aRetval.append(aCurrentEdge.getEndPoint()); 3092 } 3093 3094 // prepare next step 3095 aCurrentEdge.setStartPoint(aCurrentEdge.getEndPoint()); 3096 } 3097 3098 // copy closed flag and return 3099 aRetval.setClosed(rCandidate.isClosed()); 3100 return aRetval; 3101 } 3102 } 3103 interpolate(const B2DPolygon & rOld1,const B2DPolygon & rOld2,double t)3104 B2DPolygon interpolate(const B2DPolygon& rOld1, const B2DPolygon& rOld2, double t) 3105 { 3106 OSL_ENSURE(rOld1.count() == rOld2.count(), "B2DPolygon interpolate: Different geometry (!)"); 3107 3108 if(fTools::lessOrEqual(t, 0.0) || rOld1 == rOld2) 3109 { 3110 return rOld1; 3111 } 3112 else if(fTools::moreOrEqual(t, 1.0)) 3113 { 3114 return rOld2; 3115 } 3116 else 3117 { 3118 B2DPolygon aRetval; 3119 const bool bInterpolateVectors(rOld1.areControlPointsUsed() || rOld2.areControlPointsUsed()); 3120 aRetval.setClosed(rOld1.isClosed() && rOld2.isClosed()); 3121 3122 for(sal_uInt32 a(0L); a < rOld1.count(); a++) 3123 { 3124 aRetval.append(interpolate(rOld1.getB2DPoint(a), rOld2.getB2DPoint(a), t)); 3125 3126 if(bInterpolateVectors) 3127 { 3128 aRetval.setPrevControlPoint(a, interpolate(rOld1.getPrevControlPoint(a), rOld2.getPrevControlPoint(a), t)); 3129 aRetval.setNextControlPoint(a, interpolate(rOld1.getNextControlPoint(a), rOld2.getNextControlPoint(a), t)); 3130 } 3131 } 3132 3133 return aRetval; 3134 } 3135 } 3136 isPolyPolygonEqualRectangle(const B2DPolyPolygon & rPolyPoly,const B2DRange & rRect)3137 bool isPolyPolygonEqualRectangle( const B2DPolyPolygon& rPolyPoly, 3138 const B2DRange& rRect ) 3139 { 3140 // exclude some cheap cases first 3141 if( rPolyPoly.count() != 1 ) 3142 return false; 3143 3144 // fill array with rectangle vertices 3145 const B2DPoint aPoints[] = 3146 { 3147 B2DPoint(rRect.getMinX(),rRect.getMinY()), 3148 B2DPoint(rRect.getMaxX(),rRect.getMinY()), 3149 B2DPoint(rRect.getMaxX(),rRect.getMaxY()), 3150 B2DPoint(rRect.getMinX(),rRect.getMaxY()) 3151 }; 3152 3153 const B2DPolygon& rPoly( rPolyPoly.getB2DPolygon(0) ); 3154 const sal_uInt32 nCount( rPoly.count() ); 3155 const double epsilon = ::std::numeric_limits<double>::epsilon(); 3156 3157 for(unsigned int j=0; j<4; ++j) 3158 { 3159 const B2DPoint &p1 = aPoints[j]; 3160 const B2DPoint &p2 = aPoints[(j+1)%4]; 3161 bool bPointOnBoundary = false; 3162 for( sal_uInt32 i=0; i<nCount; ++i ) 3163 { 3164 const B2DPoint p(rPoly.getB2DPoint(i)); 3165 3166 // 1 | x0 y0 1 | 3167 // A = - | x1 y1 1 | 3168 // 2 | x2 y2 1 | 3169 double fDoubleArea = p2.getX()*p.getY() - 3170 p2.getY()*p.getX() - 3171 p1.getX()*p.getY() + 3172 p1.getY()*p.getX() + 3173 p1.getX()*p2.getY() - 3174 p1.getY()*p2.getX(); 3175 3176 if(fDoubleArea < epsilon) 3177 { 3178 bPointOnBoundary=true; 3179 break; 3180 } 3181 } 3182 if(!(bPointOnBoundary)) 3183 return false; 3184 } 3185 3186 return true; 3187 } 3188 3189 3190 // create simplified version of the original polygon by 3191 // replacing segments with spikes/loops and self intersections 3192 // by several trivial sub-segments createSimplifiedPolygon(const B2DPolygon & rCandidate)3193 B2DPolygon createSimplifiedPolygon( const B2DPolygon& rCandidate ) 3194 { 3195 const sal_uInt32 nCount(rCandidate.count()); 3196 3197 if(nCount && rCandidate.areControlPointsUsed()) 3198 { 3199 const sal_uInt32 nEdgeCount(rCandidate.isClosed() ? nCount : nCount - 1); 3200 B2DPolygon aRetval; 3201 B2DCubicBezier aSegment; 3202 3203 aSegment.setStartPoint(rCandidate.getB2DPoint(0)); 3204 aRetval.append(aSegment.getStartPoint()); 3205 3206 for(sal_uInt32 a(0); a < nEdgeCount; a++) 3207 { 3208 // fill edge 3209 const sal_uInt32 nNextIndex((a + 1) % nCount); 3210 aSegment.setControlPointA(rCandidate.getNextControlPoint(a)); 3211 aSegment.setControlPointB(rCandidate.getPrevControlPoint(nNextIndex)); 3212 aSegment.setEndPoint(rCandidate.getB2DPoint(nNextIndex)); 3213 3214 if(aSegment.isBezier()) 3215 { 3216 double fExtremumPos(0.0); 3217 sal_uInt32 nExtremumCounter(4); 3218 3219 while(nExtremumCounter-- && aSegment.isBezier() && aSegment.getMinimumExtremumPosition(fExtremumPos)) 3220 { 3221 // split off left, now extremum-free part and append 3222 B2DCubicBezier aLeft; 3223 3224 aSegment.split(fExtremumPos, &aLeft, &aSegment); 3225 aLeft.testAndSolveTrivialBezier(); 3226 aSegment.testAndSolveTrivialBezier(); 3227 3228 if(aLeft.isBezier()) 3229 { 3230 aRetval.appendBezierSegment(aLeft.getControlPointA(), aLeft.getControlPointB(), aLeft.getEndPoint()); 3231 } 3232 else 3233 { 3234 aRetval.append(aLeft.getEndPoint()); 3235 } 3236 } 3237 3238 // append (evtl. reduced) rest of Segment 3239 if(aSegment.isBezier()) 3240 { 3241 aRetval.appendBezierSegment(aSegment.getControlPointA(), aSegment.getControlPointB(), aSegment.getEndPoint()); 3242 } 3243 else 3244 { 3245 aRetval.append(aSegment.getEndPoint()); 3246 } 3247 } 3248 else 3249 { 3250 // simple edge, append end point 3251 aRetval.append(aSegment.getEndPoint()); 3252 } 3253 3254 // prepare next edge 3255 aSegment.setStartPoint(aSegment.getEndPoint()); 3256 } 3257 3258 // copy closed flag and check for double points 3259 aRetval.setClosed(rCandidate.isClosed()); 3260 aRetval.removeDoublePoints(); 3261 3262 return aRetval; 3263 } 3264 else 3265 { 3266 return rCandidate; 3267 } 3268 } 3269 3270 // #i76891# simplifyCurveSegments(const B2DPolygon & rCandidate)3271 B2DPolygon simplifyCurveSegments(const B2DPolygon& rCandidate) 3272 { 3273 const sal_uInt32 nPointCount(rCandidate.count()); 3274 3275 if(nPointCount && rCandidate.areControlPointsUsed()) 3276 { 3277 // prepare loop 3278 const sal_uInt32 nEdgeCount(rCandidate.isClosed() ? nPointCount : nPointCount - 1); 3279 B2DPolygon aRetval; 3280 B2DCubicBezier aBezier; 3281 aBezier.setStartPoint(rCandidate.getB2DPoint(0)); 3282 3283 // try to avoid costly reallocations 3284 aRetval.reserve( nEdgeCount+1); 3285 3286 // add start point 3287 aRetval.append(aBezier.getStartPoint()); 3288 3289 for(sal_uInt32 a(0L); a < nEdgeCount; a++) 3290 { 3291 // get values for edge 3292 const sal_uInt32 nNextIndex((a + 1) % nPointCount); 3293 aBezier.setEndPoint(rCandidate.getB2DPoint(nNextIndex)); 3294 aBezier.setControlPointA(rCandidate.getNextControlPoint(a)); 3295 aBezier.setControlPointB(rCandidate.getPrevControlPoint(nNextIndex)); 3296 aBezier.testAndSolveTrivialBezier(); 3297 3298 // still bezier? 3299 if(aBezier.isBezier()) 3300 { 3301 // add edge with control vectors 3302 aRetval.appendBezierSegment(aBezier.getControlPointA(), aBezier.getControlPointB(), aBezier.getEndPoint()); 3303 } 3304 else 3305 { 3306 // add edge 3307 aRetval.append(aBezier.getEndPoint()); 3308 } 3309 3310 // next point 3311 aBezier.setStartPoint(aBezier.getEndPoint()); 3312 } 3313 3314 if(rCandidate.isClosed()) 3315 { 3316 // set closed flag, rescue control point and correct last double point 3317 closeWithGeometryChange(aRetval); 3318 } 3319 3320 return aRetval; 3321 } 3322 else 3323 { 3324 return rCandidate; 3325 } 3326 } 3327 3328 // makes the given indexed point the new polygon start point. To do that, the points in the 3329 // polygon will be rotated. This is only valid for closed polygons, for non-closed ones 3330 // an assertion will be triggered makeStartPoint(const B2DPolygon & rCandidate,sal_uInt32 nIndexOfNewStatPoint)3331 B2DPolygon makeStartPoint(const B2DPolygon& rCandidate, sal_uInt32 nIndexOfNewStatPoint) 3332 { 3333 const sal_uInt32 nPointCount(rCandidate.count()); 3334 3335 if(nPointCount > 2 && nIndexOfNewStatPoint != 0 && nIndexOfNewStatPoint < nPointCount) 3336 { 3337 OSL_ENSURE(rCandidate.isClosed(), "makeStartPoint: only valid for closed polygons (!)"); 3338 B2DPolygon aRetval; 3339 3340 for(sal_uInt32 a(0); a < nPointCount; a++) 3341 { 3342 const sal_uInt32 nSourceIndex((a + nIndexOfNewStatPoint) % nPointCount); 3343 aRetval.append(rCandidate.getB2DPoint(nSourceIndex)); 3344 3345 if(rCandidate.areControlPointsUsed()) 3346 { 3347 aRetval.setPrevControlPoint(a, rCandidate.getPrevControlPoint(nSourceIndex)); 3348 aRetval.setNextControlPoint(a, rCandidate.getNextControlPoint(nSourceIndex)); 3349 } 3350 } 3351 3352 return aRetval; 3353 } 3354 3355 return rCandidate; 3356 } 3357 createEdgesOfGivenLength(const B2DPolygon & rCandidate,double fLength,double fStart,double fEnd)3358 B2DPolygon createEdgesOfGivenLength(const B2DPolygon& rCandidate, double fLength, double fStart, double fEnd) 3359 { 3360 B2DPolygon aRetval; 3361 3362 if(fLength < 0.0) 3363 { 3364 fLength = 0.0; 3365 } 3366 3367 if(!fTools::equalZero(fLength)) 3368 { 3369 if(fStart < 0.0) 3370 { 3371 fStart = 0.0; 3372 } 3373 3374 if(fEnd < 0.0) 3375 { 3376 fEnd = 0.0; 3377 } 3378 3379 if(fEnd < fStart) 3380 { 3381 fEnd = fStart; 3382 } 3383 3384 // iterate and consume pieces with fLength. First subdivide to reduce input to line segments 3385 const B2DPolygon aCandidate(rCandidate.areControlPointsUsed() ? rCandidate.getDefaultAdaptiveSubdivision() : rCandidate); 3386 const sal_uInt32 nPointCount(aCandidate.count()); 3387 3388 if(nPointCount > 1) 3389 { 3390 const bool bEndActive(!fTools::equalZero(fEnd)); 3391 const sal_uInt32 nEdgeCount(aCandidate.isClosed() ? nPointCount : nPointCount - 1); 3392 B2DPoint aCurrent(aCandidate.getB2DPoint(0)); 3393 double fPositionInEdge(fStart); 3394 double fAbsolutePosition(fStart); 3395 3396 for(sal_uInt32 a(0); a < nEdgeCount; a++) 3397 { 3398 const sal_uInt32 nNextIndex((a + 1) % nPointCount); 3399 const B2DPoint aNext(aCandidate.getB2DPoint(nNextIndex)); 3400 const B2DVector aEdge(aNext - aCurrent); 3401 double fEdgeLength(aEdge.getLength()); 3402 3403 if(!fTools::equalZero(fEdgeLength)) 3404 { 3405 while(fTools::less(fPositionInEdge, fEdgeLength)) 3406 { 3407 // move position on edge forward as long as on edge 3408 const double fScalar(fPositionInEdge / fEdgeLength); 3409 aRetval.append(aCurrent + (aEdge * fScalar)); 3410 fPositionInEdge += fLength; 3411 3412 if(bEndActive) 3413 { 3414 fAbsolutePosition += fLength; 3415 3416 if(fTools::more(fAbsolutePosition, fEnd)) 3417 { 3418 break; 3419 } 3420 } 3421 } 3422 3423 // substract length of current edge 3424 fPositionInEdge -= fEdgeLength; 3425 } 3426 3427 if(bEndActive && fTools::more(fAbsolutePosition, fEnd)) 3428 { 3429 break; 3430 } 3431 3432 // prepare next step 3433 aCurrent = aNext; 3434 } 3435 3436 // keep closed state 3437 aRetval.setClosed(aCandidate.isClosed()); 3438 } 3439 else 3440 { 3441 // source polygon has only one point, return unchanged 3442 aRetval = aCandidate; 3443 } 3444 } 3445 3446 return aRetval; 3447 } 3448 createWaveline(const B2DPolygon & rCandidate,double fWaveWidth,double fWaveHeight)3449 B2DPolygon createWaveline(const B2DPolygon& rCandidate, double fWaveWidth, double fWaveHeight) 3450 { 3451 B2DPolygon aRetval; 3452 3453 if(fWaveWidth < 0.0) 3454 { 3455 fWaveWidth = 0.0; 3456 } 3457 3458 if(fWaveHeight < 0.0) 3459 { 3460 fWaveHeight = 0.0; 3461 } 3462 3463 const bool bHasWidth(!fTools::equalZero(fWaveWidth)); 3464 const bool bHasHeight(!fTools::equalZero(fWaveHeight)); 3465 3466 if(bHasWidth) 3467 { 3468 if(bHasHeight) 3469 { 3470 // width and height, create waveline. First subdivide to reduce input to line segments 3471 // of WaveWidth. Last segment may be missing. If this turns out to be a problem, it 3472 // may be added here again using the original last point from rCandidate. It may 3473 // also be the case that rCandidate was closed. To simplify things it is handled here 3474 // as if it was opened. 3475 // Result from createEdgesOfGivenLength contains no curved segments, handle as straight 3476 // edges. 3477 const B2DPolygon aEqualLenghEdges(createEdgesOfGivenLength(rCandidate, fWaveWidth)); 3478 const sal_uInt32 nPointCount(aEqualLenghEdges.count()); 3479 3480 if(nPointCount > 1) 3481 { 3482 // iterate over straight edges, add start point 3483 B2DPoint aCurrent(aEqualLenghEdges.getB2DPoint(0)); 3484 aRetval.append(aCurrent); 3485 3486 for(sal_uInt32 a(0); a < nPointCount - 1; a++) 3487 { 3488 const sal_uInt32 nNextIndex((a + 1) % nPointCount); 3489 const B2DPoint aNext(aEqualLenghEdges.getB2DPoint(nNextIndex)); 3490 const B2DVector aEdge(aNext - aCurrent); 3491 const B2DVector aPerpendicular(getNormalizedPerpendicular(aEdge)); 3492 const B2DVector aControlOffset((aEdge * 0.467308) - (aPerpendicular * fWaveHeight)); 3493 3494 // add curve segment 3495 aRetval.appendBezierSegment( 3496 aCurrent + aControlOffset, 3497 aNext - aControlOffset, 3498 aNext); 3499 3500 // prepare next step 3501 aCurrent = aNext; 3502 } 3503 } 3504 } 3505 else 3506 { 3507 // width but no height -> return original polygon 3508 aRetval = rCandidate; 3509 } 3510 } 3511 else 3512 { 3513 // no width -> no waveline, stay empty and return 3514 } 3515 3516 return aRetval; 3517 } 3518 3519 ////////////////////////////////////////////////////////////////////// 3520 // comparators with tolerance for 2D Polygons 3521 equal(const B2DPolygon & rCandidateA,const B2DPolygon & rCandidateB,const double & rfSmallValue)3522 bool equal(const B2DPolygon& rCandidateA, const B2DPolygon& rCandidateB, const double& rfSmallValue) 3523 { 3524 const sal_uInt32 nPointCount(rCandidateA.count()); 3525 3526 if(nPointCount != rCandidateB.count()) 3527 return false; 3528 3529 const bool bClosed(rCandidateA.isClosed()); 3530 3531 if(bClosed != rCandidateB.isClosed()) 3532 return false; 3533 3534 const bool bAreControlPointsUsed(rCandidateA.areControlPointsUsed()); 3535 3536 if(bAreControlPointsUsed != rCandidateB.areControlPointsUsed()) 3537 return false; 3538 3539 for(sal_uInt32 a(0); a < nPointCount; a++) 3540 { 3541 const B2DPoint aPoint(rCandidateA.getB2DPoint(a)); 3542 3543 if(!aPoint.equal(rCandidateB.getB2DPoint(a), rfSmallValue)) 3544 return false; 3545 3546 if(bAreControlPointsUsed) 3547 { 3548 const basegfx::B2DPoint aPrev(rCandidateA.getPrevControlPoint(a)); 3549 3550 if(!aPrev.equal(rCandidateB.getPrevControlPoint(a), rfSmallValue)) 3551 return false; 3552 3553 const basegfx::B2DPoint aNext(rCandidateA.getNextControlPoint(a)); 3554 3555 if(!aNext.equal(rCandidateB.getNextControlPoint(a), rfSmallValue)) 3556 return false; 3557 } 3558 } 3559 3560 return true; 3561 } 3562 equal(const B2DPolygon & rCandidateA,const B2DPolygon & rCandidateB)3563 bool equal(const B2DPolygon& rCandidateA, const B2DPolygon& rCandidateB) 3564 { 3565 const double fSmallValue(fTools::getSmallValue()); 3566 3567 return equal(rCandidateA, rCandidateB, fSmallValue); 3568 } 3569 3570 // snap points of horizontal or vertical edges to discrete values snapPointsOfHorizontalOrVerticalEdges(const B2DPolygon & rCandidate)3571 B2DPolygon snapPointsOfHorizontalOrVerticalEdges(const B2DPolygon& rCandidate) 3572 { 3573 const sal_uInt32 nPointCount(rCandidate.count()); 3574 3575 if(nPointCount > 1) 3576 { 3577 // Start by copying the source polygon to get a writeable copy. The closed state is 3578 // copied by aRetval's initialisation, too, so no need to copy it in this method 3579 B2DPolygon aRetval(rCandidate); 3580 3581 // prepare geometry data. Get rounded from original 3582 B2ITuple aPrevTuple(basegfx::fround(rCandidate.getB2DPoint(nPointCount - 1))); 3583 B2DPoint aCurrPoint(rCandidate.getB2DPoint(0)); 3584 B2ITuple aCurrTuple(basegfx::fround(aCurrPoint)); 3585 3586 // loop over all points. This will also snap the implicit closing edge 3587 // even when not closed, but that's no problem here 3588 for(sal_uInt32 a(0); a < nPointCount; a++) 3589 { 3590 // get next point. Get rounded from original 3591 const bool bLastRun(a + 1 == nPointCount); 3592 const sal_uInt32 nNextIndex(bLastRun ? 0 : a + 1); 3593 const B2DPoint aNextPoint(rCandidate.getB2DPoint(nNextIndex)); 3594 const B2ITuple aNextTuple(basegfx::fround(aNextPoint)); 3595 3596 // get the states 3597 const bool bPrevVertical(aPrevTuple.getX() == aCurrTuple.getX()); 3598 const bool bNextVertical(aNextTuple.getX() == aCurrTuple.getX()); 3599 const bool bPrevHorizontal(aPrevTuple.getY() == aCurrTuple.getY()); 3600 const bool bNextHorizontal(aNextTuple.getY() == aCurrTuple.getY()); 3601 const bool bSnapX(bPrevVertical || bNextVertical); 3602 const bool bSnapY(bPrevHorizontal || bNextHorizontal); 3603 3604 if(bSnapX || bSnapY) 3605 { 3606 const B2DPoint aSnappedPoint( 3607 bSnapX ? aCurrTuple.getX() : aCurrPoint.getX(), 3608 bSnapY ? aCurrTuple.getY() : aCurrPoint.getY()); 3609 3610 aRetval.setB2DPoint(a, aSnappedPoint); 3611 } 3612 3613 // prepare next point 3614 if(!bLastRun) 3615 { 3616 aPrevTuple = aCurrTuple; 3617 aCurrPoint = aNextPoint; 3618 aCurrTuple = aNextTuple; 3619 } 3620 } 3621 3622 return aRetval; 3623 } 3624 else 3625 { 3626 return rCandidate; 3627 } 3628 } 3629 containsOnlyHorizontalAndVerticalEdges(const B2DPolygon & rCandidate)3630 bool containsOnlyHorizontalAndVerticalEdges(const B2DPolygon& rCandidate) 3631 { 3632 if(rCandidate.areControlPointsUsed()) 3633 { 3634 return false; 3635 } 3636 3637 const sal_uInt32 nPointCount(rCandidate.count()); 3638 3639 if(nPointCount < 2) 3640 { 3641 return true; 3642 } 3643 3644 const sal_uInt32 nEdgeCount(rCandidate.isClosed() ? nPointCount + 1 : nPointCount); 3645 basegfx::B2DPoint aLast(rCandidate.getB2DPoint(0)); 3646 3647 for(sal_uInt32 a(1); a < nEdgeCount; a++) 3648 { 3649 const sal_uInt32 nNextIndex(a % nPointCount); 3650 const basegfx::B2DPoint aCurrent(rCandidate.getB2DPoint(nNextIndex)); 3651 3652 if(!basegfx::fTools::equal(aLast.getX(), aCurrent.getX()) && !basegfx::fTools::equal(aLast.getY(), aCurrent.getY())) 3653 { 3654 return false; 3655 } 3656 3657 aLast = aCurrent; 3658 } 3659 3660 return true; 3661 } 3662 getTangentEnteringPoint(const B2DPolygon & rCandidate,sal_uInt32 nIndex)3663 B2DVector getTangentEnteringPoint(const B2DPolygon& rCandidate, sal_uInt32 nIndex) 3664 { 3665 B2DVector aRetval(0.0, 0.0); 3666 const sal_uInt32 nCount(rCandidate.count()); 3667 3668 if(nIndex >= nCount) 3669 { 3670 // out of range 3671 return aRetval; 3672 } 3673 3674 // start immediately at prev point compared to nIndex 3675 const bool bClosed(rCandidate.isClosed()); 3676 sal_uInt32 nPrev(bClosed ? (nIndex + nCount - 1) % nCount : nIndex ? nIndex - 1 : nIndex); 3677 3678 if(nPrev == nIndex) 3679 { 3680 // no previous, done 3681 return aRetval; 3682 } 3683 3684 B2DCubicBezier aSegment; 3685 3686 // go backward in the polygon; if closed, maximal back to start index (nIndex); if not closed, 3687 // until zero. Use nIndex as stop criteria 3688 while(nPrev != nIndex) 3689 { 3690 // get BezierSegment and tangent at the *end* of segment 3691 rCandidate.getBezierSegment(nPrev, aSegment); 3692 aRetval = aSegment.getTangent(1.0); 3693 3694 if(!aRetval.equalZero()) 3695 { 3696 // if we have a tangent, return it 3697 return aRetval; 3698 } 3699 3700 // prepare index before checked one 3701 nPrev = bClosed ? (nPrev + nCount - 1) % nCount : nPrev ? nPrev - 1 : nIndex; 3702 } 3703 3704 return aRetval; 3705 } 3706 getTangentLeavingPoint(const B2DPolygon & rCandidate,sal_uInt32 nIndex)3707 B2DVector getTangentLeavingPoint(const B2DPolygon& rCandidate, sal_uInt32 nIndex) 3708 { 3709 B2DVector aRetval(0.0, 0.0); 3710 const sal_uInt32 nCount(rCandidate.count()); 3711 3712 if(nIndex >= nCount) 3713 { 3714 // out of range 3715 return aRetval; 3716 } 3717 3718 // start at nIndex 3719 const bool bClosed(rCandidate.isClosed()); 3720 sal_uInt32 nCurrent(nIndex); 3721 B2DCubicBezier aSegment; 3722 3723 // go forward; if closed, do this until once around and back at start index (nIndex); if not 3724 // closed, until last point (nCount - 1). Use nIndex as stop criteria 3725 do 3726 { 3727 // get BezierSegment and tangent at the *beginning* of segment 3728 rCandidate.getBezierSegment(nCurrent, aSegment); 3729 aRetval = aSegment.getTangent(0.0); 3730 3731 if(!aRetval.equalZero()) 3732 { 3733 // if we have a tangent, return it 3734 return aRetval; 3735 } 3736 3737 // prepare next index 3738 nCurrent = bClosed ? (nCurrent + 1) % nCount : nCurrent + 1 < nCount ? nCurrent + 1 : nIndex; 3739 } 3740 while(nCurrent != nIndex); 3741 3742 return aRetval; 3743 } 3744 3745 ////////////////////////////////////////////////////////////////////////////// 3746 // converters for com::sun::star::drawing::PointSequence 3747 UnoPointSequenceToB2DPolygon(const com::sun::star::drawing::PointSequence & rPointSequenceSource,bool bCheckClosed)3748 B2DPolygon UnoPointSequenceToB2DPolygon( 3749 const com::sun::star::drawing::PointSequence& rPointSequenceSource, 3750 bool bCheckClosed) 3751 { 3752 B2DPolygon aRetval; 3753 const sal_uInt32 nLength(rPointSequenceSource.getLength()); 3754 3755 if(nLength) 3756 { 3757 aRetval.reserve(nLength); 3758 const com::sun::star::awt::Point* pArray = rPointSequenceSource.getConstArray(); 3759 const com::sun::star::awt::Point* pArrayEnd = pArray + rPointSequenceSource.getLength(); 3760 3761 for(;pArray != pArrayEnd; pArray++) 3762 { 3763 aRetval.append(B2DPoint(pArray->X, pArray->Y)); 3764 } 3765 3766 if(bCheckClosed) 3767 { 3768 // check for closed state flag 3769 tools::checkClosed(aRetval); 3770 } 3771 } 3772 3773 return aRetval; 3774 } 3775 B2DPolygonToUnoPointSequence(const B2DPolygon & rPolygon,com::sun::star::drawing::PointSequence & rPointSequenceRetval)3776 void B2DPolygonToUnoPointSequence( 3777 const B2DPolygon& rPolygon, 3778 com::sun::star::drawing::PointSequence& rPointSequenceRetval) 3779 { 3780 B2DPolygon aPolygon(rPolygon); 3781 3782 if(aPolygon.areControlPointsUsed()) 3783 { 3784 OSL_ENSURE(false, "B2DPolygonToUnoPointSequence: Source contains bezier segments, wrong UNO API data type may be used (!)"); 3785 aPolygon = aPolygon.getDefaultAdaptiveSubdivision(); 3786 } 3787 3788 const sal_uInt32 nPointCount(aPolygon.count()); 3789 3790 if(nPointCount) 3791 { 3792 // Take closed state into account, the API polygon still uses the old closed definition 3793 // with last/first point are identical (cannot hold information about open polygons with identical 3794 // first and last point, though) 3795 const bool bIsClosed(aPolygon.isClosed()); 3796 3797 rPointSequenceRetval.realloc(bIsClosed ? nPointCount + 1 : nPointCount); 3798 com::sun::star::awt::Point* pSequence = rPointSequenceRetval.getArray(); 3799 3800 for(sal_uInt32 b(0); b < nPointCount; b++) 3801 { 3802 const B2DPoint aPoint(aPolygon.getB2DPoint(b)); 3803 const com::sun::star::awt::Point aAPIPoint(fround(aPoint.getX()), fround(aPoint.getY())); 3804 3805 *pSequence = aAPIPoint; 3806 pSequence++; 3807 } 3808 3809 // copy first point if closed 3810 if(bIsClosed) 3811 { 3812 *pSequence = *rPointSequenceRetval.getArray(); 3813 } 3814 } 3815 else 3816 { 3817 rPointSequenceRetval.realloc(0); 3818 } 3819 } 3820 3821 ////////////////////////////////////////////////////////////////////////////// 3822 // converters for com::sun::star::drawing::PointSequence and 3823 // com::sun::star::drawing::FlagSequence to B2DPolygon (curved polygons) 3824 UnoPolygonBezierCoordsToB2DPolygon(const com::sun::star::drawing::PointSequence & rPointSequenceSource,const com::sun::star::drawing::FlagSequence & rFlagSequenceSource,bool bCheckClosed)3825 B2DPolygon UnoPolygonBezierCoordsToB2DPolygon( 3826 const com::sun::star::drawing::PointSequence& rPointSequenceSource, 3827 const com::sun::star::drawing::FlagSequence& rFlagSequenceSource, 3828 bool bCheckClosed) 3829 { 3830 const sal_uInt32 nCount((sal_uInt32)rPointSequenceSource.getLength()); 3831 OSL_ENSURE(nCount == (sal_uInt32)rFlagSequenceSource.getLength(), 3832 "UnoPolygonBezierCoordsToB2DPolygon: Unequal count of Points and Flags (!)"); 3833 3834 // prepare new polygon 3835 B2DPolygon aRetval; 3836 const com::sun::star::awt::Point* pPointSequence = rPointSequenceSource.getConstArray(); 3837 const com::sun::star::drawing::PolygonFlags* pFlagSequence = rFlagSequenceSource.getConstArray(); 3838 3839 // get first point and flag 3840 B2DPoint aNewCoordinatePair(pPointSequence->X, pPointSequence->Y); pPointSequence++; 3841 com::sun::star::drawing::PolygonFlags ePolygonFlag(*pFlagSequence); pFlagSequence++; 3842 B2DPoint aControlA; 3843 B2DPoint aControlB; 3844 3845 // first point is not allowed to be a control point 3846 OSL_ENSURE(com::sun::star::drawing::PolygonFlags_CONTROL != ePolygonFlag, 3847 "UnoPolygonBezierCoordsToB2DPolygon: Start point is a control point, illegal input polygon (!)"); 3848 3849 // add first point as start point 3850 aRetval.append(aNewCoordinatePair); 3851 3852 for(sal_uInt32 b(1); b < nCount;) 3853 { 3854 // prepare loop 3855 bool bControlA(false); 3856 bool bControlB(false); 3857 3858 // get next point and flag 3859 aNewCoordinatePair = B2DPoint(pPointSequence->X, pPointSequence->Y); 3860 ePolygonFlag = *pFlagSequence; 3861 pPointSequence++; pFlagSequence++; b++; 3862 3863 if(b < nCount && com::sun::star::drawing::PolygonFlags_CONTROL == ePolygonFlag) 3864 { 3865 aControlA = aNewCoordinatePair; 3866 bControlA = true; 3867 3868 // get next point and flag 3869 aNewCoordinatePair = B2DPoint(pPointSequence->X, pPointSequence->Y); 3870 ePolygonFlag = *pFlagSequence; 3871 pPointSequence++; pFlagSequence++; b++; 3872 } 3873 3874 if(b < nCount && com::sun::star::drawing::PolygonFlags_CONTROL == ePolygonFlag) 3875 { 3876 aControlB = aNewCoordinatePair; 3877 bControlB = true; 3878 3879 // get next point and flag 3880 aNewCoordinatePair = B2DPoint(pPointSequence->X, pPointSequence->Y); 3881 ePolygonFlag = *pFlagSequence; 3882 pPointSequence++; pFlagSequence++; b++; 3883 } 3884 3885 // two or no control points are consumed, another one would be an error. 3886 // It's also an error if only one control point was read 3887 OSL_ENSURE(com::sun::star::drawing::PolygonFlags_CONTROL != ePolygonFlag && bControlA == bControlB, 3888 "UnoPolygonBezierCoordsToB2DPolygon: Illegal source polygon (!)"); 3889 3890 // the previous writes used the B2DPolyPoygon -> PolyPolygon converter 3891 // which did not create minimal PolyPolygons, but created all control points 3892 // as null vectors (identical points). Because of the former P(CA)(CB)-norm of 3893 // B2DPolygon and it's unused sign of being the zero-vector and CA and CB being 3894 // relative to P, an empty edge was exported as P == CA == CB. Luckily, the new 3895 // export format can be read without errors by the old OOo-versions, so we need only 3896 // to correct here at read and do not need to export a wrong but compatible version 3897 // for the future. 3898 if(bControlA 3899 && aControlA.equal(aControlB) 3900 && aControlA.equal(aRetval.getB2DPoint(aRetval.count() - 1))) 3901 { 3902 bControlA = bControlB = false; 3903 } 3904 3905 if(bControlA) 3906 { 3907 // add bezier edge 3908 aRetval.appendBezierSegment(aControlA, aControlB, aNewCoordinatePair); 3909 } 3910 else 3911 { 3912 // add edge 3913 aRetval.append(aNewCoordinatePair); 3914 } 3915 } 3916 3917 // #i72807# API import uses old line start/end-equal definition for closed, 3918 // so we need to correct this to closed state here 3919 if(bCheckClosed) 3920 { 3921 checkClosed(aRetval); 3922 } 3923 3924 return aRetval; 3925 } 3926 B2DPolygonToUnoPolygonBezierCoords(const B2DPolygon & rPolygon,com::sun::star::drawing::PointSequence & rPointSequenceRetval,com::sun::star::drawing::FlagSequence & rFlagSequenceRetval)3927 void B2DPolygonToUnoPolygonBezierCoords( 3928 const B2DPolygon& rPolygon, 3929 com::sun::star::drawing::PointSequence& rPointSequenceRetval, 3930 com::sun::star::drawing::FlagSequence& rFlagSequenceRetval) 3931 { 3932 const sal_uInt32 nPointCount(rPolygon.count()); 3933 3934 if(nPointCount) 3935 { 3936 const bool bCurve(rPolygon.areControlPointsUsed()); 3937 const bool bClosed(rPolygon.isClosed()); 3938 3939 if(nPointCount) 3940 { 3941 if(bCurve) 3942 { 3943 // calculate target point count 3944 const sal_uInt32 nLoopCount(bClosed ? nPointCount : (nPointCount ? nPointCount - 1 : 0)); 3945 3946 if(nLoopCount) 3947 { 3948 // prepare target data. The real needed number of target points (and flags) 3949 // could only be calculated by using two loops, so use dynamic memory 3950 std::vector< com::sun::star::awt::Point > aCollectPoints; 3951 std::vector< com::sun::star::drawing::PolygonFlags > aCollectFlags; 3952 3953 // reserve maximum creatable points 3954 const sal_uInt32 nMaxTargetCount((nLoopCount * 3) + 1); 3955 aCollectPoints.reserve(nMaxTargetCount); 3956 aCollectFlags.reserve(nMaxTargetCount); 3957 3958 // prepare current bezier segment by setting start point 3959 B2DCubicBezier aBezierSegment; 3960 aBezierSegment.setStartPoint(rPolygon.getB2DPoint(0)); 3961 3962 for(sal_uInt32 a(0); a < nLoopCount; a++) 3963 { 3964 // add current point (always) and remember StartPointIndex for evtl. later corrections 3965 const sal_uInt32 nStartPointIndex(aCollectPoints.size()); 3966 aCollectPoints.push_back( 3967 com::sun::star::awt::Point( 3968 fround(aBezierSegment.getStartPoint().getX()), 3969 fround(aBezierSegment.getStartPoint().getY()))); 3970 aCollectFlags.push_back(com::sun::star::drawing::PolygonFlags_NORMAL); 3971 3972 // prepare next segment 3973 const sal_uInt32 nNextIndex((a + 1) % nPointCount); 3974 aBezierSegment.setEndPoint(rPolygon.getB2DPoint(nNextIndex)); 3975 aBezierSegment.setControlPointA(rPolygon.getNextControlPoint(a)); 3976 aBezierSegment.setControlPointB(rPolygon.getPrevControlPoint(nNextIndex)); 3977 3978 if(aBezierSegment.isBezier()) 3979 { 3980 // if bezier is used, add always two control points due to the old schema 3981 aCollectPoints.push_back( 3982 com::sun::star::awt::Point( 3983 fround(aBezierSegment.getControlPointA().getX()), 3984 fround(aBezierSegment.getControlPointA().getY()))); 3985 aCollectFlags.push_back(com::sun::star::drawing::PolygonFlags_CONTROL); 3986 3987 aCollectPoints.push_back( 3988 com::sun::star::awt::Point( 3989 fround(aBezierSegment.getControlPointB().getX()), 3990 fround(aBezierSegment.getControlPointB().getY()))); 3991 aCollectFlags.push_back(com::sun::star::drawing::PolygonFlags_CONTROL); 3992 } 3993 3994 // test continuity with previous control point to set flag value 3995 if(aBezierSegment.getControlPointA() != aBezierSegment.getStartPoint() && (bClosed || a)) 3996 { 3997 const B2VectorContinuity eCont(rPolygon.getContinuityInPoint(a)); 3998 3999 if(CONTINUITY_C1 == eCont) 4000 { 4001 aCollectFlags[nStartPointIndex] = com::sun::star::drawing::PolygonFlags_SMOOTH; 4002 } 4003 else if(CONTINUITY_C2 == eCont) 4004 { 4005 aCollectFlags[nStartPointIndex] = com::sun::star::drawing::PolygonFlags_SYMMETRIC; 4006 } 4007 } 4008 4009 // prepare next loop 4010 aBezierSegment.setStartPoint(aBezierSegment.getEndPoint()); 4011 } 4012 4013 if(bClosed) 4014 { 4015 // add first point again as closing point due to old definition 4016 aCollectPoints.push_back(aCollectPoints[0]); 4017 aCollectFlags.push_back(com::sun::star::drawing::PolygonFlags_NORMAL); 4018 } 4019 else 4020 { 4021 // add last point as closing point 4022 const B2DPoint aClosingPoint(rPolygon.getB2DPoint(nPointCount - 1L)); 4023 aCollectPoints.push_back( 4024 com::sun::star::awt::Point( 4025 fround(aClosingPoint.getX()), 4026 fround(aClosingPoint.getY()))); 4027 aCollectFlags.push_back(com::sun::star::drawing::PolygonFlags_NORMAL); 4028 } 4029 4030 // copy collected data to target arrays 4031 const sal_uInt32 nTargetCount(aCollectPoints.size()); 4032 OSL_ENSURE(nTargetCount == aCollectFlags.size(), "Unequal Point and Flag count (!)"); 4033 4034 rPointSequenceRetval.realloc((sal_Int32)nTargetCount); 4035 rFlagSequenceRetval.realloc((sal_Int32)nTargetCount); 4036 com::sun::star::awt::Point* pPointSequence = rPointSequenceRetval.getArray(); 4037 com::sun::star::drawing::PolygonFlags* pFlagSequence = rFlagSequenceRetval.getArray(); 4038 4039 for(sal_uInt32 a(0); a < nTargetCount; a++) 4040 { 4041 *pPointSequence = aCollectPoints[a]; 4042 *pFlagSequence = aCollectFlags[a]; 4043 pPointSequence++; 4044 pFlagSequence++; 4045 } 4046 } 4047 } 4048 else 4049 { 4050 // straightforward point list creation 4051 const sal_uInt32 nTargetCount(nPointCount + (bClosed ? 1 : 0)); 4052 4053 rPointSequenceRetval.realloc((sal_Int32)nTargetCount); 4054 rFlagSequenceRetval.realloc((sal_Int32)nTargetCount); 4055 4056 com::sun::star::awt::Point* pPointSequence = rPointSequenceRetval.getArray(); 4057 com::sun::star::drawing::PolygonFlags* pFlagSequence = rFlagSequenceRetval.getArray(); 4058 4059 for(sal_uInt32 a(0); a < nPointCount; a++) 4060 { 4061 const B2DPoint aB2DPoint(rPolygon.getB2DPoint(a)); 4062 const com::sun::star::awt::Point aAPIPoint( 4063 fround(aB2DPoint.getX()), 4064 fround(aB2DPoint.getY())); 4065 4066 *pPointSequence = aAPIPoint; 4067 *pFlagSequence = com::sun::star::drawing::PolygonFlags_NORMAL; 4068 pPointSequence++; 4069 pFlagSequence++; 4070 } 4071 4072 if(bClosed) 4073 { 4074 // add first point as closing point 4075 *pPointSequence = *rPointSequenceRetval.getConstArray(); 4076 *pFlagSequence = com::sun::star::drawing::PolygonFlags_NORMAL; 4077 } 4078 } 4079 } 4080 } 4081 else 4082 { 4083 rPointSequenceRetval.realloc(0); 4084 rFlagSequenceRetval.realloc(0); 4085 } 4086 } 4087 4088 } // end of namespace tools 4089 } // end of namespace basegfx 4090 4091 ////////////////////////////////////////////////////////////////////////////// 4092 // eof 4093