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