tools/source/generic/line.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: line.cxx,v $
  10  * $Revision: 1.10 $
  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_tools.hxx"
  33
  34 #define _LINE_CXX
  35 #include <tools/link.hxx>
  36 #include <tools/line.hxx>
  37 #include <tools/debug.hxx>
  38
  39 #include <cstdlib>
  40 #include <math.h>
  41
  42 inline long FRound( double fVal )
  43 {
  44     return( fVal > 0.0 ? (long) ( fVal + 0.5 ) : -(long) ( -fVal + 0.5 ) );
  45 }
  46
  47 // --------
  48 // - Line -
  49 // --------
  50
  51 double Line::GetLength() const
  52 {
  53     return hypot( maStart.X() - maEnd.X(), maStart.Y() - maEnd.Y() );
  54 }
  55
  56 // ------------------------------------------------------------------------
  57
  58 BOOL Line::Intersection( const Line& rLine, Point& rIntersection ) const
  59 {
  60     double      fX, fY;
  61     BOOL        bRet;
  62
  63     if( Intersection( rLine, fX, fY ) )
  64     {
  65         rIntersection.X() = FRound( fX );
  66         rIntersection.Y() = FRound( fY );
  67         bRet = TRUE;
  68     }
  69     else
  70         bRet = FALSE;
  71
  72     return bRet;
  73 }
  74
  75 // ------------------------------------------------------------------------
  76
  77 BOOL Line::Intersection( const Line& rLine, double& rIntersectionX, double& rIntersectionY ) const
  78 {
  79     const double    fAx = maEnd.X() - maStart.X();
  80     const double    fAy = maEnd.Y() - maStart.Y();
  81     const double    fBx = rLine.maStart.X() - rLine.maEnd.X();
  82     const double    fBy = rLine.maStart.Y() - rLine.maEnd.Y();
  83     const double    fDen = fAy * fBx - fAx * fBy;
  84     BOOL            bOk = FALSE;
  85
  86     if( fDen != 0. )
  87     {
  88         const double    fCx = maStart.X() - rLine.maStart.X();
  89         const double    fCy = maStart.Y() - rLine.maStart.Y();
  90         const double    fA = fBy * fCx - fBx * fCy;
  91         const BOOL      bGreater = ( fDen > 0. );
  92
  93         bOk = TRUE;
  94
  95         if ( bGreater )
  96         {
  97             if ( ( fA < 0. ) || ( fA > fDen ) )
  98                 bOk = FALSE;
  99         }
 100         else if ( ( fA > 0. ) || ( fA < fDen ) )
 101             bOk = FALSE;
 102
 103         if ( bOk )
 104         {
 105             const double fB = fAx * fCy - fAy * fCx;
 106
 107             if ( bGreater )
 108             {
 109                 if ( ( fB < 0. ) || ( fB > fDen ) )
 110                     bOk = FALSE;
 111             }
 112             else if ( ( fB > 0. ) || ( fB < fDen ) )
 113                 bOk = FALSE;
 114
 115             if( bOk )
 116             {
 117                 const double fAlpha = fA / fDen;
 118
 119                 rIntersectionX = ( maStart.X() + fAlpha * fAx );
 120                 rIntersectionY = ( maStart.Y() + fAlpha * fAy );
 121             }
 122         }
 123     }
 124
 125     return bOk;
 126 }
 127
 128 // ------------------------------------------------------------------------
 129
 130 BOOL Line::Intersection( const Rectangle& rRect, Line& rIntersection ) const
 131 {
 132     const BOOL  bStartInside = rRect.IsInside( maStart );
 133     const BOOL  bEndInside = rRect.IsInside( maEnd );
 134     BOOL        bRet = TRUE;
 135
 136     if( bStartInside && bEndInside )
 137     {
 138         // line completely inside rect
 139         rIntersection.maStart = maStart;
 140         rIntersection.maEnd = maEnd;
 141     }
 142     else
 143     {
 144         // calculate intersections
 145         const Point aTL( rRect.TopLeft() ), aTR( rRect.TopRight() );
 146         const Point aBR( rRect.BottomRight() ), aBL( rRect.BottomLeft() );
 147         Point       aIntersect1, aIntersect2;
 148         Point*      pCurIntersection = &aIntersect1;
 149
 150         if( Intersection( Line( aTL, aTR ), *pCurIntersection ) )
 151             pCurIntersection = &aIntersect2;
 152
 153         if( Intersection( Line( aTR, aBR ), *pCurIntersection ) )
 154             pCurIntersection = ( pCurIntersection == &aIntersect1 ) ? &aIntersect2 : NULL;
 155
 156         if( pCurIntersection && Intersection( Line( aBR, aBL ), *pCurIntersection ) )
 157             pCurIntersection = ( pCurIntersection == &aIntersect1 ) ? &aIntersect2 : NULL;
 158
 159         if( pCurIntersection && Intersection( Line( aBL, aTL ), *pCurIntersection ) )
 160             pCurIntersection = ( pCurIntersection == &aIntersect1 ) ? &aIntersect2 : NULL;
 161
 162         if( !pCurIntersection )
 163         {
 164             // two intersections
 165             rIntersection.maStart = aIntersect1;
 166             rIntersection.maEnd = aIntersect2;
 167         }
 168         else if( pCurIntersection == &aIntersect2 )
 169         {
 170             // one intersection
 171             rIntersection.maStart = aIntersect1;
 172
 173             if( ( maStart != aIntersect1 ) && bStartInside )
 174                 rIntersection.maEnd = maStart;
 175             else if( ( maEnd != aIntersect1 ) && bEndInside )
 176                 rIntersection.maEnd = maEnd;
 177             else
 178                 rIntersection.maEnd = rIntersection.maStart;
 179         }
 180         else
 181             bRet = FALSE;
 182     }
 183
 184     return bRet;
 185 }
 186
 187 // ------------------------------------------------------------------------
 188
 189 Point Line::NearestPoint( const Point& rPoint ) const
 190 {
 191     Point aRetPt;
 192
 193     if ( maStart != maEnd )
 194     {
 195         const double    fDistX = maEnd.X() - maStart.X();
 196         const double    fDistY = maStart.Y() - maEnd.Y();
 197         const double    fTau = ( ( maStart.Y() - rPoint.Y() ) * fDistY -
 198                                  ( maStart.X() - rPoint.X() ) * fDistX ) /
 199                                ( fDistX * fDistX + fDistY * fDistY );
 200
 201         if( fTau < 0.0 )
 202             aRetPt = maStart;
 203         else if( fTau <= 1.0 )
 204         {
 205             aRetPt.X() = FRound( maStart.X() + fTau * fDistX );
 206             aRetPt.Y() = FRound( maStart.Y() - fTau * fDistY );
 207         }
 208         else
 209             aRetPt = maEnd;
 210     }
 211     else
 212         aRetPt = maStart;
 213
 214     return aRetPt;
 215 }
 216
 217 // ------------------------------------------------------------------------
 218
 219 double Line::GetDistance( const double& rPtX, const double& rPtY ) const
 220 {
 221     double fDist;
 222
 223     if( maStart != maEnd )
 224     {
 225         const double    fDistX = maEnd.X() - maStart.X();
 226         const double    fDistY = maEnd.Y() - maStart.Y();
 227         const double    fACX = maStart.X() - rPtX;
 228         const double    fACY = maStart.Y() - rPtY;
 229         const double    fL2 = fDistX * fDistX + fDistY * fDistY;
 230         const double    fR = ( fACY * -fDistY - fACX * fDistX ) / fL2;
 231         const double    fS = ( fACY * fDistX - fACX * fDistY ) / fL2;
 232
 233         if( fR < 0.0 )
 234         {
 235             fDist = hypot( maStart.X() - rPtX, maStart.Y() - rPtY );
 236
 237             if( fS < 0.0 )
 238                 fDist *= -1.0;
 239         }
 240         else if( fR <= 1.0 )
 241             fDist = fS * sqrt( fL2 );
 242         else
 243         {
 244             fDist = hypot( maEnd.X() - rPtX, maEnd.Y() - rPtY );
 245
 246             if( fS < 0.0 )
 247                 fDist *= -1.0;
 248         }
 249     }
 250     else
 251         fDist = hypot( maStart.X() - rPtX, maStart.Y() - rPtY );
 252
 253     return fDist;
 254 }
 255
 256 // ------------------------------------------------------------------------
 257
 258 void Line::Enum( const Link& rEnumLink )
 259 {
 260     DBG_ASSERT( rEnumLink.IsSet(), "This call doesn't make any sense with !rEnumLink.IsSet()" );
 261
 262     Point   aEnum;
 263     long    nX;
 264     long    nY;
 265
 266     if( maStart.X() == maEnd.X() )
 267     {
 268         const long nEndY = maEnd.Y();
 269
 270         nX = maStart.X();
 271         nY = maStart.Y();
 272
 273         if( nEndY > nY )
 274         {
 275             while( nY <= nEndY )
 276             {
 277                 aEnum.X() = nX;
 278                 aEnum.Y() = nY++;
 279                 rEnumLink.Call( &aEnum );
 280             }
 281         }
 282         else
 283         {
 284             while( nY >= nEndY )
 285             {
 286                 aEnum.X() = nX;
 287                 aEnum.Y() = nY--;
 288                 rEnumLink.Call( &aEnum );
 289             }
 290         }
 291     }
 292     else if( maStart.Y() == maEnd.Y() )
 293     {
 294         const long nEndX = maEnd.X();
 295
 296         nX = maStart.X();
 297         nY = maStart.Y();
 298
 299         if( nEndX > nX )
 300         {
 301             while( nX <= nEndX )
 302             {
 303                 aEnum.X() = nX++;
 304                 aEnum.Y() = nY;
 305                 rEnumLink.Call( &aEnum );
 306             }
 307         }
 308         else
 309         {
 310             while( nX >= nEndX )
 311             {
 312                 aEnum.X() = nX--;
 313                 aEnum.Y() = nY;
 314                 rEnumLink.Call( &aEnum );
 315             }
 316         }
 317     }
 318     else
 319     {
 320         const long  nDX = labs( maEnd.X() - maStart.X() );
 321         const long  nDY = labs( maEnd.Y() - maStart.Y() );
 322         const long      nStartX = maStart.X();
 323         const long      nStartY = maStart.Y();
 324         const long      nEndX = maEnd.X();
 325         const long      nEndY = maEnd.Y();
 326         const long      nXInc = ( nStartX < nEndX ) ? 1L : -1L;
 327         const long      nYInc = ( nStartY < nEndY ) ? 1L : -1L;
 328
 329         if( nDX >= nDY )
 330         {
 331             const long  nDYX = ( nDY - nDX ) << 1;
 332             const long  nDY2 = nDY << 1;
 333             long        nD = nDY2 - nDX;
 334
 335             for( nX = nStartX, nY = nStartY; nX != nEndX; nX += nXInc )
 336             {
 337                 aEnum.X() = nX;
 338                 aEnum.Y() = nY;
 339                 rEnumLink.Call( &aEnum );
 340
 341                 if( nD < 0L )
 342                     nD += nDY2;
 343                 else
 344                     nD += nDYX, nY += nYInc;
 345             }
 346         }
 347         else
 348         {
 349             const long  nDYX = ( nDX - nDY ) << 1;
 350             const long  nDY2 = nDX << 1;
 351             long        nD = nDY2 - nDY;
 352
 353             for( nX = nStartX, nY = nStartY; nY != nEndY; nY += nYInc )
 354             {
 355                 aEnum.X() = nX;
 356                 aEnum.Y() = nY;
 357                 rEnumLink.Call( &aEnum );
 358
 359                 if( nD < 0L )
 360                     nD += nDY2;
 361                 else
 362                     nD += nDYX, nX += nXInc;
 363             }
 364         }
 365
 366         // last point
 367         aEnum.X() = nEndX;
 368         aEnum.Y() = nEndY;
 369         rEnumLink.Call( &aEnum );
 370     }
 371 }