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