1 /************************************************************************* 2 * 3 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. 4 * 5 * Copyright 2000, 2010 Oracle and/or its affiliates. 6 * 7 * OpenOffice.org - a multi-platform office productivity suite 8 * 9 * This file is part of OpenOffice.org. 10 * 11 * OpenOffice.org is free software: you can redistribute it and/or modify 12 * it under the terms of the GNU Lesser General Public License version 3 13 * only, as published by the Free Software Foundation. 14 * 15 * OpenOffice.org is distributed in the hope that it will be useful, 16 * but WITHOUT ANY WARRANTY; without even the implied warranty of 17 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 18 * GNU Lesser General Public License version 3 for more details 19 * (a copy is included in the LICENSE file that accompanied this code). 20 * 21 * You should have received a copy of the GNU Lesser General Public License 22 * version 3 along with OpenOffice.org. If not, see 23 * <http://www.openoffice.org/license.html> 24 * for a copy of the LGPLv3 License. 25 * 26 ************************************************************************/ 27 28 // MARKER(update_precomp.py): autogen include statement, do not remove 29 #include "precompiled_vcl.hxx" 30 #include <tools/debug.hxx> 31 #include <vcl/salbtype.hxx> 32 #include <vcl/regband.hxx> 33 34 #include <algorithm> 35 36 37 // ======================================================================= 38 // 39 // ImplRegionBand 40 // 41 // Jedes Band enthaelt die zwischen der enthaltenen Ober- und Untergrenze 42 // enthaltenen Rechtecke. Bei den Operationen Union, Intersect, XOr und 43 // Exclude werden immer Rechtecke der gleichen Hoehe ausgewerte; die 44 // Grenzen der Baender sind immer so zu waehlen, dasz dies moeglich ist. 45 // 46 // Die Rechtecke in den Baendern werden nach Moeglichkeit zusammengefaszt. 47 // 48 // Bei der Umwandlung von Polygonen werden alle Punkte des Polygons 49 // in die einzelnen Baender eingetragen (sie stehen fuer jedes Band als 50 // Punkte in einer Liste). Nach dem Eintragen der Punkte werden diese 51 // in Rechtecke umgewandelt und die Liste der Punkte geloescht. 52 // 53 // ----------------------------------------------------------------------- 54 55 ImplRegionBand::ImplRegionBand( long nTop, long nBottom ) 56 { 57 // save boundaries 58 mnYTop = nTop; 59 mnYBottom = nBottom; 60 61 // initialize lists 62 mpNextBand = NULL; 63 mpPrevBand = NULL; 64 mpFirstSep = NULL; 65 mpFirstBandPoint = NULL; 66 mbTouched = sal_False; 67 } 68 69 // ----------------------------------------------------------------------- 70 71 ImplRegionBand::ImplRegionBand( 72 const ImplRegionBand& rRegionBand, 73 const bool bIgnorePoints) 74 { 75 // copy boundaries 76 mnYTop = rRegionBand.mnYTop; 77 mnYBottom = rRegionBand.mnYBottom; 78 mbTouched = rRegionBand.mbTouched; 79 80 // initialisation 81 mpNextBand = NULL; 82 mpPrevBand = NULL; 83 mpFirstSep = NULL; 84 mpFirstBandPoint = NULL; 85 86 // copy all elements of the list with separations 87 ImplRegionBandSep* pNewSep; 88 ImplRegionBandSep* pPrevSep = 0; 89 ImplRegionBandSep* pSep = rRegionBand.mpFirstSep; 90 while ( pSep ) 91 { 92 // create new and copy data 93 pNewSep = new ImplRegionBandSep; 94 pNewSep->mnXLeft = pSep->mnXLeft; 95 pNewSep->mnXRight = pSep->mnXRight; 96 pNewSep->mbRemoved = pSep->mbRemoved; 97 pNewSep->mpNextSep = NULL; 98 if ( pSep == rRegionBand.mpFirstSep ) 99 mpFirstSep = pNewSep; 100 else 101 pPrevSep->mpNextSep = pNewSep; 102 103 pPrevSep = pNewSep; 104 pSep = pSep->mpNextSep; 105 } 106 107 if ( ! bIgnorePoints) 108 { 109 // Copy points. 110 ImplRegionBandPoint* pPoint = rRegionBand.mpFirstBandPoint; 111 ImplRegionBandPoint* pPrevPointCopy = NULL; 112 while (pPoint != NULL) 113 { 114 ImplRegionBandPoint* pPointCopy = new ImplRegionBandPoint(); 115 pPointCopy->mnX = pPoint->mnX; 116 pPointCopy->mnLineId = pPoint->mnLineId; 117 pPointCopy->mbEndPoint = pPoint->mbEndPoint; 118 pPointCopy->meLineType = pPoint->meLineType; 119 120 if (pPrevPointCopy != NULL) 121 pPrevPointCopy->mpNextBandPoint = pPointCopy; 122 else 123 mpFirstBandPoint = pPointCopy; 124 125 pPrevPointCopy = pPointCopy; 126 pPoint = pPoint->mpNextBandPoint; 127 } 128 } 129 } 130 131 // ----------------------------------------------------------------------- 132 133 ImplRegionBand::~ImplRegionBand() 134 { 135 DBG_ASSERT( mpFirstBandPoint == NULL, "ImplRegionBand::~ImplRegionBand -> pointlist not empty" ); 136 137 // delete elements of the list 138 ImplRegionBandSep* pSep = mpFirstSep; 139 while ( pSep ) 140 { 141 ImplRegionBandSep* pTempSep = pSep->mpNextSep; 142 delete pSep; 143 pSep = pTempSep; 144 } 145 146 // delete elements of the list 147 ImplRegionBandPoint* pPoint = mpFirstBandPoint; 148 while ( pPoint ) 149 { 150 ImplRegionBandPoint* pTempPoint = pPoint->mpNextBandPoint; 151 delete pPoint; 152 pPoint = pTempPoint; 153 } 154 } 155 156 // ----------------------------------------------------------------------- 157 // 158 // generate separations from lines and process union with existing 159 // separations 160 161 void ImplRegionBand::ProcessPoints() 162 { 163 // check Pointlist 164 ImplRegionBandPoint* pRegionBandPoint = mpFirstBandPoint; 165 while ( pRegionBandPoint ) 166 { 167 // within list? 168 if ( pRegionBandPoint && pRegionBandPoint->mpNextBandPoint ) 169 { 170 // start/stop? 171 if ( pRegionBandPoint->mbEndPoint && pRegionBandPoint->mpNextBandPoint->mbEndPoint ) 172 { 173 // same direction? -> remove next point! 174 if ( pRegionBandPoint->meLineType == pRegionBandPoint->mpNextBandPoint->meLineType ) 175 { 176 ImplRegionBandPoint* pSaveRegionBandPoint = pRegionBandPoint->mpNextBandPoint; 177 pRegionBandPoint->mpNextBandPoint = pRegionBandPoint->mpNextBandPoint->mpNextBandPoint; 178 delete pSaveRegionBandPoint; 179 } 180 } 181 } 182 183 // continue with next element in the list 184 pRegionBandPoint = pRegionBandPoint->mpNextBandPoint; 185 } 186 187 pRegionBandPoint = mpFirstBandPoint; 188 while ( pRegionBandPoint && pRegionBandPoint->mpNextBandPoint ) 189 { 190 Union( pRegionBandPoint->mnX, pRegionBandPoint->mpNextBandPoint->mnX ); 191 192 ImplRegionBandPoint* pNextBandPoint = pRegionBandPoint->mpNextBandPoint->mpNextBandPoint; 193 194 // remove allready processed points 195 delete pRegionBandPoint->mpNextBandPoint; 196 delete pRegionBandPoint; 197 198 // continue with next element in the list 199 pRegionBandPoint = pNextBandPoint; 200 } 201 202 // remove last element if necessary 203 if ( pRegionBandPoint ) 204 delete pRegionBandPoint; 205 206 // list is now empty 207 mpFirstBandPoint = NULL; 208 } 209 210 // ----------------------------------------------------------------------- 211 // 212 // generate separations from lines and process union with existing 213 // separations 214 215 sal_Bool ImplRegionBand::InsertPoint( long nX, long nLineId, 216 sal_Bool bEndPoint, LineType eLineType ) 217 { 218 if ( !mpFirstBandPoint ) 219 { 220 mpFirstBandPoint = new ImplRegionBandPoint; 221 mpFirstBandPoint->mnX = nX; 222 mpFirstBandPoint->mnLineId = nLineId; 223 mpFirstBandPoint->mbEndPoint = bEndPoint; 224 mpFirstBandPoint->meLineType = eLineType; 225 mpFirstBandPoint->mpNextBandPoint = NULL; 226 return sal_True; 227 } 228 229 // look if line allready touched the band 230 ImplRegionBandPoint* pRegionBandPoint = mpFirstBandPoint; 231 ImplRegionBandPoint* pLastTestedRegionBandPoint = NULL; 232 while( pRegionBandPoint ) 233 { 234 if ( pRegionBandPoint->mnLineId == nLineId ) 235 { 236 if ( bEndPoint ) 237 { 238 if( !pRegionBandPoint->mbEndPoint ) 239 { 240 // remove old band point 241 if( !mpFirstBandPoint->mpNextBandPoint ) 242 { 243 // if we've only got one point => replace first point 244 pRegionBandPoint->mnX = nX; 245 pRegionBandPoint->mbEndPoint = sal_True; 246 return sal_True; 247 } 248 else 249 { 250 // remove current point 251 if( !pLastTestedRegionBandPoint ) 252 { 253 // remove and delete old first point 254 ImplRegionBandPoint* pSaveBandPoint = mpFirstBandPoint; 255 mpFirstBandPoint = mpFirstBandPoint->mpNextBandPoint; 256 delete pSaveBandPoint; 257 } 258 else 259 { 260 // remove and delete current band point 261 pLastTestedRegionBandPoint->mpNextBandPoint = pRegionBandPoint->mpNextBandPoint; 262 delete pRegionBandPoint; 263 } 264 265 break; 266 } 267 } 268 } 269 else 270 return sal_False; 271 } 272 273 // use next element 274 pLastTestedRegionBandPoint = pRegionBandPoint; 275 pRegionBandPoint = pRegionBandPoint->mpNextBandPoint; 276 } 277 278 // search appropriate position and insert point into the list 279 ImplRegionBandPoint* pNewRegionBandPoint; 280 281 pRegionBandPoint = mpFirstBandPoint; 282 pLastTestedRegionBandPoint = NULL; 283 while ( pRegionBandPoint ) 284 { 285 // new point completly left? -> insert as first point 286 if ( nX <= pRegionBandPoint->mnX ) 287 { 288 pNewRegionBandPoint = new ImplRegionBandPoint; 289 pNewRegionBandPoint->mnX = nX; 290 pNewRegionBandPoint->mnLineId = nLineId; 291 pNewRegionBandPoint->mbEndPoint = bEndPoint; 292 pNewRegionBandPoint->meLineType = eLineType; 293 pNewRegionBandPoint->mpNextBandPoint = pRegionBandPoint; 294 295 // connections to the new point 296 if ( !pLastTestedRegionBandPoint ) 297 mpFirstBandPoint = pNewRegionBandPoint; 298 else 299 pLastTestedRegionBandPoint->mpNextBandPoint = pNewRegionBandPoint; 300 301 return sal_True; 302 } 303 304 // use next element 305 pLastTestedRegionBandPoint = pRegionBandPoint; 306 pRegionBandPoint = pRegionBandPoint->mpNextBandPoint; 307 } 308 309 // not inserted -> add to the end of the list 310 pNewRegionBandPoint = new ImplRegionBandPoint; 311 pNewRegionBandPoint->mnX = nX; 312 pNewRegionBandPoint->mnLineId = nLineId; 313 pNewRegionBandPoint->mbEndPoint = bEndPoint; 314 pNewRegionBandPoint->meLineType = eLineType; 315 pNewRegionBandPoint->mpNextBandPoint = NULL; 316 317 // connections to the new point 318 pLastTestedRegionBandPoint->mpNextBandPoint = pNewRegionBandPoint; 319 320 return sal_True; 321 } 322 323 // ----------------------------------------------------------------------- 324 325 void ImplRegionBand::MoveX( long nHorzMove ) 326 { 327 // move all x-separations 328 ImplRegionBandSep* pSep = mpFirstSep; 329 while ( pSep ) 330 { 331 pSep->mnXLeft += nHorzMove; 332 pSep->mnXRight += nHorzMove; 333 pSep = pSep->mpNextSep; 334 } 335 } 336 337 // ----------------------------------------------------------------------- 338 339 void ImplRegionBand::ScaleX( double fHorzScale ) 340 { 341 ImplRegionBandSep* pSep = mpFirstSep; 342 while ( pSep ) 343 { 344 pSep->mnXLeft = FRound( pSep->mnXLeft * fHorzScale ); 345 pSep->mnXRight = FRound( pSep->mnXRight * fHorzScale ); 346 pSep = pSep->mpNextSep; 347 } 348 } 349 350 // ----------------------------------------------------------------------- 351 // 352 // combine overlaping sparations 353 354 sal_Bool ImplRegionBand::OptimizeBand() 355 { 356 ImplRegionBandSep* pPrevSep = 0; 357 ImplRegionBandSep* pSep = mpFirstSep; 358 while ( pSep ) 359 { 360 // remove? 361 if ( pSep->mbRemoved || (pSep->mnXRight < pSep->mnXLeft) ) 362 { 363 ImplRegionBandSep* pOldSep = pSep; 364 if ( pSep == mpFirstSep ) 365 mpFirstSep = pSep->mpNextSep; 366 else 367 pPrevSep->mpNextSep = pSep->mpNextSep; 368 pSep = pSep->mpNextSep; 369 delete pOldSep; 370 continue; 371 } 372 373 // overlaping separations? -> combine! 374 if ( pSep->mpNextSep ) 375 { 376 if ( (pSep->mnXRight+1) >= pSep->mpNextSep->mnXLeft ) 377 { 378 if ( pSep->mpNextSep->mnXRight > pSep->mnXRight ) 379 pSep->mnXRight = pSep->mpNextSep->mnXRight; 380 381 ImplRegionBandSep* pOldSep = pSep->mpNextSep; 382 pSep->mpNextSep = pOldSep->mpNextSep; 383 delete pOldSep; 384 continue; 385 } 386 } 387 388 pPrevSep = pSep; 389 pSep = pSep->mpNextSep; 390 } 391 392 return sal_True; 393 } 394 395 // ----------------------------------------------------------------------- 396 397 void ImplRegionBand::Union( long nXLeft, long nXRight ) 398 { 399 DBG_ASSERT( nXLeft <= nXRight, "ImplRegionBand::Union(): nxLeft > nXRight" ); 400 401 // band empty? -> add element 402 if ( !mpFirstSep ) 403 { 404 mpFirstSep = new ImplRegionBandSep; 405 mpFirstSep->mnXLeft = nXLeft; 406 mpFirstSep->mnXRight = nXRight; 407 mpFirstSep->mbRemoved = sal_False; 408 mpFirstSep->mpNextSep = NULL; 409 return; 410 } 411 412 // process real union 413 ImplRegionBandSep* pNewSep; 414 ImplRegionBandSep* pPrevSep = 0; 415 ImplRegionBandSep* pSep = mpFirstSep; 416 while ( pSep ) 417 { 418 // new separation completely inside? nothing to do! 419 if ( (nXLeft >= pSep->mnXLeft) && (nXRight <= pSep->mnXRight) ) 420 return; 421 422 // new separation completly left? -> new separation! 423 if ( nXRight < pSep->mnXLeft ) 424 { 425 pNewSep = new ImplRegionBandSep; 426 pNewSep->mnXLeft = nXLeft; 427 pNewSep->mnXRight = nXRight; 428 pNewSep->mbRemoved = sal_False; 429 430 pNewSep->mpNextSep = pSep; 431 if ( pSep == mpFirstSep ) 432 mpFirstSep = pNewSep; 433 else 434 pPrevSep->mpNextSep = pNewSep; 435 break; 436 } 437 438 // new separation overlaping from left? -> extend boundary 439 if ( (nXRight >= pSep->mnXLeft) && (nXLeft <= pSep->mnXLeft) ) 440 pSep->mnXLeft = nXLeft; 441 442 // new separation overlaping from right? -> extend boundary 443 if ( (nXLeft <= pSep->mnXRight) && (nXRight > pSep->mnXRight) ) 444 { 445 pSep->mnXRight = nXRight; 446 break; 447 } 448 449 // not inserted, but last element? -> add to the end of the list 450 if ( !pSep->mpNextSep && (nXLeft > pSep->mnXRight) ) 451 { 452 pNewSep = new ImplRegionBandSep; 453 pNewSep->mnXLeft = nXLeft; 454 pNewSep->mnXRight = nXRight; 455 pNewSep->mbRemoved = sal_False; 456 457 pSep->mpNextSep = pNewSep; 458 pNewSep->mpNextSep = NULL; 459 break; 460 } 461 462 pPrevSep = pSep; 463 pSep = pSep->mpNextSep; 464 } 465 466 OptimizeBand(); 467 } 468 469 // ----------------------------------------------------------------------- 470 471 void ImplRegionBand::Intersect( long nXLeft, long nXRight ) 472 { 473 DBG_ASSERT( nXLeft <= nXRight, "ImplRegionBand::Intersect(): nxLeft > nXRight" ); 474 475 // band has been touched 476 mbTouched = sal_True; 477 478 // band empty? -> nothing to do 479 if ( !mpFirstSep ) 480 return; 481 482 // process real intersection 483 ImplRegionBandSep* pSep = mpFirstSep; 484 while ( pSep ) 485 { 486 // new separation completly outside? -> remove separation 487 if ( (nXRight < pSep->mnXLeft) || (nXLeft > pSep->mnXRight) ) 488 // will be removed from the optimizer 489 pSep->mbRemoved = sal_True; 490 491 // new separation overlaping from left? -> reduce right boundary 492 if ( (nXLeft <= pSep->mnXLeft) && 493 (nXRight <= pSep->mnXRight) && 494 (nXRight >= pSep->mnXLeft) ) 495 pSep->mnXRight = nXRight; 496 497 // new separation overlaping from right? -> reduce right boundary 498 if ( (nXLeft >= pSep->mnXLeft) && 499 (nXLeft <= pSep->mnXRight) && 500 (nXRight >= pSep->mnXRight) ) 501 pSep->mnXLeft = nXLeft; 502 503 // new separation within the actual one? -> reduce both boundaries 504 if ( (nXLeft >= pSep->mnXLeft) && (nXRight <= pSep->mnXRight) ) 505 { 506 pSep->mnXRight = nXRight; 507 pSep->mnXLeft = nXLeft; 508 } 509 510 pSep = pSep->mpNextSep; 511 } 512 513 OptimizeBand(); 514 } 515 516 // ----------------------------------------------------------------------- 517 518 void ImplRegionBand::Exclude( long nXLeft, long nXRight ) 519 { 520 DBG_ASSERT( nXLeft <= nXRight, "ImplRegionBand::Exclude(): nxLeft > nXRight" ); 521 522 // band has been touched 523 mbTouched = sal_True; 524 525 // band empty? -> nothing to do 526 if ( !mpFirstSep ) 527 return; 528 529 // process real exclusion 530 ImplRegionBandSep* pNewSep; 531 ImplRegionBandSep* pPrevSep = 0; 532 ImplRegionBandSep* pSep = mpFirstSep; 533 while ( pSep ) 534 { 535 sal_Bool bSepProcessed = sal_False; 536 537 // new separation completely overlapping? -> remove separation 538 if ( (nXLeft <= pSep->mnXLeft) && (nXRight >= pSep->mnXRight) ) 539 { 540 // will be removed from the optimizer 541 pSep->mbRemoved = sal_True; 542 bSepProcessed = sal_True; 543 } 544 545 // new separation overlaping from left? -> reduce boundary 546 if ( !bSepProcessed ) 547 { 548 if ( (nXRight >= pSep->mnXLeft) && (nXLeft <= pSep->mnXLeft) ) 549 { 550 pSep->mnXLeft = nXRight+1; 551 bSepProcessed = sal_True; 552 } 553 } 554 555 // new separation overlaping from right? -> reduce boundary 556 if ( !bSepProcessed ) 557 { 558 if ( (nXLeft <= pSep->mnXRight) && (nXRight > pSep->mnXRight) ) 559 { 560 pSep->mnXRight = nXLeft-1; 561 bSepProcessed = sal_True; 562 } 563 } 564 565 // new separation within the actual one? -> reduce boundary 566 // and add new entry for reminder 567 if ( !bSepProcessed ) 568 { 569 if ( (nXLeft >= pSep->mnXLeft) && (nXRight <= pSep->mnXRight) ) 570 { 571 pNewSep = new ImplRegionBandSep; 572 pNewSep->mnXLeft = pSep->mnXLeft; 573 pNewSep->mnXRight = nXLeft-1; 574 pNewSep->mbRemoved = sal_False; 575 576 pSep->mnXLeft = nXRight+1; 577 578 // connections from the new separation 579 pNewSep->mpNextSep = pSep; 580 581 // connections to the new separation 582 if ( pSep == mpFirstSep ) 583 mpFirstSep = pNewSep; 584 else 585 pPrevSep->mpNextSep = pNewSep; 586 } 587 } 588 589 pPrevSep = pSep; 590 pSep = pSep->mpNextSep; 591 } 592 593 OptimizeBand(); 594 } 595 596 // ----------------------------------------------------------------------- 597 598 void ImplRegionBand::XOr( long nXLeft, long nXRight ) 599 { 600 DBG_ASSERT( nXLeft <= nXRight, "ImplRegionBand::XOr(): nxLeft > nXRight" ); 601 602 // #i46602# Reworked rectangle Xor 603 // 604 // In general, we can distinguish 11 cases of intersection 605 // (details below). The old implementation explicitely handled 7 606 // cases (numbered in the order of appearance, use CVS to get your 607 // hands on the old version), therefore, I've sticked to that 608 // order, and added four more cases. The code below references 609 // those numbers via #1, #2, etc. 610 // 611 // Num Mnem newX:oldX newY:oldY Description Result Can quit? 612 // 613 // #1 Empty band - - The band is empty, thus, simply add new bandSep just add Yes 614 // 615 // #2 apart - - The rectangles are disjunct, add new one as is just add Yes 616 // 617 // #3 atop == == The rectangles are _exactly_ the same, remove existing just remove Yes 618 // 619 // #4 around < > The new rectangle extends the old to both sides intersect No 620 // 621 // #5 left < < The new rectangle is left of the old (but intersects) intersect Yes 622 // 623 // #5b left-atop < == The new is left of the old, and coincides on the right intersect Yes 624 // 625 // #6 right > > The new is right of the old (but intersects) intersect No 626 // 627 // #6b right-atop == > The new is right of the old, and coincides on the left intersect No 628 // 629 // #7 inside > < The new is fully inside the old intersect Yes 630 // 631 // #8 inside-right > == The new is fully inside the old, coincides on the right intersect Yes 632 // 633 // #9 inside-left == < The new is fully inside the old, coincides on the left intersect Yes 634 // 635 // 636 // Then, to correctly perform XOr, the segment that's switched off 637 // (i.e. the overlapping part of the old and the new segment) must 638 // be extended by one pixel value at each border: 639 // 1 1 640 // 0 4 0 4 641 // 111100000001111 642 // 643 // Clearly, the leading band sep now goes from 0 to 3, and the 644 // trailing band sep from 11 to 14. This mimicks the xor look of a 645 // bitmap operation. 646 // 647 648 // band empty? -> add element 649 if ( !mpFirstSep ) 650 { 651 mpFirstSep = new ImplRegionBandSep; 652 mpFirstSep->mnXLeft = nXLeft; 653 mpFirstSep->mnXRight = nXRight; 654 mpFirstSep->mbRemoved = sal_False; 655 mpFirstSep->mpNextSep = NULL; 656 return; 657 } 658 659 // process real xor 660 ImplRegionBandSep* pNewSep; 661 ImplRegionBandSep* pPrevSep = 0; 662 ImplRegionBandSep* pSep = mpFirstSep; 663 664 while ( pSep ) 665 { 666 long nOldLeft( pSep->mnXLeft ); 667 long nOldRight( pSep->mnXRight ); 668 669 // did the current segment actually touch the new rect? If 670 // not, skip all comparisons, go on, loop and try to find 671 // intersecting bandSep 672 if( nXLeft <= nOldRight ) 673 { 674 if( nXRight < nOldLeft ) 675 { 676 // #2 677 678 // add _before_ current bandSep 679 pNewSep = new ImplRegionBandSep; 680 pNewSep->mnXLeft = nXLeft; 681 pNewSep->mnXRight = nXRight; 682 pNewSep->mpNextSep = pSep; 683 pNewSep->mbRemoved = sal_False; 684 685 // connections from the new separation 686 pNewSep->mpNextSep = pSep; 687 688 // connections to the new separation 689 if ( pSep == mpFirstSep ) 690 mpFirstSep = pNewSep; 691 else 692 pPrevSep->mpNextSep = pNewSep; 693 pPrevSep = NULL; // do not run accidentally into the "right" case when breaking the loop 694 break; 695 } 696 else if( nXLeft == nOldLeft && nXRight == nOldRight ) 697 { 698 // #3 699 pSep->mbRemoved = sal_True; 700 pPrevSep = NULL; // do not run accidentally into the "right" case when breaking the loop 701 break; 702 } 703 else if( nXLeft != nOldLeft && nXRight == nOldRight ) 704 { 705 // # 5b, 8 706 if( nXLeft < nOldLeft ) 707 { 708 nXRight = nOldLeft; // 5b 709 } 710 else 711 { 712 nXRight = nXLeft; // 8 713 nXLeft = nOldLeft; 714 } 715 716 pSep->mnXLeft = nXLeft; 717 pSep->mnXRight = nXRight-1; 718 719 pPrevSep = NULL; // do not run accidentally into the "right" case when breaking the loop 720 break; 721 } 722 else if( nXLeft == nOldLeft && nXRight != nOldRight ) 723 { 724 // # 6b, 9 725 726 if( nXRight > nOldRight ) 727 { 728 nXLeft = nOldRight+1; // 6b 729 730 // cannot break here, simply mark segment as removed, 731 // and go on with adapted nXLeft/nXRight 732 pSep->mbRemoved = sal_True; 733 } 734 else 735 { 736 pSep->mnXLeft = nXRight+1; // 9 737 738 pPrevSep = NULL; // do not run accidentally into the "right" case when breaking the loop 739 break; 740 } 741 } 742 else // if( nXLeft != nOldLeft && nXRight != nOldRight ) follows automatically 743 { 744 // #4,5,6,7 745 DBG_ASSERT( nXLeft != nOldLeft && nXRight != nOldRight, 746 "ImplRegionBand::XOr(): Case 4,5,6,7 expected all coordinates to be not equal!" ); 747 748 // The plain-jane check would look like this: 749 // 750 // if( nXLeft < nOldLeft ) 751 // { 752 // // #4,5 753 // if( nXRight > nOldRight ) 754 // { 755 // // #4 756 // } 757 // else 758 // { 759 // // #5 done! 760 // } 761 // } 762 // else 763 // { 764 // // #6,7 765 // if( nXRight > nOldRight ) 766 // { 767 // // #6 768 // } 769 // else 770 // { 771 // // #7 done! 772 // } 773 // } 774 // 775 // but since we generally don't have to care whether 776 // it's 4 or 6 (only that we must not stop processing 777 // here), condensed that in such a way that only the 778 // coordinates get shuffled into correct ordering. 779 780 if( nXLeft < nOldLeft ) 781 ::std::swap( nOldLeft, nXLeft ); 782 783 bool bDone( false ); 784 785 if( nXRight < nOldRight ) 786 { 787 ::std::swap( nOldRight, nXRight ); 788 bDone = true; 789 } 790 791 // now, nOldLeft<nXLeft<=nOldRight<nXRight always 792 // holds. Note that we need the nXLeft<=nOldRight here, as 793 // the intersection part might be only one pixel (original 794 // nXLeft==nXRight) 795 DBG_ASSERT( nOldLeft<nXLeft && nXLeft<=nOldRight && nOldRight<nXRight, 796 "ImplRegionBand::XOr(): Case 4,5,6,7 expected coordinates to be ordered now!" ); 797 798 pSep->mnXLeft = nOldLeft; 799 pSep->mnXRight = nXLeft-1; 800 801 nXLeft = nOldRight+1; 802 // nxRight is already setup correctly 803 804 if( bDone ) 805 { 806 // add behind current bandSep 807 pNewSep = new ImplRegionBandSep; 808 809 pNewSep->mnXLeft = nXLeft; 810 pNewSep->mnXRight = nXRight; 811 pNewSep->mpNextSep = pSep->mpNextSep; 812 pNewSep->mbRemoved = sal_False; 813 814 // connections from the new separation 815 pSep->mpNextSep = pNewSep; 816 817 pPrevSep = NULL; // do not run accidentally into the "right" case when breaking the loop 818 break; 819 } 820 } 821 } 822 823 pPrevSep = pSep; 824 pSep = pSep->mpNextSep; 825 } 826 827 // new separation completely right of existing bandSeps ? 828 if( pPrevSep && nXLeft >= pPrevSep->mnXRight ) 829 { 830 pNewSep = new ImplRegionBandSep; 831 pNewSep->mnXLeft = nXLeft; 832 pNewSep->mnXRight = nXRight; 833 pNewSep->mpNextSep = NULL; 834 pNewSep->mbRemoved = sal_False; 835 836 // connections from the new separation 837 pPrevSep->mpNextSep = pNewSep; 838 } 839 840 OptimizeBand(); 841 } 842 843 // ----------------------------------------------------------------------- 844 845 sal_Bool ImplRegionBand::IsInside( long nX ) 846 { 847 ImplRegionBandSep* pSep = mpFirstSep; 848 while ( pSep ) 849 { 850 if ( (pSep->mnXLeft <= nX) && (pSep->mnXRight >= nX) ) 851 return sal_True; 852 853 pSep = pSep->mpNextSep; 854 } 855 856 return sal_False; 857 } 858 859 // ----------------------------------------------------------------------- 860 861 sal_Bool ImplRegionBand::IsOver( long nLeft, long nRight ) 862 { 863 ImplRegionBandSep* pSep = mpFirstSep; 864 while ( pSep ) 865 { 866 if ( (pSep->mnXLeft < nRight) && (pSep->mnXRight > nLeft) ) 867 return sal_True; 868 869 pSep = pSep->mpNextSep; 870 } 871 872 return sal_False; 873 } 874 875 // ----------------------------------------------------------------------- 876 877 sal_Bool ImplRegionBand::IsInside( long nLeft, long nRight ) 878 { 879 ImplRegionBandSep* pSep = mpFirstSep; 880 while ( pSep ) 881 { 882 if ( (pSep->mnXLeft >= nLeft) && (nRight <= pSep->mnXRight) ) 883 return sal_True; 884 885 pSep = pSep->mpNextSep; 886 } 887 888 return sal_False; 889 } 890 891 // ----------------------------------------------------------------------- 892 893 long ImplRegionBand::GetXLeftBoundary() const 894 { 895 DBG_ASSERT( mpFirstSep != NULL, "ImplRegionBand::XLeftBoundary -> no separation in band!" ); 896 897 return mpFirstSep->mnXLeft; 898 } 899 900 // ----------------------------------------------------------------------- 901 902 long ImplRegionBand::GetXRightBoundary() const 903 { 904 DBG_ASSERT( mpFirstSep != NULL, "ImplRegionBand::XRightBoundary -> no separation in band!" ); 905 906 // search last separation 907 ImplRegionBandSep* pSep = mpFirstSep; 908 while ( pSep->mpNextSep ) 909 pSep = pSep->mpNextSep; 910 return pSep->mnXRight; 911 } 912 913 // ----------------------------------------------------------------------- 914 915 sal_Bool ImplRegionBand::operator==( const ImplRegionBand& rRegionBand ) const 916 { 917 ImplRegionBandSep* pOwnRectBandSep = mpFirstSep; 918 ImplRegionBandSep* pSecondRectBandSep = rRegionBand.mpFirstSep; 919 while ( pOwnRectBandSep && pSecondRectBandSep ) 920 { 921 // get boundaries of current rectangle 922 long nOwnXLeft = pOwnRectBandSep->mnXLeft; 923 long nSecondXLeft = pSecondRectBandSep->mnXLeft; 924 if ( nOwnXLeft != nSecondXLeft ) 925 return sal_False; 926 927 long nOwnXRight = pOwnRectBandSep->mnXRight; 928 long nSecondXRight = pSecondRectBandSep->mnXRight; 929 if ( nOwnXRight != nSecondXRight ) 930 return sal_False; 931 932 // get next separation from current band 933 pOwnRectBandSep = pOwnRectBandSep->mpNextSep; 934 935 // get next separation from current band 936 pSecondRectBandSep = pSecondRectBandSep->mpNextSep; 937 } 938 939 // differnt number of separations? 940 if ( pOwnRectBandSep || pSecondRectBandSep ) 941 return sal_False; 942 943 return sal_True; 944 } 945 946 // ----------------------------------------------------------------------- 947 948 ImplRegionBand* ImplRegionBand::SplitBand (const sal_Int32 nY) 949 { 950 OSL_ASSERT(nY>mnYTop); 951 OSL_ASSERT(nY<=mnYBottom); 952 953 // Create a copy of the given band (we tell the constructor to copy the points together 954 // with the seps.) 955 ImplRegionBand* pLowerBand = new ImplRegionBand(*this, false); 956 957 // Adapt vertical coordinates. 958 mnYBottom = nY-1; 959 pLowerBand->mnYTop = nY; 960 961 // Insert new band into list of bands. 962 pLowerBand->mpNextBand = mpNextBand; 963 mpNextBand = pLowerBand; 964 pLowerBand->mpPrevBand = this; 965 if (pLowerBand->mpNextBand != NULL) 966 pLowerBand->mpNextBand->mpPrevBand = pLowerBand; 967 968 return pLowerBand; 969 } 970