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
ImplRegionBand(long nTop,long nBottom)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
ImplRegionBand(const ImplRegionBand & rRegionBand,const bool bIgnorePoints)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
~ImplRegionBand()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
ProcessPoints()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
InsertPoint(long nX,long nLineId,bool bEndPoint,LineType eLineType)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 completely 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
MoveX(long nHorzMove)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
ScaleX(double fHorzScale)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 overlapping separations
349
OptimizeBand()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 // overlapping 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
Union(long nXLeft,long nXRight)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 completely 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 overlapping from left? -> extend boundary
435 if ( (nXRight >= pSep->mnXLeft) && (nXLeft <= pSep->mnXLeft) )
436 pSep->mnXLeft = nXLeft;
437
438 // new separation overlapping 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
Intersect(long nXLeft,long nXRight)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 completely 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 overlapping 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 overlapping 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
Exclude(long nXLeft,long nXRight)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 overlapping 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 overlapping 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
XOr(long nXLeft,long nXRight)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
IsInside(long nX)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
IsOver(long nLeft,long nRight)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
IsInside(long nLeft,long nRight)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
GetXLeftBoundary() const889 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
GetXRightBoundary() const898 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
operator ==(const ImplRegionBand & rRegionBand) const911 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
SplitBand(const sal_Int32 nY)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