vcl/source/gdi/polyscan.cxx

   1 /*************************************************************************
   2  *
   3  * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
   4  *
   5  * Copyright 2008 by Sun Microsystems, Inc.
   6  *
   7  * OpenOffice.org - a multi-platform office productivity suite
   8  *
   9  * $RCSfile: polyscan.cxx,v $
  10  * $Revision: 1.6 $
  11  *
  12  * This file is part of OpenOffice.org.
  13  *
  14  * OpenOffice.org is free software: you can redistribute it and/or modify
  15  * it under the terms of the GNU Lesser General Public License version 3
  16  * only, as published by the Free Software Foundation.
  17  *
  18  * OpenOffice.org is distributed in the hope that it will be useful,
  19  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  20  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  21  * GNU Lesser General Public License version 3 for more details
  22  * (a copy is included in the LICENSE file that accompanied this code).
  23  *
  24  * You should have received a copy of the GNU Lesser General Public License
  25  * version 3 along with OpenOffice.org.  If not, see
  26  * <http://www.openoffice.org/license.html>
  27  * for a copy of the LGPLv3 License.
  28  *
  29  ************************************************************************/
  30
  31 // MARKER(update_precomp.py): autogen include statement, do not remove
  32 #include "precompiled_vcl.hxx"
  33
  34 #include <string.h>
  35 #include <tools/new.hxx>
  36 #include <vcl/salbtype.hxx>
  37 #include "polyscan.hxx"
  38 #include <tools/poly.hxx>
  39
  40 // ----------------
  41 // - PolyScanline -
  42 // ----------------
  43
  44 PolyScanline::PolyScanline() :
  45         mpFirst ( NULL ),
  46         mpLast  ( NULL ),
  47         mpAct   ( NULL ),
  48         mnLeft  ( 0L ),
  49         mnRight ( 0L )
  50 {
  51 }
  52
  53 // ------------------------------------------------------------------------
  54
  55 PolyScanline::~PolyScanline()
  56 {
  57     ImplDelete();
  58 }
  59
  60 // ------------------------------------------------------------------------
  61
  62 void PolyScanline::ImplDelete()
  63 {
  64     ScanlinePoint* pAct = mpFirst;
  65
  66     while( pAct )
  67     {
  68         ScanlinePoint* pNext = pAct->mpNext;
  69         delete pAct;
  70         pAct = pNext;
  71     }
  72
  73     mnLeft = mnRight = 0L;
  74     mpFirst = mpAct = mpLast = NULL;
  75 }
  76
  77 // ------------------------------------------------------------------------
  78
  79 void PolyScanline::Insert( long nX )
  80 {
  81     // first point to insert?
  82     if( !mpFirst )
  83         mpLast = mpFirst = new ScanlinePoint( mnLeft = mnRight = nX, NULL );
  84     else
  85     {
  86         // insert at the beginning of the scanline
  87         if( nX <= mpFirst->mnX )
  88             mpFirst = new ScanlinePoint( mnLeft = nX, mpFirst );
  89         else if( nX >= mnRight )
  90             mpLast = mpLast->mpNext = new ScanlinePoint( mnRight = nX, NULL );
  91         else
  92         {
  93             ScanlinePoint* pLast = mpFirst;
  94             ScanlinePoint* pAct = mpFirst->mpNext;
  95
  96             while( pAct )
  97             {
  98                 // insert in the midlle of the scanline?
  99                 if( nX <= pAct->mnX )
 100                 {
 101                     pLast->mpNext = new ScanlinePoint( nX, pAct );
 102                     break;
 103                 }
 104
 105                 pLast = pAct;
 106                 pAct = pAct->mpNext;
 107             }
 108         }
 109     }
 110 }
 111
 112 // ------------------------------------------------------------------------
 113
 114 void PolyScanline::Set( long nStart, long nEnd )
 115 {
 116     if( mpFirst )
 117         ImplDelete();
 118
 119     if( nStart <= nEnd )
 120         mpFirst = new ScanlinePoint( mnLeft = nStart, mpLast = new ScanlinePoint( mnRight = nEnd, NULL ) );
 121     else
 122         mpFirst = new ScanlinePoint( mnLeft = nEnd, mpLast = new ScanlinePoint( mnRight = nStart, NULL ) );
 123 }
 124
 125 // ------------------------------------------------------------------------
 126
 127 BOOL PolyScanline::GetFirstSegment( PolyScanSegment& rSegment )
 128 {
 129     BOOL bRet = GetFirstX( rSegment.mnStart );
 130
 131     if( bRet && !GetNextX( rSegment.mnEnd ) )
 132         rSegment.mnEnd = rSegment.mnStart;
 133
 134     return bRet;
 135 }
 136
 137 // ------------------------------------------------------------------------
 138
 139 BOOL PolyScanline::GetNextSegment( PolyScanSegment& rSegment )
 140 {
 141     BOOL bRet = GetNextX( rSegment.mnStart );
 142
 143     if( bRet && !GetNextX( rSegment.mnEnd ) )
 144         rSegment.mnEnd = rSegment.mnStart;
 145
 146     return bRet;
 147 }
 148
 149 // ---------------
 150 // - PolyScanner -
 151 // ---------------
 152
 153 PolyScanner::PolyScanner( const Rectangle& rRect )
 154 {
 155     if( !rRect.IsEmpty() )
 156     {
 157         Rectangle       aRect( rRect );
 158         ULONG           nHeight;
 159
 160         aRect.Justify();
 161         mnLeft = aRect.Left();
 162         mnTop = aRect.Top();
 163         mnRight = aRect.Right();
 164         mnBottom = aRect.Bottom();
 165         mpArray = new PolyScanline[ nHeight = Height() ];
 166
 167         for( ULONG i = 0UL; i < nHeight; i++ )
 168             mpArray[ i ].Set( mnLeft, mnRight );
 169     }
 170     else
 171     {
 172         mnLeft = mnTop = mnRight = mnBottom = 0L;
 173         mpArray = NULL;
 174     }
 175 }
 176
 177 // ------------------------------------------------------------------------
 178
 179 PolyScanner::PolyScanner( const Polygon& rPoly )
 180 {
 181     const long nCount = rPoly.GetSize();
 182
 183     if( nCount )
 184     {
 185         long    nLast = nCount - 1;
 186         Point   aFirst( rPoly[ 0 ] );
 187         Point   aLast( rPoly[ (USHORT) nLast ] );
 188
 189         while( nLast && ( aLast == aFirst ) )
 190             aLast = rPoly[ (USHORT) --nLast ];
 191
 192         if( !nLast )
 193         {
 194             aLast = rPoly[ 0 ];
 195             mnLeft = mnRight = aLast.X();
 196             mnTop = mnBottom = aLast.Y();
 197             mpArray = new PolyScanline[ 1UL ];
 198             mpArray[ 0 ].Set( mnLeft, mnRight );
 199         }
 200         else
 201         {
 202             const Rectangle aRect( rPoly.GetBoundRect() );
 203             ULONG                       nHeight;
 204
 205             mnLeft = aRect.Left();
 206             mnTop = aRect.Top();
 207             mnRight = aRect.Right();
 208             mnBottom = aRect.Bottom();
 209             aLast = aFirst;
 210             mpArray = new PolyScanline[ nHeight = Height() ];
 211
 212             for( long i = 1L; i <= nLast; i++ )
 213             {
 214                 const Point& rPt = rPoly[ (USHORT) i ];
 215
 216                 if( rPt != aLast )
 217                 {
 218                     InsertLine( aLast, rPt );
 219                     aLast = rPt;
 220                 }
 221             }
 222
 223             InsertLine( aLast, aFirst );
 224         }
 225     }
 226     else
 227         mpArray = NULL;
 228 }
 229
 230 // ------------------------------------------------------------------------
 231
 232 PolyScanner::PolyScanner( const PolyPolygon& rPolyPoly )
 233 {
 234     mpArray = NULL;
 235 }
 236
 237 // ------------------------------------------------------------------------
 238
 239 PolyScanner::~PolyScanner()
 240 {
 241     delete[] mpArray;
 242 }
 243
 244 // ------------------------------------------------------------------------
 245
 246 PolyScanline* PolyScanner::operator[]( ULONG nPos ) const
 247 {
 248     DBG_ASSERT( nPos < Count(), "nPos out of range!" );
 249     return( mpArray ? ( mpArray + nPos ) : NULL );
 250 }
 251
 252 // ------------------------------------------------------------------------
 253
 254 void PolyScanner::InsertLine( const Point& rStart, const Point& rEnd )
 255 {
 256     long nX, nY;
 257
 258     if( rStart.Y() == rEnd.Y() )
 259         mpArray[ rStart.Y() - mnTop ].Insert( rStart.X() );
 260     else if( rStart.X() == rEnd.X() )
 261     {
 262         // vertical line
 263         const long nEndY = rEnd.Y();
 264
 265         nX = rStart.X();
 266         nY = rStart.Y();
 267
 268         if( nEndY > nY )
 269             while( nY < nEndY )
 270                 mpArray[ nY++ - mnTop ].Insert( nX );
 271         else
 272             while( nY > nEndY )
 273                 mpArray[ nY-- - mnTop ].Insert( nX );
 274     }
 275     else
 276     {
 277         const long  nDX = labs( rEnd.X() - rStart.X() );
 278         const long  nDY = labs( rEnd.Y() - rStart.Y() );
 279         const long      nStartX = rStart.X();
 280         const long      nStartY = rStart.Y();
 281         const long      nEndX = rEnd.X();
 282         const long      nEndY = rEnd.Y();
 283         const long      nXInc = ( nStartX < nEndX ) ? 1L : -1L;
 284         const long      nYInc = ( nStartY < nEndY ) ? 1L : -1L;
 285         long            nLastX = nStartX;
 286         long            nLastY = nStartY;
 287         BOOL            bLast = FALSE;
 288
 289         mpArray[ nStartY - mnTop ].Insert( nStartX );
 290
 291         if( nDX >= nDY )
 292         {
 293             const long  nDYX = ( nDY - nDX ) << 1;
 294             const long  nDY2 = nDY << 1;
 295             long        nD = nDY2 - nDX;
 296
 297             for( nX = nStartX, nY = nLastY = nStartY; nX != nEndX; )
 298             {
 299                 if( nY != nLastY )
 300                 {
 301                     if( bLast )
 302                         mpArray[ nLastY - mnTop ].Insert( nLastX );
 303
 304                     mpArray[ nY - mnTop ].Insert( nX );
 305                     bLast = FALSE;
 306                 }
 307                 else
 308                     bLast = TRUE;
 309
 310                 nLastX = nX;
 311                 nLastY = nY;
 312
 313                 if( nD < 0L )
 314                     nD += nDY2;
 315                 else
 316                 {
 317                     nD += nDYX;
 318                     nY += nYInc;
 319                 }
 320
 321                 nX += nXInc;
 322             }
 323         }
 324         else
 325         {
 326             const long  nDYX = ( nDX - nDY ) << 1;
 327             const long  nDY2 = nDX << 1;
 328             long        nD = nDY2 - nDY;
 329
 330             for( nX = nStartX, nY = nStartY; nY != nEndY; )
 331             {
 332                 if( nY != nLastY )
 333                 {
 334                     if( bLast )
 335                         mpArray[ nLastY - mnTop ].Insert( nLastX );
 336
 337                     mpArray[ nY - mnTop ].Insert( nX );
 338                     bLast = FALSE;
 339                 }
 340                 else
 341                     bLast = TRUE;
 342
 343                 nLastX = nX;
 344                 nLastY = nY;
 345
 346                 if( nD < 0L )
 347                     nD += nDY2;
 348                 else
 349                 {
 350                     nD += nDYX;
 351                     nX += nXInc;
 352                 }
 353
 354                 nY += nYInc;
 355             }
 356         }
 357
 358         if( bLast )
 359             mpArray[ nLastY - mnTop ].Insert( nLastX );
 360     }
 361 }