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