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