| /************************************************************** |
| * |
| * Licensed to the Apache Software Foundation (ASF) under one |
| * or more contributor license agreements. See the NOTICE file |
| * distributed with this work for additional information |
| * regarding copyright ownership. The ASF licenses this file |
| * to you under the Apache License, Version 2.0 (the |
| * "License"); you may not use this file except in compliance |
| * with the License. You may obtain a copy of the License at |
| * |
| * http://www.apache.org/licenses/LICENSE-2.0 |
| * |
| * Unless required by applicable law or agreed to in writing, |
| * software distributed under the License is distributed on an |
| * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY |
| * KIND, either express or implied. See the License for the |
| * specific language governing permissions and limitations |
| * under the License. |
| * |
| *************************************************************/ |
| |
| // MARKER(update_precomp.py): autogen include statement, do not remove |
| #include "precompiled_vcl.hxx" |
| |
| #include <tools/stream.hxx> |
| #include <tools/debug.hxx> |
| #include <regionband.hxx> |
| |
| ////////////////////////////////////////////////////////////////////////////// |
| |
| DBG_NAME( RegionBand ) |
| DBG_NAMEEX( Polygon ) |
| DBG_NAMEEX( PolyPolygon ) |
| |
| ////////////////////////////////////////////////////////////////////////////// |
| |
| RegionBand::RegionBand() |
| : mpFirstBand(0), |
| mpLastCheckedBand(0) |
| { |
| DBG_CTOR(RegionBand, ImplDbgTestRegionBand); |
| } |
| |
| RegionBand::RegionBand(const RegionBand& rRef) |
| : mpFirstBand(0), |
| mpLastCheckedBand(0) |
| { |
| *this = rRef; |
| DBG_CTOR(RegionBand, ImplDbgTestRegionBand); |
| } |
| |
| RegionBand& RegionBand::operator=(const RegionBand& rRef) |
| { |
| ImplRegionBand* pPrevBand = 0; |
| ImplRegionBand* pBand = rRef.mpFirstBand; |
| |
| while(pBand) |
| { |
| ImplRegionBand* pNewBand = new ImplRegionBand(*pBand); |
| |
| // first element? -> set as first into the list |
| if(pBand == rRef.mpFirstBand) |
| { |
| mpFirstBand = pNewBand; |
| } |
| else |
| { |
| pPrevBand->mpNextBand = pNewBand; |
| } |
| |
| pPrevBand = pNewBand; |
| pBand = pBand->mpNextBand; |
| } |
| |
| DBG_CHKTHIS(RegionBand, ImplDbgTestRegionBand); |
| DBG_CHKOBJ(&rRef, RegionBand, ImplDbgTestRegionBand); |
| |
| return *this; |
| } |
| |
| RegionBand::RegionBand(const Rectangle& rRect) |
| : mpFirstBand(0), |
| mpLastCheckedBand(0) |
| { |
| const long nTop(std::min(rRect.Top(), rRect.Bottom())); |
| const long nBottom(std::max(rRect.Top(), rRect.Bottom())); |
| const long nLeft(std::min(rRect.Left(), rRect.Right())); |
| const long nRight(std::max(rRect.Left(), rRect.Right())); |
| |
| // add band with boundaries of the rectangle |
| mpFirstBand = new ImplRegionBand(nTop, nBottom); |
| |
| // Set left and right boundaries of the band |
| mpFirstBand->Union(nLeft, nRight); |
| |
| DBG_CTOR(RegionBand, ImplDbgTestRegionBand); |
| } |
| |
| void RegionBand::implReset() |
| { |
| ImplRegionBand* pBand = mpFirstBand; |
| |
| while(pBand) |
| { |
| ImplRegionBand* pTempBand = pBand->mpNextBand; |
| delete pBand; |
| pBand = pTempBand; |
| } |
| |
| mpLastCheckedBand = 0; |
| |
| DBG_CHKTHIS(RegionBand, ImplDbgTestRegionBand); |
| } |
| |
| RegionBand::~RegionBand() |
| { |
| implReset(); |
| DBG_DTOR(RegionBand, ImplDbgTestRegionBand); |
| } |
| |
| bool RegionBand::operator==( const RegionBand& rRegionBand ) const |
| { |
| DBG_CHKTHIS(RegionBand, ImplDbgTestRegionBand); |
| DBG_CHKOBJ(&rRegionBand, RegionBand, ImplDbgTestRegionBand); |
| |
| // initialise pointers |
| ImplRegionBand* pOwnRectBand = mpFirstBand; |
| ImplRegionBandSep* pOwnRectBandSep = pOwnRectBand->mpFirstSep; |
| ImplRegionBand* pSecondRectBand = rRegionBand.mpFirstBand; |
| ImplRegionBandSep* pSecondRectBandSep = pSecondRectBand->mpFirstSep; |
| |
| while ( pOwnRectBandSep && pSecondRectBandSep ) |
| { |
| // get boundaries of current rectangle |
| long nOwnXLeft = pOwnRectBandSep->mnXLeft; |
| long nSecondXLeft = pSecondRectBandSep->mnXLeft; |
| |
| if ( nOwnXLeft != nSecondXLeft ) |
| { |
| return false; |
| } |
| |
| long nOwnYTop = pOwnRectBand->mnYTop; |
| long nSecondYTop = pSecondRectBand->mnYTop; |
| |
| if ( nOwnYTop != nSecondYTop ) |
| { |
| return false; |
| } |
| |
| long nOwnXRight = pOwnRectBandSep->mnXRight; |
| long nSecondXRight = pSecondRectBandSep->mnXRight; |
| |
| if ( nOwnXRight != nSecondXRight ) |
| { |
| return false; |
| } |
| |
| long nOwnYBottom = pOwnRectBand->mnYBottom; |
| long nSecondYBottom = pSecondRectBand->mnYBottom; |
| |
| if ( nOwnYBottom != nSecondYBottom ) |
| { |
| return false; |
| } |
| |
| // get next separation from current band |
| pOwnRectBandSep = pOwnRectBandSep->mpNextSep; |
| |
| // no separation found? -> go to next band! |
| if ( !pOwnRectBandSep ) |
| { |
| // get next band |
| pOwnRectBand = pOwnRectBand->mpNextBand; |
| |
| // get first separation in current band |
| if( pOwnRectBand ) |
| { |
| pOwnRectBandSep = pOwnRectBand->mpFirstSep; |
| } |
| } |
| |
| // get next separation from current band |
| pSecondRectBandSep = pSecondRectBandSep->mpNextSep; |
| |
| // no separation found? -> go to next band! |
| if ( !pSecondRectBandSep ) |
| { |
| // get next band |
| pSecondRectBand = pSecondRectBand->mpNextBand; |
| |
| // get first separation in current band |
| if( pSecondRectBand ) |
| { |
| pSecondRectBandSep = pSecondRectBand->mpFirstSep; |
| } |
| } |
| |
| if ( pOwnRectBandSep && !pSecondRectBandSep ) |
| { |
| return false; |
| } |
| |
| if ( !pOwnRectBandSep && pSecondRectBandSep ) |
| { |
| return false; |
| } |
| } |
| |
| return true; |
| } |
| |
| enum StreamEntryType { STREAMENTRY_BANDHEADER, STREAMENTRY_SEPARATION, STREAMENTRY_END }; |
| |
| void RegionBand::load(SvStream& rIStrm) |
| { |
| // clear this nstance's data |
| implReset(); |
| |
| // get all bands |
| ImplRegionBand* pCurrBand = 0; |
| |
| // get header from first element |
| sal_uInt16 nTmp16(0); |
| rIStrm >> nTmp16; |
| |
| while(STREAMENTRY_END != (StreamEntryType)nTmp16) |
| { |
| // insert new band or new separation? |
| if(STREAMENTRY_BANDHEADER == (StreamEntryType)nTmp16) |
| { |
| long nYTop; |
| long nYBottom; |
| |
| rIStrm >> nYTop; |
| rIStrm >> nYBottom; |
| |
| // create band |
| ImplRegionBand* pNewBand = new ImplRegionBand( nYTop, nYBottom ); |
| |
| // first element? -> set as first into the list |
| if ( !pCurrBand ) |
| { |
| mpFirstBand = pNewBand; |
| } |
| else |
| { |
| pCurrBand->mpNextBand = pNewBand; |
| } |
| |
| // save pointer for next creation |
| pCurrBand = pNewBand; |
| } |
| else |
| { |
| long nXLeft; |
| long nXRight; |
| |
| rIStrm >> nXLeft; |
| rIStrm >> nXRight; |
| |
| // add separation |
| if ( pCurrBand ) |
| { |
| pCurrBand->Union( nXLeft, nXRight ); |
| } |
| } |
| |
| if( rIStrm.IsEof() ) |
| { |
| DBG_ERROR( "premature end of region stream" ); |
| implReset(); |
| return; |
| } |
| |
| // get next header |
| rIStrm >> nTmp16; |
| } |
| |
| DBG_CHKTHIS(RegionBand, ImplDbgTestRegionBand); |
| } |
| |
| void RegionBand::save(SvStream& rOStrm) const |
| { |
| DBG_CHKTHIS(RegionBand, ImplDbgTestRegionBand); |
| ImplRegionBand* pBand = mpFirstBand; |
| |
| while(pBand) |
| { |
| // put boundaries |
| rOStrm << (sal_uInt16)STREAMENTRY_BANDHEADER; |
| rOStrm << pBand->mnYTop; |
| rOStrm << pBand->mnYBottom; |
| |
| // put separations of current band |
| ImplRegionBandSep* pSep = pBand->mpFirstSep; |
| |
| while(pSep) |
| { |
| // put separation |
| rOStrm << (sal_uInt16)STREAMENTRY_SEPARATION; |
| rOStrm << pSep->mnXLeft; |
| rOStrm << pSep->mnXRight; |
| |
| // next separation from current band |
| pSep = pSep->mpNextSep; |
| } |
| |
| pBand = pBand->mpNextBand; |
| } |
| |
| // put endmarker |
| rOStrm << (sal_uInt16)STREAMENTRY_END; |
| } |
| |
| bool RegionBand::isSingleRectangle() const |
| { |
| // just one band? |
| if(mpFirstBand && !mpFirstBand->mpNextBand) |
| { |
| // just one sep? |
| if(mpFirstBand->mpFirstSep && !mpFirstBand->mpFirstSep->mpNextSep) |
| { |
| return true; |
| } |
| } |
| |
| return false; |
| } |
| |
| void RegionBand::InsertBand(ImplRegionBand* pPreviousBand, ImplRegionBand* pBandToInsert) |
| { |
| OSL_ASSERT(pBandToInsert!=NULL); |
| |
| if(!pPreviousBand) |
| { |
| // Insert band before all others. |
| if(mpFirstBand) |
| { |
| mpFirstBand->mpPrevBand = pBandToInsert; |
| } |
| |
| pBandToInsert->mpNextBand = mpFirstBand; |
| mpFirstBand = pBandToInsert; |
| } |
| else |
| { |
| // Insert band directly after pPreviousBand. |
| pBandToInsert->mpNextBand = pPreviousBand->mpNextBand; |
| pPreviousBand->mpNextBand = pBandToInsert; |
| pBandToInsert->mpPrevBand = pPreviousBand; |
| } |
| |
| DBG_CHKTHIS(RegionBand, ImplDbgTestRegionBand); |
| } |
| |
| void RegionBand::processPoints() |
| { |
| ImplRegionBand* pRegionBand = mpFirstBand; |
| |
| while(pRegionBand) |
| { |
| // generate separations from the lines and process union |
| pRegionBand->ProcessPoints(); |
| pRegionBand = pRegionBand->mpNextBand; |
| } |
| |
| DBG_CHKTHIS(RegionBand, ImplDbgTestRegionBand); |
| } |
| |
| /** This function is similar to the RegionBand::InsertBands() method. |
| It creates a minimal set of missing bands so that the entire vertical |
| interval from nTop to nBottom is covered by bands. |
| */ |
| void RegionBand::ImplAddMissingBands(const long nTop, const long nBottom) |
| { |
| // Iterate over already existing bands and add missing bands atop the |
| // first and between two bands. |
| ImplRegionBand* pPreviousBand = NULL; |
| ImplRegionBand* pBand = ImplGetFirstRegionBand(); |
| long nCurrentTop (nTop); |
| |
| while (pBand != NULL && nCurrentTop<nBottom) |
| { |
| if (nCurrentTop < pBand->mnYTop) |
| { |
| // Create new band above the current band. |
| ImplRegionBand* pAboveBand = new ImplRegionBand( |
| nCurrentTop, |
| ::std::min(nBottom,pBand->mnYTop-1)); |
| InsertBand(pPreviousBand, pAboveBand); |
| } |
| |
| // Adapt the top of the interval to prevent overlapping bands. |
| nCurrentTop = ::std::max(nTop, pBand->mnYBottom+1); |
| |
| // Advance to next band. |
| pPreviousBand = pBand; |
| pBand = pBand->mpNextBand; |
| } |
| |
| // We still have to cover two cases: |
| // 1. The region does not yet contain any bands. |
| // 2. The intervall nTop->nBottom extends past the bottom most band. |
| if (nCurrentTop <= nBottom |
| && (pBand==NULL || nBottom>pBand->mnYBottom)) |
| { |
| // When there is no previous band then the new one will be the |
| // first. Otherwise the new band is inserted behind the last band. |
| InsertBand( |
| pPreviousBand, |
| new ImplRegionBand( |
| nCurrentTop, |
| nBottom)); |
| } |
| |
| DBG_CHKTHIS(RegionBand, ImplDbgTestRegionBand); |
| } |
| |
| void RegionBand::CreateBandRange(long nYTop, long nYBottom) |
| { |
| // add top band |
| mpFirstBand = new ImplRegionBand( nYTop-1, nYTop-1 ); |
| |
| // begin first search from the first element |
| mpLastCheckedBand = mpFirstBand; |
| ImplRegionBand* pBand = mpFirstBand; |
| |
| for ( int i = nYTop; i <= nYBottom+1; i++ ) |
| { |
| // create new band |
| ImplRegionBand* pNewBand = new ImplRegionBand( i, i ); |
| pBand->mpNextBand = pNewBand; |
| |
| if ( pBand != mpFirstBand ) |
| { |
| pNewBand->mpPrevBand = pBand; |
| } |
| |
| pBand = pBand->mpNextBand; |
| } |
| |
| DBG_CHKTHIS(RegionBand, ImplDbgTestRegionBand); |
| } |
| |
| bool RegionBand::InsertLine(const Point& rStartPt, const Point& rEndPt, long nLineId) |
| { |
| long nX, nY; |
| |
| // lines consisting of a single point do not interest here |
| if ( rStartPt == rEndPt ) |
| { |
| DBG_CHKTHIS(RegionBand, ImplDbgTestRegionBand); |
| return true; |
| } |
| |
| LineType eLineType = (rStartPt.Y() > rEndPt.Y()) ? LINE_DESCENDING : LINE_ASCENDING; |
| if ( rStartPt.X() == rEndPt.X() ) |
| { |
| // vertical line |
| const long nEndY = rEndPt.Y(); |
| |
| nX = rStartPt.X(); |
| nY = rStartPt.Y(); |
| |
| if( nEndY > nY ) |
| { |
| for ( ; nY <= nEndY; nY++ ) |
| { |
| Point aNewPoint( nX, nY ); |
| InsertPoint( aNewPoint, nLineId, |
| (aNewPoint == rEndPt) || (aNewPoint == rStartPt), |
| eLineType ); |
| } |
| } |
| else |
| { |
| for ( ; nY >= nEndY; nY-- ) |
| { |
| Point aNewPoint( nX, nY ); |
| InsertPoint( aNewPoint, nLineId, |
| (aNewPoint == rEndPt) || (aNewPoint == rStartPt), |
| eLineType ); |
| } |
| } |
| } |
| else if ( rStartPt.Y() != rEndPt.Y() ) |
| { |
| const long nDX = labs( rEndPt.X() - rStartPt.X() ); |
| const long nDY = labs( rEndPt.Y() - rStartPt.Y() ); |
| const long nStartX = rStartPt.X(); |
| const long nStartY = rStartPt.Y(); |
| const long nEndX = rEndPt.X(); |
| const long nEndY = rEndPt.Y(); |
| const long nXInc = ( nStartX < nEndX ) ? 1L : -1L; |
| const long nYInc = ( nStartY < nEndY ) ? 1L : -1L; |
| |
| if ( nDX >= nDY ) |
| { |
| const long nDYX = ( nDY - nDX ) << 1; |
| const long nDY2 = nDY << 1; |
| long nD = nDY2 - nDX; |
| |
| for ( nX = nStartX, nY = nStartY; nX != nEndX; nX += nXInc ) |
| { |
| InsertPoint( Point( nX, nY ), nLineId, nStartX == nX, eLineType ); |
| |
| if ( nD < 0L ) |
| nD += nDY2; |
| else |
| nD += nDYX, nY += nYInc; |
| } |
| } |
| else |
| { |
| const long nDYX = ( nDX - nDY ) << 1; |
| const long nDY2 = nDX << 1; |
| long nD = nDY2 - nDY; |
| |
| for ( nX = nStartX, nY = nStartY; nY != nEndY; nY += nYInc ) |
| { |
| InsertPoint( Point( nX, nY ), nLineId, nStartY == nY, eLineType ); |
| |
| if ( nD < 0L ) |
| nD += nDY2; |
| else |
| nD += nDYX, nX += nXInc; |
| } |
| } |
| |
| // last point |
| InsertPoint( Point( nEndX, nEndY ), nLineId, true, eLineType ); |
| } |
| |
| DBG_CHKTHIS(RegionBand, ImplDbgTestRegionBand); |
| return true; |
| } |
| |
| bool RegionBand::InsertPoint(const Point &rPoint, long nLineID, bool bEndPoint, LineType eLineType) |
| { |
| DBG_ASSERT( mpFirstBand != NULL, "RegionBand::InsertPoint - no bands available!" ); |
| |
| if ( rPoint.Y() == mpLastCheckedBand->mnYTop ) |
| { |
| mpLastCheckedBand->InsertPoint( rPoint.X(), nLineID, bEndPoint, eLineType ); |
| return true; |
| } |
| |
| if ( rPoint.Y() > mpLastCheckedBand->mnYTop ) |
| { |
| // Search ascending |
| while ( mpLastCheckedBand ) |
| { |
| // Insert point if possible |
| if ( rPoint.Y() == mpLastCheckedBand->mnYTop ) |
| { |
| mpLastCheckedBand->InsertPoint( rPoint.X(), nLineID, bEndPoint, eLineType ); |
| DBG_CHKTHIS(RegionBand, ImplDbgTestRegionBand); |
| return true; |
| } |
| |
| mpLastCheckedBand = mpLastCheckedBand->mpNextBand; |
| } |
| |
| DBG_ERROR( "RegionBand::InsertPoint reached the end of the list!" ); |
| } |
| else |
| { |
| // Search descending |
| while ( mpLastCheckedBand ) |
| { |
| // Insert point if possible |
| if ( rPoint.Y() == mpLastCheckedBand->mnYTop ) |
| { |
| mpLastCheckedBand->InsertPoint( rPoint.X(), nLineID, bEndPoint, eLineType ); |
| DBG_CHKTHIS(RegionBand, ImplDbgTestRegionBand); |
| return true; |
| } |
| |
| mpLastCheckedBand = mpLastCheckedBand->mpPrevBand; |
| } |
| |
| DBG_ERROR( "RegionBand::InsertPoint reached the beginning of the list!" ); |
| } |
| |
| DBG_ERROR( "RegionBand::InsertPoint point not inserted!" ); |
| |
| // reinitialize pointer (should never be reached!) |
| mpLastCheckedBand = mpFirstBand; |
| |
| DBG_CHKTHIS(RegionBand, ImplDbgTestRegionBand); |
| return false; |
| } |
| |
| bool RegionBand::OptimizeBandList() |
| { |
| ImplRegionBand* pPrevBand = 0; |
| ImplRegionBand* pBand = mpFirstBand; |
| |
| while ( pBand ) |
| { |
| const bool bBTEqual = pBand->mpNextBand && (pBand->mnYBottom == pBand->mpNextBand->mnYTop); |
| |
| // no separation? -> remove! |
| if ( pBand->IsEmpty() || (bBTEqual && (pBand->mnYBottom == pBand->mnYTop)) ) |
| { |
| // save pointer |
| ImplRegionBand* pOldBand = pBand; |
| |
| // previous element of the list |
| if ( pBand == mpFirstBand ) |
| mpFirstBand = pBand->mpNextBand; |
| else |
| pPrevBand->mpNextBand = pBand->mpNextBand; |
| |
| pBand = pBand->mpNextBand; |
| delete pOldBand; |
| } |
| else |
| { |
| // fixup |
| if ( bBTEqual ) |
| pBand->mnYBottom = pBand->mpNextBand->mnYTop-1; |
| |
| // this and next band with equal separations? -> combine! |
| if ( pBand->mpNextBand && |
| ((pBand->mnYBottom+1) == pBand->mpNextBand->mnYTop) && |
| (*pBand == *pBand->mpNextBand) ) |
| { |
| // expand current height |
| pBand->mnYBottom = pBand->mpNextBand->mnYBottom; |
| |
| // remove next band from list |
| ImplRegionBand* pDeletedBand = pBand->mpNextBand; |
| pBand->mpNextBand = pDeletedBand->mpNextBand; |
| delete pDeletedBand; |
| |
| // check band again! |
| } |
| else |
| { |
| // count rectangles within band |
| ImplRegionBandSep* pSep = pBand->mpFirstSep; |
| while ( pSep ) |
| { |
| pSep = pSep->mpNextSep; |
| } |
| |
| pPrevBand = pBand; |
| pBand = pBand->mpNextBand; |
| } |
| } |
| } |
| |
| #ifdef DBG_UTIL |
| pBand = mpFirstBand; |
| while ( pBand ) |
| { |
| DBG_ASSERT( pBand->mpFirstSep != NULL, "Exiting RegionBand::OptimizeBandList(): empty band in region!" ); |
| |
| if ( pBand->mnYBottom < pBand->mnYTop ) |
| DBG_ERROR( "RegionBand::OptimizeBandList(): YBottomBoundary < YTopBoundary" ); |
| |
| if ( pBand->mpNextBand ) |
| { |
| if ( pBand->mnYBottom >= pBand->mpNextBand->mnYTop ) |
| DBG_ERROR( "RegionBand::OptimizeBandList(): overlapping bands in region!" ); |
| } |
| |
| pBand = pBand->mpNextBand; |
| } |
| #endif |
| |
| DBG_CHKTHIS(RegionBand, ImplDbgTestRegionBand); |
| return (0 != mpFirstBand); |
| } |
| |
| void RegionBand::Move(long nHorzMove, long nVertMove) |
| { |
| ImplRegionBand* pBand = mpFirstBand; |
| |
| while(pBand) |
| { |
| // process the vertical move |
| if(nVertMove) |
| { |
| pBand->mnYTop = pBand->mnYTop + nVertMove; |
| pBand->mnYBottom = pBand->mnYBottom + nVertMove; |
| } |
| |
| // process the horizontal move |
| if(nHorzMove) |
| { |
| pBand->MoveX(nHorzMove); |
| } |
| |
| pBand = pBand->mpNextBand; |
| } |
| |
| DBG_CHKTHIS(RegionBand, ImplDbgTestRegionBand); |
| } |
| |
| void RegionBand::Scale(double fScaleX, double fScaleY) |
| { |
| ImplRegionBand* pBand = mpFirstBand; |
| |
| while(pBand) |
| { |
| // process the vertical move |
| if(0.0 != fScaleY) |
| { |
| pBand->mnYTop = basegfx::fround(pBand->mnYTop * fScaleY); |
| pBand->mnYBottom = basegfx::fround(pBand->mnYBottom * fScaleY); |
| } |
| |
| // process the horizontal move |
| if(0.0 != fScaleX) |
| { |
| pBand->ScaleX(fScaleX); |
| } |
| |
| pBand = pBand->mpNextBand; |
| } |
| |
| DBG_CHKTHIS(RegionBand, ImplDbgTestRegionBand); |
| } |
| |
| void RegionBand::InsertBands(long nTop, long nBottom) |
| { |
| // region empty? -> set rectagle as first entry! |
| if ( !mpFirstBand ) |
| { |
| // add band with boundaries of the rectangle |
| mpFirstBand = new ImplRegionBand( nTop, nBottom ); |
| DBG_CHKTHIS(RegionBand, ImplDbgTestRegionBand); |
| return; |
| } |
| |
| // find/insert bands for the boundaries of the rectangle |
| bool bTopBoundaryInserted = false; |
| bool bTop2BoundaryInserted = false; |
| bool bBottomBoundaryInserted = false; |
| |
| // special case: top boundary is above the first band |
| ImplRegionBand* pNewBand; |
| |
| if ( nTop < mpFirstBand->mnYTop ) |
| { |
| // create new band above the first in the list |
| pNewBand = new ImplRegionBand( nTop, mpFirstBand->mnYTop ); |
| |
| if ( nBottom < mpFirstBand->mnYTop ) |
| { |
| pNewBand->mnYBottom = nBottom; |
| } |
| |
| // insert band into the list |
| pNewBand->mpNextBand = mpFirstBand; |
| mpFirstBand = pNewBand; |
| |
| bTopBoundaryInserted = true; |
| } |
| |
| // insert band(s) into the list |
| ImplRegionBand* pBand = mpFirstBand; |
| |
| while ( pBand ) |
| { |
| // Insert Bands if possible |
| if ( !bTopBoundaryInserted ) |
| { |
| bTopBoundaryInserted = InsertSingleBand( pBand, nTop - 1 ); |
| } |
| |
| if ( !bTop2BoundaryInserted ) |
| { |
| bTop2BoundaryInserted = InsertSingleBand( pBand, nTop ); |
| } |
| |
| if ( !bBottomBoundaryInserted && (nTop != nBottom) ) |
| { |
| bBottomBoundaryInserted = InsertSingleBand( pBand, nBottom ); |
| } |
| |
| // both boundaries inserted? -> nothing more to do |
| if ( bTopBoundaryInserted && bTop2BoundaryInserted && bBottomBoundaryInserted ) |
| { |
| break; |
| } |
| |
| // insert bands between two bands if neccessary |
| if ( pBand->mpNextBand ) |
| { |
| if ( (pBand->mnYBottom + 1) < pBand->mpNextBand->mnYTop ) |
| { |
| // copy band with list and set new boundary |
| pNewBand = new ImplRegionBand( pBand->mnYBottom+1, pBand->mpNextBand->mnYTop-1 ); |
| |
| // insert band into the list |
| pNewBand->mpNextBand = pBand->mpNextBand; |
| pBand->mpNextBand = pNewBand; |
| } |
| } |
| |
| pBand = pBand->mpNextBand; |
| } |
| |
| DBG_CHKTHIS(RegionBand, ImplDbgTestRegionBand); |
| } |
| |
| bool RegionBand::InsertSingleBand(ImplRegionBand* pBand, long nYBandPosition) |
| { |
| // boundary already included in band with height 1? -> nothing to do! |
| if ( (pBand->mnYTop == pBand->mnYBottom) && (nYBandPosition == pBand->mnYTop) ) |
| { |
| DBG_CHKTHIS(RegionBand, ImplDbgTestRegionBand); |
| return true; |
| } |
| |
| // insert single height band on top? |
| ImplRegionBand* pNewBand; |
| |
| if ( nYBandPosition == pBand->mnYTop ) |
| { |
| // copy band with list and set new boundary |
| pNewBand = new ImplRegionBand( *pBand ); |
| pNewBand->mnYTop = nYBandPosition+1; |
| |
| // insert band into the list |
| pNewBand->mpNextBand = pBand->mpNextBand; |
| pBand->mnYBottom = nYBandPosition; |
| pBand->mpNextBand = pNewBand; |
| |
| DBG_CHKTHIS(RegionBand, ImplDbgTestRegionBand); |
| return true; |
| } |
| |
| // top of new rectangle within the current band? -> insert new band and copy data |
| if ( (nYBandPosition > pBand->mnYTop) && (nYBandPosition < pBand->mnYBottom) ) |
| { |
| // copy band with list and set new boundary |
| pNewBand = new ImplRegionBand( *pBand ); |
| pNewBand->mnYTop = nYBandPosition; |
| |
| // insert band into the list |
| pNewBand->mpNextBand = pBand->mpNextBand; |
| pBand->mnYBottom = nYBandPosition; |
| pBand->mpNextBand = pNewBand; |
| |
| // copy band with list and set new boundary |
| pNewBand = new ImplRegionBand( *pBand ); |
| pNewBand->mnYTop = nYBandPosition; |
| |
| // insert band into the list |
| pBand->mpNextBand->mnYTop = nYBandPosition+1; |
| |
| pNewBand->mpNextBand = pBand->mpNextBand; |
| pBand->mnYBottom = nYBandPosition - 1; |
| pBand->mpNextBand = pNewBand; |
| |
| DBG_CHKTHIS(RegionBand, ImplDbgTestRegionBand); |
| return true; |
| } |
| |
| // create new band behind the current in the list |
| if ( !pBand->mpNextBand ) |
| { |
| if ( nYBandPosition == pBand->mnYBottom ) |
| { |
| // copy band with list and set new boundary |
| pNewBand = new ImplRegionBand( *pBand ); |
| pNewBand->mnYTop = pBand->mnYBottom; |
| pNewBand->mnYBottom = nYBandPosition; |
| |
| pBand->mnYBottom = nYBandPosition-1; |
| |
| // append band to the list |
| pBand->mpNextBand = pNewBand; |
| DBG_CHKTHIS(RegionBand, ImplDbgTestRegionBand); |
| return true; |
| } |
| |
| if ( nYBandPosition > pBand->mnYBottom ) |
| { |
| // create new band |
| pNewBand = new ImplRegionBand( pBand->mnYBottom + 1, nYBandPosition ); |
| |
| // append band to the list |
| pBand->mpNextBand = pNewBand; |
| DBG_CHKTHIS(RegionBand, ImplDbgTestRegionBand); |
| return true; |
| } |
| } |
| |
| DBG_CHKTHIS(RegionBand, ImplDbgTestRegionBand); |
| return false; |
| } |
| |
| void RegionBand::Union(long nLeft, long nTop, long nRight, long nBottom) |
| { |
| DBG_ASSERT( nLeft <= nRight, "RegionBand::Union() - nLeft > nRight" ); |
| DBG_ASSERT( nTop <= nBottom, "RegionBand::Union() - nTop > nBottom" ); |
| |
| // process union |
| ImplRegionBand* pBand = mpFirstBand; |
| while ( pBand ) |
| { |
| if ( pBand->mnYTop >= nTop ) |
| { |
| if ( pBand->mnYBottom <= nBottom ) |
| pBand->Union( nLeft, nRight ); |
| else |
| { |
| #ifdef DBG_UTIL |
| long nCurY = pBand->mnYBottom; |
| pBand = pBand->mpNextBand; |
| while ( pBand ) |
| { |
| if ( (pBand->mnYTop < nCurY) || (pBand->mnYBottom < nCurY) ) |
| { |
| DBG_ERROR( "RegionBand::Union() - Bands not sorted!" ); |
| } |
| pBand = pBand->mpNextBand; |
| } |
| #endif |
| break; |
| } |
| } |
| |
| pBand = pBand->mpNextBand; |
| } |
| |
| DBG_CHKTHIS(RegionBand, ImplDbgTestRegionBand); |
| } |
| |
| void RegionBand::Intersect(long nLeft, long nTop, long nRight, long nBottom) |
| { |
| // process intersections |
| ImplRegionBand* pPrevBand = 0; |
| ImplRegionBand* pBand = mpFirstBand; |
| |
| while(pBand) |
| { |
| // band within intersection boundary? -> process. otherwise remove |
| if((pBand->mnYTop >= nTop) && (pBand->mnYBottom <= nBottom)) |
| { |
| // process intersection |
| pBand->Intersect(nLeft, nRight); |
| pPrevBand = pBand; |
| pBand = pBand->mpNextBand; |
| } |
| else |
| { |
| ImplRegionBand* pOldBand = pBand; |
| |
| if(pBand == mpFirstBand) |
| { |
| mpFirstBand = pBand->mpNextBand; |
| } |
| else |
| { |
| pPrevBand->mpNextBand = pBand->mpNextBand; |
| } |
| |
| pBand = pBand->mpNextBand; |
| delete pOldBand; |
| } |
| } |
| |
| DBG_CHKTHIS(RegionBand, ImplDbgTestRegionBand); |
| } |
| |
| void RegionBand::Union(const RegionBand& rSource) |
| { |
| // apply all rectangles from rSource to this |
| ImplRegionBand* pBand = rSource.mpFirstBand; |
| |
| while ( pBand ) |
| { |
| // insert bands if the boundaries are not allready in the list |
| InsertBands(pBand->mnYTop, pBand->mnYBottom); |
| |
| // process all elements of the list |
| ImplRegionBandSep* pSep = pBand->mpFirstSep; |
| |
| while(pSep) |
| { |
| Union(pSep->mnXLeft, pBand->mnYTop, pSep->mnXRight, pBand->mnYBottom); |
| pSep = pSep->mpNextSep; |
| } |
| |
| pBand = pBand->mpNextBand; |
| } |
| |
| DBG_CHKTHIS(RegionBand, ImplDbgTestRegionBand); |
| } |
| |
| void RegionBand::Exclude(long nLeft, long nTop, long nRight, long nBottom) |
| { |
| DBG_ASSERT( nLeft <= nRight, "RegionBand::Exclude() - nLeft > nRight" ); |
| DBG_ASSERT( nTop <= nBottom, "RegionBand::Exclude() - nTop > nBottom" ); |
| |
| // process exclude |
| ImplRegionBand* pBand = mpFirstBand; |
| |
| while(pBand) |
| { |
| if(pBand->mnYTop >= nTop) |
| { |
| if(pBand->mnYBottom <= nBottom) |
| { |
| pBand->Exclude(nLeft, nRight); |
| } |
| else |
| { |
| #ifdef DBG_UTIL |
| long nCurY = pBand->mnYBottom; |
| pBand = pBand->mpNextBand; |
| |
| while(pBand) |
| { |
| if((pBand->mnYTop < nCurY) || (pBand->mnYBottom < nCurY)) |
| { |
| DBG_ERROR( "RegionBand::Exclude() - Bands not sorted!" ); |
| } |
| |
| pBand = pBand->mpNextBand; |
| } |
| #endif |
| break; |
| } |
| } |
| |
| pBand = pBand->mpNextBand; |
| } |
| |
| DBG_CHKTHIS(RegionBand, ImplDbgTestRegionBand); |
| } |
| |
| void RegionBand::XOr(long nLeft, long nTop, long nRight, long nBottom) |
| { |
| DBG_ASSERT( nLeft <= nRight, "RegionBand::Exclude() - nLeft > nRight" ); |
| DBG_ASSERT( nTop <= nBottom, "RegionBand::Exclude() - nTop > nBottom" ); |
| |
| // process xor |
| ImplRegionBand* pBand = mpFirstBand; |
| |
| while(pBand) |
| { |
| if(pBand->mnYTop >= nTop) |
| { |
| if(pBand->mnYBottom <= nBottom) |
| { |
| pBand->XOr(nLeft, nRight); |
| } |
| else |
| { |
| #ifdef DBG_UTIL |
| long nCurY = pBand->mnYBottom; |
| pBand = pBand->mpNextBand; |
| |
| while(pBand) |
| { |
| if((pBand->mnYTop < nCurY) || (pBand->mnYBottom < nCurY)) |
| { |
| DBG_ERROR( "RegionBand::XOr() - Bands not sorted!" ); |
| } |
| |
| pBand = pBand->mpNextBand; |
| } |
| #endif |
| break; |
| } |
| } |
| |
| pBand = pBand->mpNextBand; |
| } |
| |
| DBG_CHKTHIS(RegionBand, ImplDbgTestRegionBand); |
| } |
| |
| void RegionBand::Intersect(const RegionBand& rSource) |
| { |
| // mark all bands as untouched |
| ImplRegionBand* pBand = mpFirstBand; |
| |
| while ( pBand ) |
| { |
| pBand->mbTouched = false; |
| pBand = pBand->mpNextBand; |
| } |
| |
| pBand = rSource.mpFirstBand; |
| |
| while ( pBand ) |
| { |
| // insert bands if the boundaries are not allready in the list |
| InsertBands( pBand->mnYTop, pBand->mnYBottom ); |
| |
| // process all elements of the list |
| ImplRegionBandSep* pSep = pBand->mpFirstSep; |
| |
| while ( pSep ) |
| { |
| // left boundary? |
| if ( pSep == pBand->mpFirstSep ) |
| { |
| // process intersection and do not remove untouched bands |
| Exclude( LONG_MIN+1, pBand->mnYTop, pSep->mnXLeft-1, pBand->mnYBottom ); |
| } |
| |
| // right boundary? |
| if ( pSep->mpNextSep == NULL ) |
| { |
| // process intersection and do not remove untouched bands |
| Exclude( pSep->mnXRight+1, pBand->mnYTop, LONG_MAX-1, pBand->mnYBottom ); |
| } |
| else |
| { |
| // process intersection and do not remove untouched bands |
| Exclude( pSep->mnXRight+1, pBand->mnYTop, pSep->mpNextSep->mnXLeft-1, pBand->mnYBottom ); |
| } |
| |
| pSep = pSep->mpNextSep; |
| } |
| |
| pBand = pBand->mpNextBand; |
| } |
| |
| // remove all untouched bands if bands allready left |
| ImplRegionBand* pPrevBand = 0; |
| pBand = mpFirstBand; |
| |
| while ( pBand ) |
| { |
| if ( !pBand->mbTouched ) |
| { |
| // save pointer |
| ImplRegionBand* pOldBand = pBand; |
| |
| // previous element of the list |
| if ( pBand == mpFirstBand ) |
| { |
| mpFirstBand = pBand->mpNextBand; |
| } |
| else |
| { |
| pPrevBand->mpNextBand = pBand->mpNextBand; |
| } |
| |
| pBand = pBand->mpNextBand; |
| delete pOldBand; |
| } |
| else |
| { |
| pPrevBand = pBand; |
| pBand = pBand->mpNextBand; |
| } |
| } |
| |
| DBG_CHKTHIS(RegionBand, ImplDbgTestRegionBand); |
| } |
| |
| bool RegionBand::Exclude(const RegionBand& rSource) |
| { |
| // Alle Rechtecke aus der uebergebenen Region auf diese Region anwenden |
| ImplRegionBand* pBand = rSource.mpFirstBand; |
| |
| while ( pBand ) |
| { |
| // insert bands if the boundaries are not allready in the list |
| InsertBands( pBand->mnYTop, pBand->mnYBottom ); |
| |
| // process all elements of the list |
| ImplRegionBandSep* pSep = pBand->mpFirstSep; |
| |
| while ( pSep ) |
| { |
| Exclude( pSep->mnXLeft, pBand->mnYTop, pSep->mnXRight, pBand->mnYBottom ); |
| pSep = pSep->mpNextSep; |
| } |
| |
| // to test less bands, already check in the loop |
| if ( !OptimizeBandList() ) |
| { |
| DBG_CHKTHIS(RegionBand, ImplDbgTestRegionBand); |
| return false; |
| } |
| |
| pBand = pBand->mpNextBand; |
| } |
| |
| DBG_CHKTHIS(RegionBand, ImplDbgTestRegionBand); |
| return true; |
| } |
| |
| Rectangle RegionBand::GetBoundRect() const |
| { |
| DBG_CHKTHIS(RegionBand, ImplDbgTestRegionBand); |
| |
| // get the boundaries of the first band |
| long nYTop(mpFirstBand->mnYTop); |
| long nYBottom(mpFirstBand->mnYBottom); |
| long nXLeft(mpFirstBand->GetXLeftBoundary()); |
| long nXRight(mpFirstBand->GetXRightBoundary()); |
| |
| // look in the band list (don't test first band again!) |
| ImplRegionBand* pBand = mpFirstBand->mpNextBand; |
| |
| while ( pBand ) |
| { |
| nYBottom = pBand->mnYBottom; |
| nXLeft = std::min( nXLeft, pBand->GetXLeftBoundary() ); |
| nXRight = std::max( nXRight, pBand->GetXRightBoundary() ); |
| |
| pBand = pBand->mpNextBand; |
| } |
| |
| return Rectangle( nXLeft, nYTop, nXRight, nYBottom ); |
| } |
| |
| void RegionBand::XOr(const RegionBand& rSource) |
| { |
| ImplRegionBand* pBand = rSource.mpFirstBand; |
| |
| while ( pBand ) |
| { |
| // insert bands if the boundaries are not allready in the list |
| InsertBands( pBand->mnYTop, pBand->mnYBottom ); |
| |
| // process all elements of the list |
| ImplRegionBandSep* pSep = pBand->mpFirstSep; |
| |
| while ( pSep ) |
| { |
| XOr( pSep->mnXLeft, pBand->mnYTop, pSep->mnXRight, pBand->mnYBottom ); |
| pSep = pSep->mpNextSep; |
| } |
| |
| pBand = pBand->mpNextBand; |
| } |
| } |
| |
| bool RegionBand::IsInside(const Point& rPoint) const |
| { |
| DBG_CHKTHIS(RegionBand, ImplDbgTestRegionBand); |
| |
| // search band list |
| ImplRegionBand* pBand = mpFirstBand; |
| |
| while(pBand) |
| { |
| // is point within band? |
| if((pBand->mnYTop <= rPoint.Y()) && (pBand->mnYBottom >= rPoint.Y())) |
| { |
| // is point within separation of the band? |
| DBG_CHKTHIS(RegionBand, ImplDbgTestRegionBand); |
| if(pBand->IsInside(rPoint.X())) |
| { |
| return true; |
| } |
| else |
| { |
| return false; |
| } |
| } |
| |
| pBand = pBand->mpNextBand; |
| } |
| |
| return false; |
| } |
| |
| void RegionBand::GetRegionRectangles(RectangleVector& rTarget) const |
| { |
| // clear result vector |
| rTarget.clear(); |
| ImplRegionBand* mpCurrRectBand = mpFirstBand; |
| Rectangle aRectangle; |
| |
| while(mpCurrRectBand) |
| { |
| ImplRegionBandSep* mpCurrRectBandSep = mpCurrRectBand->mpFirstSep; |
| |
| aRectangle.Top() = mpCurrRectBand->mnYTop; |
| aRectangle.Bottom() = mpCurrRectBand->mnYBottom; |
| |
| while(mpCurrRectBandSep) |
| { |
| aRectangle.Left() = mpCurrRectBandSep->mnXLeft; |
| aRectangle.Right() = mpCurrRectBandSep->mnXRight; |
| rTarget.push_back(aRectangle); |
| mpCurrRectBandSep = mpCurrRectBandSep->mpNextSep; |
| } |
| |
| mpCurrRectBand = mpCurrRectBand->mpNextBand; |
| } |
| } |
| |
| sal_uInt32 RegionBand::getRectangleCount() const |
| { |
| sal_uInt32 nCount = 0; |
| const ImplRegionBand* pBand = mpFirstBand; |
| |
| while(pBand) |
| { |
| ImplRegionBandSep* pSep = pBand->mpFirstSep; |
| |
| while(pSep) |
| { |
| nCount++; |
| pSep = pSep->mpNextSep; |
| } |
| |
| pBand = pBand->mpNextBand; |
| } |
| |
| return 0; |
| } |
| |
| #ifdef DBG_UTIL |
| const char* ImplDbgTestRegionBand(const void* pObj) |
| { |
| const RegionBand* pRegionBand = reinterpret_cast< const RegionBand* >(pObj); |
| |
| if(pRegionBand) |
| { |
| const ImplRegionBand* pBand = pRegionBand->ImplGetFirstRegionBand(); |
| |
| while(pBand) |
| { |
| if(pBand->mnYBottom < pBand->mnYTop) |
| { |
| return "YBottom < YTop"; |
| } |
| |
| if(pBand->mpNextBand) |
| { |
| if(pBand->mnYBottom >= pBand->mpNextBand->mnYTop) |
| { |
| return "overlapping bands in region"; |
| } |
| } |
| |
| if(pBand->mbTouched) |
| { |
| return "Band-mbTouched overwrite"; |
| } |
| |
| ImplRegionBandSep* pSep = pBand->mpFirstSep; |
| |
| while(pSep) |
| { |
| if(pSep->mnXRight < pSep->mnXLeft) |
| { |
| return "XLeft < XRight"; |
| } |
| |
| if(pSep->mpNextSep) |
| { |
| if(pSep->mnXRight >= pSep->mpNextSep->mnXLeft) |
| { |
| return "overlapping separations in region"; |
| } |
| } |
| |
| if ( pSep->mbRemoved ) |
| { |
| return "Sep-mbRemoved overwrite"; |
| } |
| |
| pSep = pSep->mpNextSep; |
| } |
| |
| pBand = pBand->mpNextBand; |
| } |
| } |
| |
| return 0; |
| } |
| #endif |
| |
| ////////////////////////////////////////////////////////////////////////////// |
| // eof |