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 2121185 : ImplRegionBand::ImplRegionBand( long nTop, long nBottom )
43 : {
44 : // save boundaries
45 2121185 : mnYTop = nTop;
46 2121185 : mnYBottom = nBottom;
47 :
48 : // initialize lists
49 2121185 : mpNextBand = NULL;
50 2121185 : mpPrevBand = NULL;
51 2121185 : mpFirstSep = NULL;
52 2121185 : mpFirstBandPoint = NULL;
53 2121185 : mbTouched = false;
54 2121185 : }
55 :
56 5222829 : ImplRegionBand::ImplRegionBand(
57 : const ImplRegionBand& rRegionBand,
58 : const bool bIgnorePoints)
59 : {
60 : // copy boundaries
61 5222829 : mnYTop = rRegionBand.mnYTop;
62 5222829 : mnYBottom = rRegionBand.mnYBottom;
63 5222829 : mbTouched = rRegionBand.mbTouched;
64 :
65 : // initialisation
66 5222829 : mpNextBand = NULL;
67 5222829 : mpPrevBand = NULL;
68 5222829 : mpFirstSep = NULL;
69 5222829 : mpFirstBandPoint = NULL;
70 :
71 : // copy all elements of the list with separations
72 : ImplRegionBandSep* pNewSep;
73 5222829 : ImplRegionBandSep* pPrevSep = 0;
74 5222829 : ImplRegionBandSep* pSep = rRegionBand.mpFirstSep;
75 15465643 : while ( pSep )
76 : {
77 : // create new and copy data
78 5019985 : pNewSep = new ImplRegionBandSep;
79 5019985 : pNewSep->mnXLeft = pSep->mnXLeft;
80 5019985 : pNewSep->mnXRight = pSep->mnXRight;
81 5019985 : pNewSep->mbRemoved = pSep->mbRemoved;
82 5019985 : pNewSep->mpNextSep = NULL;
83 5019985 : if ( pSep == rRegionBand.mpFirstSep )
84 4775057 : mpFirstSep = pNewSep;
85 : else
86 244928 : pPrevSep->mpNextSep = pNewSep;
87 :
88 5019985 : pPrevSep = pNewSep;
89 5019985 : pSep = pSep->mpNextSep;
90 : }
91 :
92 5222829 : if ( ! bIgnorePoints)
93 : {
94 : // Copy points.
95 2 : ImplRegionBandPoint* pPoint = rRegionBand.mpFirstBandPoint;
96 2 : ImplRegionBandPoint* pPrevPointCopy = NULL;
97 8 : while (pPoint != NULL)
98 : {
99 4 : ImplRegionBandPoint* pPointCopy = new ImplRegionBandPoint();
100 4 : pPointCopy->mnX = pPoint->mnX;
101 4 : pPointCopy->mnLineId = pPoint->mnLineId;
102 4 : pPointCopy->mbEndPoint = pPoint->mbEndPoint;
103 4 : pPointCopy->meLineType = pPoint->meLineType;
104 :
105 4 : if (pPrevPointCopy != NULL)
106 2 : pPrevPointCopy->mpNextBandPoint = pPointCopy;
107 : else
108 2 : mpFirstBandPoint = pPointCopy;
109 :
110 4 : pPrevPointCopy = pPointCopy;
111 4 : pPoint = pPoint->mpNextBandPoint;
112 : }
113 : }
114 5222829 : }
115 :
116 7343788 : ImplRegionBand::~ImplRegionBand()
117 : {
118 : DBG_ASSERT( mpFirstBandPoint == NULL, "ImplRegionBand::~ImplRegionBand -> pointlist not empty" );
119 :
120 : // delete elements of the list
121 7343788 : ImplRegionBandSep* pSep = mpFirstSep;
122 20202572 : while ( pSep )
123 : {
124 5514996 : ImplRegionBandSep* pTempSep = pSep->mpNextSep;
125 5514996 : delete pSep;
126 5514996 : pSep = pTempSep;
127 : }
128 :
129 : // delete elements of the list
130 7343788 : ImplRegionBandPoint* pPoint = mpFirstBandPoint;
131 14687576 : while ( pPoint )
132 : {
133 0 : ImplRegionBandPoint* pTempPoint = pPoint->mpNextBandPoint;
134 0 : delete pPoint;
135 0 : pPoint = pTempPoint;
136 : }
137 7343788 : }
138 :
139 : // generate separations from lines and process union with existing
140 : // separations
141 :
142 303 : void ImplRegionBand::ProcessPoints()
143 : {
144 : // check Pointlist
145 303 : ImplRegionBandPoint* pRegionBandPoint = mpFirstBandPoint;
146 1404 : while ( pRegionBandPoint )
147 : {
148 : // within list?
149 798 : if ( pRegionBandPoint->mpNextBandPoint )
150 : {
151 : // start/stop?
152 561 : if ( pRegionBandPoint->mbEndPoint && pRegionBandPoint->mpNextBandPoint->mbEndPoint )
153 : {
154 : // same direction? -> remove next point!
155 351 : if ( pRegionBandPoint->meLineType == pRegionBandPoint->mpNextBandPoint->meLineType )
156 : {
157 310 : ImplRegionBandPoint* pSaveRegionBandPoint = pRegionBandPoint->mpNextBandPoint;
158 310 : pRegionBandPoint->mpNextBandPoint = pRegionBandPoint->mpNextBandPoint->mpNextBandPoint;
159 310 : delete pSaveRegionBandPoint;
160 : }
161 : }
162 : }
163 :
164 : // continue with next element in the list
165 798 : pRegionBandPoint = pRegionBandPoint->mpNextBandPoint;
166 : }
167 :
168 303 : pRegionBandPoint = mpFirstBandPoint;
169 1005 : while ( pRegionBandPoint && pRegionBandPoint->mpNextBandPoint )
170 : {
171 399 : Union( pRegionBandPoint->mnX, pRegionBandPoint->mpNextBandPoint->mnX );
172 :
173 399 : ImplRegionBandPoint* pNextBandPoint = pRegionBandPoint->mpNextBandPoint->mpNextBandPoint;
174 :
175 : // remove already processed points
176 399 : delete pRegionBandPoint->mpNextBandPoint;
177 399 : delete pRegionBandPoint;
178 :
179 : // continue with next element in the list
180 399 : pRegionBandPoint = pNextBandPoint;
181 : }
182 :
183 : // remove last element if necessary
184 303 : delete pRegionBandPoint;
185 :
186 : // list is now empty
187 303 : mpFirstBandPoint = NULL;
188 303 : }
189 :
190 : // generate separations from lines and process union with existing
191 : // separations
192 :
193 1514 : bool ImplRegionBand::InsertPoint( long nX, long nLineId,
194 : bool bEndPoint, LineType eLineType )
195 : {
196 1514 : if ( !mpFirstBandPoint )
197 : {
198 297 : mpFirstBandPoint = new ImplRegionBandPoint;
199 297 : mpFirstBandPoint->mnX = nX;
200 297 : mpFirstBandPoint->mnLineId = nLineId;
201 297 : mpFirstBandPoint->mbEndPoint = bEndPoint;
202 297 : mpFirstBandPoint->meLineType = eLineType;
203 297 : mpFirstBandPoint->mpNextBandPoint = NULL;
204 297 : return true;
205 : }
206 :
207 : // look if line already touched the band
208 1217 : ImplRegionBandPoint* pRegionBandPoint = mpFirstBandPoint;
209 1217 : ImplRegionBandPoint* pLastTestedRegionBandPoint = NULL;
210 5097 : while( pRegionBandPoint )
211 : {
212 3073 : if ( pRegionBandPoint->mnLineId == nLineId )
213 : {
214 410 : if ( bEndPoint )
215 : {
216 48 : if( !pRegionBandPoint->mbEndPoint )
217 : {
218 : // remove old band point
219 48 : if( !mpFirstBandPoint->mpNextBandPoint )
220 : {
221 : // if we've only got one point => replace first point
222 24 : pRegionBandPoint->mnX = nX;
223 24 : pRegionBandPoint->mbEndPoint = true;
224 24 : return true;
225 : }
226 : else
227 : {
228 : // remove current point
229 24 : 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 24 : pLastTestedRegionBandPoint->mpNextBandPoint = pRegionBandPoint->mpNextBandPoint;
240 24 : delete pRegionBandPoint;
241 : }
242 :
243 24 : break;
244 : }
245 : }
246 : }
247 : else
248 362 : return false;
249 : }
250 :
251 : // use next element
252 2663 : pLastTestedRegionBandPoint = pRegionBandPoint;
253 2663 : pRegionBandPoint = pRegionBandPoint->mpNextBandPoint;
254 : }
255 :
256 : // search appropriate position and insert point into the list
257 : ImplRegionBandPoint* pNewRegionBandPoint;
258 :
259 831 : pRegionBandPoint = mpFirstBandPoint;
260 831 : pLastTestedRegionBandPoint = NULL;
261 3178 : while ( pRegionBandPoint )
262 : {
263 : // new point completely left? -> insert as first point
264 1885 : if ( nX <= pRegionBandPoint->mnX )
265 : {
266 369 : pNewRegionBandPoint = new ImplRegionBandPoint;
267 369 : pNewRegionBandPoint->mnX = nX;
268 369 : pNewRegionBandPoint->mnLineId = nLineId;
269 369 : pNewRegionBandPoint->mbEndPoint = bEndPoint;
270 369 : pNewRegionBandPoint->meLineType = eLineType;
271 369 : pNewRegionBandPoint->mpNextBandPoint = pRegionBandPoint;
272 :
273 : // connections to the new point
274 369 : if ( !pLastTestedRegionBandPoint )
275 199 : mpFirstBandPoint = pNewRegionBandPoint;
276 : else
277 170 : pLastTestedRegionBandPoint->mpNextBandPoint = pNewRegionBandPoint;
278 :
279 369 : return true;
280 : }
281 :
282 : // use next element
283 1516 : pLastTestedRegionBandPoint = pRegionBandPoint;
284 1516 : pRegionBandPoint = pRegionBandPoint->mpNextBandPoint;
285 : }
286 :
287 : // not inserted -> add to the end of the list
288 462 : pNewRegionBandPoint = new ImplRegionBandPoint;
289 462 : pNewRegionBandPoint->mnX = nX;
290 462 : pNewRegionBandPoint->mnLineId = nLineId;
291 462 : pNewRegionBandPoint->mbEndPoint = bEndPoint;
292 462 : pNewRegionBandPoint->meLineType = eLineType;
293 462 : pNewRegionBandPoint->mpNextBandPoint = NULL;
294 :
295 : // connections to the new point
296 462 : pLastTestedRegionBandPoint->mpNextBandPoint = pNewRegionBandPoint;
297 :
298 462 : return true;
299 : }
300 :
301 46298 : void ImplRegionBand::MoveX( long nHorzMove )
302 : {
303 : // move all x-separations
304 46298 : ImplRegionBandSep* pSep = mpFirstSep;
305 139827 : while ( pSep )
306 : {
307 47231 : pSep->mnXLeft += nHorzMove;
308 47231 : pSep->mnXRight += nHorzMove;
309 47231 : pSep = pSep->mpNextSep;
310 : }
311 46298 : }
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 5027384 : bool ImplRegionBand::OptimizeBand()
327 : {
328 5027384 : ImplRegionBandSep* pPrevSep = 0;
329 5027384 : ImplRegionBandSep* pSep = mpFirstSep;
330 15536853 : while ( pSep )
331 : {
332 : // remove?
333 5482085 : if ( pSep->mbRemoved || (pSep->mnXRight < pSep->mnXLeft) )
334 : {
335 598676 : ImplRegionBandSep* pOldSep = pSep;
336 598676 : if ( pSep == mpFirstSep )
337 498028 : mpFirstSep = pSep->mpNextSep;
338 : else
339 100648 : pPrevSep->mpNextSep = pSep->mpNextSep;
340 598676 : pSep = pSep->mpNextSep;
341 598676 : delete pOldSep;
342 598676 : continue;
343 : }
344 :
345 : // overlapping separations? -> combine!
346 4883409 : if ( pSep->mpNextSep )
347 : {
348 342385 : if ( (pSep->mnXRight+1) >= pSep->mpNextSep->mnXLeft )
349 : {
350 25561 : if ( pSep->mpNextSep->mnXRight > pSep->mnXRight )
351 24969 : pSep->mnXRight = pSep->mpNextSep->mnXRight;
352 :
353 25561 : ImplRegionBandSep* pOldSep = pSep->mpNextSep;
354 25561 : pSep->mpNextSep = pOldSep->mpNextSep;
355 25561 : delete pOldSep;
356 25561 : continue;
357 : }
358 : }
359 :
360 4857848 : pPrevSep = pSep;
361 4857848 : pSep = pSep->mpNextSep;
362 : }
363 :
364 5027384 : return true;
365 : }
366 :
367 1175966 : void ImplRegionBand::Union( long nXLeft, long nXRight )
368 : {
369 : DBG_ASSERT( nXLeft <= nXRight, "ImplRegionBand::Union(): nxLeft > nXRight" );
370 :
371 : // band empty? -> add element
372 1175966 : if ( !mpFirstSep )
373 : {
374 979835 : mpFirstSep = new ImplRegionBandSep;
375 979835 : mpFirstSep->mnXLeft = nXLeft;
376 979835 : mpFirstSep->mnXRight = nXRight;
377 979835 : mpFirstSep->mbRemoved = false;
378 979835 : mpFirstSep->mpNextSep = NULL;
379 979835 : return;
380 : }
381 :
382 : // process real union
383 : ImplRegionBandSep* pNewSep;
384 196131 : ImplRegionBandSep* pPrevSep = 0;
385 196131 : ImplRegionBandSep* pSep = mpFirstSep;
386 425671 : while ( pSep )
387 : {
388 : // new separation completely inside? nothing to do!
389 202931 : if ( (nXLeft >= pSep->mnXLeft) && (nXRight <= pSep->mnXRight) )
390 77067 : return;
391 :
392 : // new separation completely left? -> new separation!
393 125864 : if ( nXRight < pSep->mnXLeft )
394 : {
395 21443 : pNewSep = new ImplRegionBandSep;
396 21443 : pNewSep->mnXLeft = nXLeft;
397 21443 : pNewSep->mnXRight = nXRight;
398 21443 : pNewSep->mbRemoved = false;
399 :
400 21443 : pNewSep->mpNextSep = pSep;
401 21443 : if ( pSep == mpFirstSep )
402 19508 : mpFirstSep = pNewSep;
403 : else
404 1935 : pPrevSep->mpNextSep = pNewSep;
405 21443 : break;
406 : }
407 :
408 : // new separation overlapping from left? -> extend boundary
409 104421 : if ( (nXRight >= pSep->mnXLeft) && (nXLeft <= pSep->mnXLeft) )
410 39894 : pSep->mnXLeft = nXLeft;
411 :
412 : // new separation overlapping from right? -> extend boundary
413 104421 : if ( (nXLeft <= pSep->mnXRight) && (nXRight > pSep->mnXRight) )
414 : {
415 34052 : pSep->mnXRight = nXRight;
416 34052 : break;
417 : }
418 :
419 : // not inserted, but last element? -> add to the end of the list
420 70369 : if ( !pSep->mpNextSep && (nXLeft > pSep->mnXRight) )
421 : {
422 36960 : pNewSep = new ImplRegionBandSep;
423 36960 : pNewSep->mnXLeft = nXLeft;
424 36960 : pNewSep->mnXRight = nXRight;
425 36960 : pNewSep->mbRemoved = false;
426 :
427 36960 : pSep->mpNextSep = pNewSep;
428 36960 : pNewSep->mpNextSep = NULL;
429 36960 : break;
430 : }
431 :
432 33409 : pPrevSep = pSep;
433 33409 : pSep = pSep->mpNextSep;
434 : }
435 :
436 119064 : OptimizeBand();
437 : }
438 :
439 752420 : void ImplRegionBand::Intersect( long nXLeft, long nXRight )
440 : {
441 : DBG_ASSERT( nXLeft <= nXRight, "ImplRegionBand::Intersect(): nxLeft > nXRight" );
442 :
443 : // band has been touched
444 752420 : mbTouched = true;
445 :
446 : // band empty? -> nothing to do
447 752420 : if ( !mpFirstSep )
448 1237178 : return;
449 :
450 : // process real intersection
451 267662 : ImplRegionBandSep* pSep = mpFirstSep;
452 804519 : while ( pSep )
453 : {
454 : // new separation completely outside? -> remove separation
455 269195 : if ( (nXRight < pSep->mnXLeft) || (nXLeft > pSep->mnXRight) )
456 : // will be removed from the optimizer
457 5670 : pSep->mbRemoved = true;
458 :
459 : // new separation overlapping from left? -> reduce right boundary
460 513786 : if ( (nXLeft <= pSep->mnXLeft) &&
461 367120 : (nXRight <= pSep->mnXRight) &&
462 122529 : (nXRight >= pSep->mnXLeft) )
463 120450 : pSep->mnXRight = nXRight;
464 :
465 : // new separation overlapping from right? -> reduce right boundary
466 423480 : if ( (nXLeft >= pSep->mnXLeft) &&
467 304979 : (nXLeft <= pSep->mnXRight) &&
468 150694 : (nXRight >= pSep->mnXRight) )
469 143571 : pSep->mnXLeft = nXLeft;
470 :
471 : // new separation within the actual one? -> reduce both boundaries
472 269195 : if ( (nXLeft >= pSep->mnXLeft) && (nXRight <= pSep->mnXRight) )
473 : {
474 116774 : pSep->mnXRight = nXRight;
475 116774 : pSep->mnXLeft = nXLeft;
476 : }
477 :
478 269195 : pSep = pSep->mpNextSep;
479 : }
480 :
481 267662 : OptimizeBand();
482 : }
483 :
484 6472992 : void ImplRegionBand::Exclude( long nXLeft, long nXRight )
485 : {
486 : DBG_ASSERT( nXLeft <= nXRight, "ImplRegionBand::Exclude(): nxLeft > nXRight" );
487 :
488 : // band has been touched
489 6472992 : mbTouched = true;
490 :
491 : // band empty? -> nothing to do
492 6472992 : if ( !mpFirstSep )
493 8305326 : return;
494 :
495 : // process real exclusion
496 : ImplRegionBandSep* pNewSep;
497 4640658 : ImplRegionBandSep* pPrevSep = 0;
498 4640658 : ImplRegionBandSep* pSep = mpFirstSep;
499 14220758 : while ( pSep )
500 : {
501 4939442 : bool bSepProcessed = false;
502 :
503 : // new separation completely overlapping? -> remove separation
504 4939442 : if ( (nXLeft <= pSep->mnXLeft) && (nXRight >= pSep->mnXRight) )
505 : {
506 : // will be removed from the optimizer
507 550686 : pSep->mbRemoved = true;
508 550686 : bSepProcessed = true;
509 : }
510 :
511 : // new separation overlapping from left? -> reduce boundary
512 4939442 : if ( !bSepProcessed )
513 : {
514 4388756 : if ( (nXRight >= pSep->mnXLeft) && (nXLeft <= pSep->mnXLeft) )
515 : {
516 947698 : pSep->mnXLeft = nXRight+1;
517 947698 : bSepProcessed = true;
518 : }
519 : }
520 :
521 : // new separation overlapping from right? -> reduce boundary
522 4939442 : if ( !bSepProcessed )
523 : {
524 3441058 : if ( (nXLeft <= pSep->mnXRight) && (nXRight > pSep->mnXRight) )
525 : {
526 740503 : pSep->mnXRight = nXLeft-1;
527 740503 : bSepProcessed = true;
528 : }
529 : }
530 :
531 : // new separation within the actual one? -> reduce boundary
532 : // and add new entry for reminder
533 4939442 : if ( !bSepProcessed )
534 : {
535 2700555 : if ( (nXLeft >= pSep->mnXLeft) && (nXRight <= pSep->mnXRight) )
536 : {
537 81248 : pNewSep = new ImplRegionBandSep;
538 81248 : pNewSep->mnXLeft = pSep->mnXLeft;
539 81248 : pNewSep->mnXRight = nXLeft-1;
540 81248 : pNewSep->mbRemoved = false;
541 :
542 81248 : pSep->mnXLeft = nXRight+1;
543 :
544 : // connections from the new separation
545 81248 : pNewSep->mpNextSep = pSep;
546 :
547 : // connections to the new separation
548 81248 : if ( pSep == mpFirstSep )
549 80729 : mpFirstSep = pNewSep;
550 : else
551 519 : pPrevSep->mpNextSep = pNewSep;
552 : }
553 : }
554 :
555 4939442 : pPrevSep = pSep;
556 4939442 : pSep = pSep->mpNextSep;
557 : }
558 :
559 4640658 : 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 336558 : long ImplRegionBand::GetXLeftBoundary() const
820 : {
821 : assert(mpFirstSep && "ImplRegionBand::XLeftBoundary -> no separation in band!");
822 :
823 336558 : return mpFirstSep->mnXLeft;
824 : }
825 :
826 336558 : long ImplRegionBand::GetXRightBoundary() const
827 : {
828 : DBG_ASSERT( mpFirstSep != NULL, "ImplRegionBand::XRightBoundary -> no separation in band!" );
829 :
830 : // search last separation
831 336558 : ImplRegionBandSep* pSep = mpFirstSep;
832 700497 : while ( pSep->mpNextSep )
833 27381 : pSep = pSep->mpNextSep;
834 336558 : return pSep->mnXRight;
835 : }
836 :
837 2198306 : bool ImplRegionBand::operator==( const ImplRegionBand& rRegionBand ) const
838 : {
839 2198306 : ImplRegionBandSep* pOwnRectBandSep = mpFirstSep;
840 2198306 : ImplRegionBandSep* pSecondRectBandSep = rRegionBand.mpFirstSep;
841 6094687 : while ( pOwnRectBandSep && pSecondRectBandSep )
842 : {
843 : // get boundaries of current rectangle
844 1843039 : long nOwnXLeft = pOwnRectBandSep->mnXLeft;
845 1843039 : long nSecondXLeft = pSecondRectBandSep->mnXLeft;
846 1843039 : if ( nOwnXLeft != nSecondXLeft )
847 93295 : return false;
848 :
849 1749744 : long nOwnXRight = pOwnRectBandSep->mnXRight;
850 1749744 : long nSecondXRight = pSecondRectBandSep->mnXRight;
851 1749744 : if ( nOwnXRight != nSecondXRight )
852 51669 : return false;
853 :
854 : // get next separation from current band
855 1698075 : pOwnRectBandSep = pOwnRectBandSep->mpNextSep;
856 :
857 : // get next separation from current band
858 1698075 : pSecondRectBandSep = pSecondRectBandSep->mpNextSep;
859 : }
860 :
861 : // different number of separations?
862 2053342 : if ( pOwnRectBandSep || pSecondRectBandSep )
863 425354 : return false;
864 :
865 1627988 : return true;
866 : }
867 :
868 2 : 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 2 : ImplRegionBand* pLowerBand = new ImplRegionBand(*this, false);
876 :
877 : // Adapt vertical coordinates.
878 2 : mnYBottom = nY-1;
879 2 : pLowerBand->mnYTop = nY;
880 :
881 : // Insert new band into list of bands.
882 2 : pLowerBand->mpNextBand = mpNextBand;
883 2 : mpNextBand = pLowerBand;
884 2 : pLowerBand->mpPrevBand = this;
885 2 : if (pLowerBand->mpNextBand != NULL)
886 2 : pLowerBand->mpNextBand->mpPrevBand = pLowerBand;
887 :
888 2 : return pLowerBand;
889 : }
890 :
891 : /* vim:set shiftwidth=4 softtabstop=4 expandtab: */
|
