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 1077121 : ImplRegionBand::ImplRegionBand( long nTop, long nBottom )
47 : {
48 : // save boundaries
49 1077121 : mnYTop = nTop;
50 1077121 : mnYBottom = nBottom;
51 :
52 : // initialize lists
53 1077121 : mpNextBand = NULL;
54 1077121 : mpPrevBand = NULL;
55 1077121 : mpFirstSep = NULL;
56 1077121 : mpFirstBandPoint = NULL;
57 1077121 : mbTouched = false;
58 1077121 : }
59 :
60 : // -----------------------------------------------------------------------
61 :
62 2175366 : ImplRegionBand::ImplRegionBand(
63 : const ImplRegionBand& rRegionBand,
64 : const bool bIgnorePoints)
65 : {
66 : // copy boundaries
67 2175366 : mnYTop = rRegionBand.mnYTop;
68 2175366 : mnYBottom = rRegionBand.mnYBottom;
69 2175366 : mbTouched = rRegionBand.mbTouched;
70 :
71 : // initialisation
72 2175366 : mpNextBand = NULL;
73 2175366 : mpPrevBand = NULL;
74 2175366 : mpFirstSep = NULL;
75 2175366 : mpFirstBandPoint = NULL;
76 :
77 : // copy all elements of the list with separations
78 : ImplRegionBandSep* pNewSep;
79 2175366 : ImplRegionBandSep* pPrevSep = 0;
80 2175366 : ImplRegionBandSep* pSep = rRegionBand.mpFirstSep;
81 6634893 : while ( pSep )
82 : {
83 : // create new and copy data
84 2284161 : pNewSep = new ImplRegionBandSep;
85 2284161 : pNewSep->mnXLeft = pSep->mnXLeft;
86 2284161 : pNewSep->mnXRight = pSep->mnXRight;
87 2284161 : pNewSep->mbRemoved = pSep->mbRemoved;
88 2284161 : pNewSep->mpNextSep = NULL;
89 2284161 : if ( pSep == rRegionBand.mpFirstSep )
90 1950398 : mpFirstSep = pNewSep;
91 : else
92 333763 : pPrevSep->mpNextSep = pNewSep;
93 :
94 2284161 : pPrevSep = pNewSep;
95 2284161 : pSep = pSep->mpNextSep;
96 : }
97 :
98 2175366 : 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 2175366 : }
121 :
122 : // -----------------------------------------------------------------------
123 :
124 3252443 : ImplRegionBand::~ImplRegionBand()
125 : {
126 : DBG_ASSERT( mpFirstBandPoint == NULL, "ImplRegionBand::~ImplRegionBand -> pointlist not empty" );
127 :
128 : // delete elements of the list
129 3252443 : ImplRegionBandSep* pSep = mpFirstSep;
130 9004292 : while ( pSep )
131 : {
132 2499406 : ImplRegionBandSep* pTempSep = pSep->mpNextSep;
133 2499406 : delete pSep;
134 2499406 : pSep = pTempSep;
135 : }
136 :
137 : // delete elements of the list
138 3252443 : ImplRegionBandPoint* pPoint = mpFirstBandPoint;
139 6504886 : while ( pPoint )
140 : {
141 0 : ImplRegionBandPoint* pTempPoint = pPoint->mpNextBandPoint;
142 0 : delete pPoint;
143 0 : pPoint = pTempPoint;
144 : }
145 3252443 : }
146 :
147 : // -----------------------------------------------------------------------
148 : //
149 : // generate separations from lines and process union with existing
150 : // separations
151 :
152 30 : void ImplRegionBand::ProcessPoints()
153 : {
154 : // check Pointlist
155 30 : ImplRegionBandPoint* pRegionBandPoint = mpFirstBandPoint;
156 120 : while ( pRegionBandPoint )
157 : {
158 : // within list?
159 60 : if ( pRegionBandPoint->mpNextBandPoint )
160 : {
161 : // start/stop?
162 30 : if ( pRegionBandPoint->mbEndPoint && pRegionBandPoint->mpNextBandPoint->mbEndPoint )
163 : {
164 : // same direction? -> remove next point!
165 30 : 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 60 : pRegionBandPoint = pRegionBandPoint->mpNextBandPoint;
176 : }
177 :
178 30 : pRegionBandPoint = mpFirstBandPoint;
179 90 : while ( pRegionBandPoint && pRegionBandPoint->mpNextBandPoint )
180 : {
181 30 : Union( pRegionBandPoint->mnX, pRegionBandPoint->mpNextBandPoint->mnX );
182 :
183 30 : ImplRegionBandPoint* pNextBandPoint = pRegionBandPoint->mpNextBandPoint->mpNextBandPoint;
184 :
185 : // remove already processed points
186 30 : delete pRegionBandPoint->mpNextBandPoint;
187 30 : delete pRegionBandPoint;
188 :
189 : // continue with next element in the list
190 30 : pRegionBandPoint = pNextBandPoint;
191 : }
192 :
193 : // remove last element if necessary
194 30 : delete pRegionBandPoint;
195 :
196 : // list is now empty
197 30 : mpFirstBandPoint = NULL;
198 30 : }
199 :
200 : // -----------------------------------------------------------------------
201 : //
202 : // generate separations from lines and process union with existing
203 : // separations
204 :
205 60 : bool ImplRegionBand::InsertPoint( long nX, long nLineId,
206 : bool bEndPoint, LineType eLineType )
207 : {
208 60 : if ( !mpFirstBandPoint )
209 : {
210 30 : mpFirstBandPoint = new ImplRegionBandPoint;
211 30 : mpFirstBandPoint->mnX = nX;
212 30 : mpFirstBandPoint->mnLineId = nLineId;
213 30 : mpFirstBandPoint->mbEndPoint = bEndPoint;
214 30 : mpFirstBandPoint->meLineType = eLineType;
215 30 : mpFirstBandPoint->mpNextBandPoint = NULL;
216 30 : return true;
217 : }
218 :
219 : // look if line already touched the band
220 30 : ImplRegionBandPoint* pRegionBandPoint = mpFirstBandPoint;
221 30 : ImplRegionBandPoint* pLastTestedRegionBandPoint = NULL;
222 90 : while( pRegionBandPoint )
223 : {
224 30 : 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 = true;
236 0 : return 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 false;
261 : }
262 :
263 : // use next element
264 30 : pLastTestedRegionBandPoint = pRegionBandPoint;
265 30 : pRegionBandPoint = pRegionBandPoint->mpNextBandPoint;
266 : }
267 :
268 : // search appropriate position and insert point into the list
269 : ImplRegionBandPoint* pNewRegionBandPoint;
270 :
271 30 : pRegionBandPoint = mpFirstBandPoint;
272 30 : pLastTestedRegionBandPoint = NULL;
273 70 : while ( pRegionBandPoint )
274 : {
275 : // new point completely left? -> insert as first point
276 30 : if ( nX <= pRegionBandPoint->mnX )
277 : {
278 20 : pNewRegionBandPoint = new ImplRegionBandPoint;
279 20 : pNewRegionBandPoint->mnX = nX;
280 20 : pNewRegionBandPoint->mnLineId = nLineId;
281 20 : pNewRegionBandPoint->mbEndPoint = bEndPoint;
282 20 : pNewRegionBandPoint->meLineType = eLineType;
283 20 : pNewRegionBandPoint->mpNextBandPoint = pRegionBandPoint;
284 :
285 : // connections to the new point
286 20 : if ( !pLastTestedRegionBandPoint )
287 20 : mpFirstBandPoint = pNewRegionBandPoint;
288 : else
289 0 : pLastTestedRegionBandPoint->mpNextBandPoint = pNewRegionBandPoint;
290 :
291 20 : return true;
292 : }
293 :
294 : // use next element
295 10 : pLastTestedRegionBandPoint = pRegionBandPoint;
296 10 : pRegionBandPoint = pRegionBandPoint->mpNextBandPoint;
297 : }
298 :
299 : // not inserted -> add to the end of the list
300 10 : pNewRegionBandPoint = new ImplRegionBandPoint;
301 10 : pNewRegionBandPoint->mnX = nX;
302 10 : pNewRegionBandPoint->mnLineId = nLineId;
303 10 : pNewRegionBandPoint->mbEndPoint = bEndPoint;
304 10 : pNewRegionBandPoint->meLineType = eLineType;
305 10 : pNewRegionBandPoint->mpNextBandPoint = NULL;
306 :
307 : // connections to the new point
308 10 : pLastTestedRegionBandPoint->mpNextBandPoint = pNewRegionBandPoint;
309 :
310 10 : return true;
311 : }
312 :
313 : // -----------------------------------------------------------------------
314 :
315 44189 : void ImplRegionBand::MoveX( long nHorzMove )
316 : {
317 : // move all x-separations
318 44189 : ImplRegionBandSep* pSep = mpFirstSep;
319 133555 : while ( pSep )
320 : {
321 45177 : pSep->mnXLeft += nHorzMove;
322 45177 : pSep->mnXRight += nHorzMove;
323 45177 : pSep = pSep->mpNextSep;
324 : }
325 44189 : }
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 2099702 : bool ImplRegionBand::OptimizeBand()
345 : {
346 2099702 : ImplRegionBandSep* pPrevSep = 0;
347 2099702 : ImplRegionBandSep* pSep = mpFirstSep;
348 6680253 : while ( pSep )
349 : {
350 : // remove?
351 2480849 : if ( pSep->mbRemoved || (pSep->mnXRight < pSep->mnXLeft) )
352 : {
353 263111 : ImplRegionBandSep* pOldSep = pSep;
354 263111 : if ( pSep == mpFirstSep )
355 206394 : mpFirstSep = pSep->mpNextSep;
356 : else
357 56717 : pPrevSep->mpNextSep = pSep->mpNextSep;
358 263111 : pSep = pSep->mpNextSep;
359 263111 : delete pOldSep;
360 263111 : continue;
361 : }
362 :
363 : // overlaping separations? -> combine!
364 2217738 : if ( pSep->mpNextSep )
365 : {
366 274285 : if ( (pSep->mnXRight+1) >= pSep->mpNextSep->mnXLeft )
367 : {
368 13551 : if ( pSep->mpNextSep->mnXRight > pSep->mnXRight )
369 13303 : pSep->mnXRight = pSep->mpNextSep->mnXRight;
370 :
371 13551 : ImplRegionBandSep* pOldSep = pSep->mpNextSep;
372 13551 : pSep->mpNextSep = pOldSep->mpNextSep;
373 13551 : delete pOldSep;
374 13551 : continue;
375 : }
376 : }
377 :
378 2204187 : pPrevSep = pSep;
379 2204187 : pSep = pSep->mpNextSep;
380 : }
381 :
382 2099702 : return true;
383 : }
384 :
385 : // -----------------------------------------------------------------------
386 :
387 542717 : void ImplRegionBand::Union( long nXLeft, long nXRight )
388 : {
389 : DBG_ASSERT( nXLeft <= nXRight, "ImplRegionBand::Union(): nxLeft > nXRight" );
390 :
391 : // band empty? -> add element
392 542717 : if ( !mpFirstSep )
393 : {
394 433691 : mpFirstSep = new ImplRegionBandSep;
395 433691 : mpFirstSep->mnXLeft = nXLeft;
396 433691 : mpFirstSep->mnXRight = nXRight;
397 433691 : mpFirstSep->mbRemoved = false;
398 433691 : mpFirstSep->mpNextSep = NULL;
399 433691 : return;
400 : }
401 :
402 : // process real union
403 : ImplRegionBandSep* pNewSep;
404 109026 : ImplRegionBandSep* pPrevSep = 0;
405 109026 : ImplRegionBandSep* pSep = mpFirstSep;
406 232355 : while ( pSep )
407 : {
408 : // new separation completely inside? nothing to do!
409 113074 : if ( (nXLeft >= pSep->mnXLeft) && (nXRight <= pSep->mnXRight) )
410 47318 : return;
411 :
412 : // new separation completely left? -> new separation!
413 65756 : if ( nXRight < pSep->mnXLeft )
414 : {
415 19687 : pNewSep = new ImplRegionBandSep;
416 19687 : pNewSep->mnXLeft = nXLeft;
417 19687 : pNewSep->mnXRight = nXRight;
418 19687 : pNewSep->mbRemoved = false;
419 :
420 19687 : pNewSep->mpNextSep = pSep;
421 19687 : if ( pSep == mpFirstSep )
422 19482 : mpFirstSep = pNewSep;
423 : else
424 205 : pPrevSep->mpNextSep = pNewSep;
425 19687 : break;
426 : }
427 :
428 : // new separation overlaping from left? -> extend boundary
429 46069 : if ( (nXRight >= pSep->mnXLeft) && (nXLeft <= pSep->mnXLeft) )
430 12698 : pSep->mnXLeft = nXLeft;
431 :
432 : // new separation overlaping from right? -> extend boundary
433 46069 : if ( (nXLeft <= pSep->mnXRight) && (nXRight > pSep->mnXRight) )
434 : {
435 23018 : pSep->mnXRight = nXRight;
436 23018 : break;
437 : }
438 :
439 : // not inserted, but last element? -> add to the end of the list
440 23051 : if ( !pSep->mpNextSep && (nXLeft > pSep->mnXRight) )
441 : {
442 8748 : pNewSep = new ImplRegionBandSep;
443 8748 : pNewSep->mnXLeft = nXLeft;
444 8748 : pNewSep->mnXRight = nXRight;
445 8748 : pNewSep->mbRemoved = false;
446 :
447 8748 : pSep->mpNextSep = pNewSep;
448 8748 : pNewSep->mpNextSep = NULL;
449 8748 : break;
450 : }
451 :
452 14303 : pPrevSep = pSep;
453 14303 : pSep = pSep->mpNextSep;
454 : }
455 :
456 61708 : OptimizeBand();
457 : }
458 :
459 : // -----------------------------------------------------------------------
460 :
461 527666 : void ImplRegionBand::Intersect( long nXLeft, long nXRight )
462 : {
463 : DBG_ASSERT( nXLeft <= nXRight, "ImplRegionBand::Intersect(): nxLeft > nXRight" );
464 :
465 : // band has been touched
466 527666 : mbTouched = true;
467 :
468 : // band empty? -> nothing to do
469 527666 : if ( !mpFirstSep )
470 902646 : return;
471 :
472 : // process real intersection
473 152686 : ImplRegionBandSep* pSep = mpFirstSep;
474 461703 : while ( pSep )
475 : {
476 : // new separation completely outside? -> remove separation
477 156331 : if ( (nXRight < pSep->mnXLeft) || (nXLeft > pSep->mnXRight) )
478 : // will be removed from the optimizer
479 2649 : pSep->mbRemoved = true;
480 :
481 : // new separation overlaping from left? -> reduce right boundary
482 307726 : if ( (nXLeft <= pSep->mnXLeft) &&
483 204700 : (nXRight <= pSep->mnXRight) &&
484 53305 : (nXRight >= pSep->mnXLeft) )
485 50903 : pSep->mnXRight = nXRight;
486 :
487 : // new separation overlaping from right? -> reduce right boundary
488 222321 : if ( (nXLeft >= pSep->mnXLeft) &&
489 131733 : (nXLeft <= pSep->mnXRight) &&
490 65743 : (nXRight >= pSep->mnXRight) )
491 61979 : pSep->mnXLeft = nXLeft;
492 :
493 : // new separation within the actual one? -> reduce both boundaries
494 156331 : if ( (nXLeft >= pSep->mnXLeft) && (nXRight <= pSep->mnXRight) )
495 : {
496 50039 : pSep->mnXRight = nXRight;
497 50039 : pSep->mnXLeft = nXLeft;
498 : }
499 :
500 156331 : pSep = pSep->mpNextSep;
501 : }
502 :
503 152686 : OptimizeBand();
504 : }
505 :
506 : // -----------------------------------------------------------------------
507 :
508 2752644 : void ImplRegionBand::Exclude( long nXLeft, long nXRight )
509 : {
510 : DBG_ASSERT( nXLeft <= nXRight, "ImplRegionBand::Exclude(): nxLeft > nXRight" );
511 :
512 : // band has been touched
513 2752644 : mbTouched = true;
514 :
515 : // band empty? -> nothing to do
516 2752644 : if ( !mpFirstSep )
517 3619980 : return;
518 :
519 : // process real exclusion
520 : ImplRegionBandSep* pNewSep;
521 1885308 : ImplRegionBandSep* pPrevSep = 0;
522 1885308 : ImplRegionBandSep* pSep = mpFirstSep;
523 5947459 : while ( pSep )
524 : {
525 2176843 : bool bSepProcessed = false;
526 :
527 : // new separation completely overlapping? -> remove separation
528 2176843 : if ( (nXLeft <= pSep->mnXLeft) && (nXRight >= pSep->mnXRight) )
529 : {
530 : // will be removed from the optimizer
531 251789 : pSep->mbRemoved = true;
532 251789 : bSepProcessed = true;
533 : }
534 :
535 : // new separation overlaping from left? -> reduce boundary
536 2176843 : if ( !bSepProcessed )
537 : {
538 1925054 : if ( (nXRight >= pSep->mnXLeft) && (nXLeft <= pSep->mnXLeft) )
539 : {
540 339595 : pSep->mnXLeft = nXRight+1;
541 339595 : bSepProcessed = true;
542 : }
543 : }
544 :
545 : // new separation overlaping from right? -> reduce boundary
546 2176843 : if ( !bSepProcessed )
547 : {
548 1585459 : if ( (nXLeft <= pSep->mnXRight) && (nXRight > pSep->mnXRight) )
549 : {
550 304437 : pSep->mnXRight = nXLeft-1;
551 304437 : bSepProcessed = true;
552 : }
553 : }
554 :
555 : // new separation within the actual one? -> reduce boundary
556 : // and add new entry for reminder
557 2176843 : if ( !bSepProcessed )
558 : {
559 1281022 : if ( (nXLeft >= pSep->mnXLeft) && (nXRight <= pSep->mnXRight) )
560 : {
561 29825 : pNewSep = new ImplRegionBandSep;
562 29825 : pNewSep->mnXLeft = pSep->mnXLeft;
563 29825 : pNewSep->mnXRight = nXLeft-1;
564 29825 : pNewSep->mbRemoved = false;
565 :
566 29825 : pSep->mnXLeft = nXRight+1;
567 :
568 : // connections from the new separation
569 29825 : pNewSep->mpNextSep = pSep;
570 :
571 : // connections to the new separation
572 29825 : if ( pSep == mpFirstSep )
573 22153 : mpFirstSep = pNewSep;
574 : else
575 7672 : pPrevSep->mpNextSep = pNewSep;
576 : }
577 : }
578 :
579 2176843 : pPrevSep = pSep;
580 2176843 : pSep = pSep->mpNextSep;
581 : }
582 :
583 1885308 : 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 = 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 = 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 0 : break;
685 : }
686 0 : else if( nXLeft == nOldLeft && nXRight == nOldRight )
687 : {
688 : // #3
689 0 : pSep->mbRemoved = true;
690 0 : pPrevSep = NULL; // do not run accidentally into the "right" case when breaking the loop
691 0 : 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 0 : 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 = 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 0 : 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 = 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 0 : 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 = false;
825 :
826 : // connections from the new separation
827 0 : pPrevSep->mpNextSep = pNewSep;
828 : }
829 :
830 0 : OptimizeBand();
831 : }
832 :
833 : // -----------------------------------------------------------------------
834 :
835 0 : 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 true;
842 :
843 0 : pSep = pSep->mpNextSep;
844 : }
845 :
846 0 : return false;
847 : }
848 :
849 : // -----------------------------------------------------------------------
850 :
851 0 : bool ImplRegionBand::IsOver( long nLeft, long nRight )
852 : {
853 0 : ImplRegionBandSep* pSep = mpFirstSep;
854 0 : while ( pSep )
855 : {
856 0 : if ( (pSep->mnXLeft < nRight) && (pSep->mnXRight > nLeft) )
857 0 : return true;
858 :
859 0 : pSep = pSep->mpNextSep;
860 : }
861 :
862 0 : return false;
863 : }
864 :
865 : // -----------------------------------------------------------------------
866 :
867 0 : bool ImplRegionBand::IsInside( long nLeft, long nRight )
868 : {
869 0 : ImplRegionBandSep* pSep = mpFirstSep;
870 0 : while ( pSep )
871 : {
872 0 : if ( (pSep->mnXLeft >= nLeft) && (nRight <= pSep->mnXRight) )
873 0 : return true;
874 :
875 0 : pSep = pSep->mpNextSep;
876 : }
877 :
878 0 : return false;
879 : }
880 :
881 : // -----------------------------------------------------------------------
882 :
883 180176 : long ImplRegionBand::GetXLeftBoundary() const
884 : {
885 : DBG_ASSERT( mpFirstSep != NULL, "ImplRegionBand::XLeftBoundary -> no separation in band!" );
886 :
887 180176 : return mpFirstSep->mnXLeft;
888 : }
889 :
890 : // -----------------------------------------------------------------------
891 :
892 180176 : long ImplRegionBand::GetXRightBoundary() const
893 : {
894 : DBG_ASSERT( mpFirstSep != NULL, "ImplRegionBand::XRightBoundary -> no separation in band!" );
895 :
896 : // search last separation
897 180176 : ImplRegionBandSep* pSep = mpFirstSep;
898 423375 : while ( pSep->mpNextSep )
899 63023 : pSep = pSep->mpNextSep;
900 180176 : return pSep->mnXRight;
901 : }
902 :
903 : // -----------------------------------------------------------------------
904 :
905 870180 : bool ImplRegionBand::operator==( const ImplRegionBand& rRegionBand ) const
906 : {
907 870180 : ImplRegionBandSep* pOwnRectBandSep = mpFirstSep;
908 870180 : ImplRegionBandSep* pSecondRectBandSep = rRegionBand.mpFirstSep;
909 2393410 : while ( pOwnRectBandSep && pSecondRectBandSep )
910 : {
911 : // get boundaries of current rectangle
912 699899 : long nOwnXLeft = pOwnRectBandSep->mnXLeft;
913 699899 : long nSecondXLeft = pSecondRectBandSep->mnXLeft;
914 699899 : if ( nOwnXLeft != nSecondXLeft )
915 22372 : return false;
916 :
917 677527 : long nOwnXRight = pOwnRectBandSep->mnXRight;
918 677527 : long nSecondXRight = pSecondRectBandSep->mnXRight;
919 677527 : if ( nOwnXRight != nSecondXRight )
920 24477 : return false;
921 :
922 : // get next separation from current band
923 653050 : pOwnRectBandSep = pOwnRectBandSep->mpNextSep;
924 :
925 : // get next separation from current band
926 653050 : pSecondRectBandSep = pSecondRectBandSep->mpNextSep;
927 : }
928 :
929 : // different number of separations?
930 823331 : if ( pOwnRectBandSep || pSecondRectBandSep )
931 222844 : return false;
932 :
933 600487 : return true;
934 : }
935 :
936 : // -----------------------------------------------------------------------
937 :
938 0 : ImplRegionBand* ImplRegionBand::SplitBand (const sal_Int32 nY)
939 : {
940 : OSL_ASSERT(nY>mnYTop);
941 : OSL_ASSERT(nY<=mnYBottom);
942 :
943 : // Create a copy of the given band (we tell the constructor to copy the points together
944 : // with the seps.)
945 0 : ImplRegionBand* pLowerBand = new ImplRegionBand(*this, false);
946 :
947 : // Adapt vertical coordinates.
948 0 : mnYBottom = nY-1;
949 0 : pLowerBand->mnYTop = nY;
950 :
951 : // Insert new band into list of bands.
952 0 : pLowerBand->mpNextBand = mpNextBand;
953 0 : mpNextBand = pLowerBand;
954 0 : pLowerBand->mpPrevBand = this;
955 0 : if (pLowerBand->mpNextBand != NULL)
956 0 : pLowerBand->mpNextBand->mpPrevBand = pLowerBand;
957 :
958 0 : return pLowerBand;
959 : }
960 :
961 : /* vim:set shiftwidth=4 softtabstop=4 expandtab: */
|
