1 /************************************************************************* 2 * 3 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. 4 * 5 * Copyright 2000, 2010 Oracle and/or its affiliates. 6 * 7 * OpenOffice.org - a multi-platform office productivity suite 8 * 9 * This file is part of OpenOffice.org. 10 * 11 * OpenOffice.org is free software: you can redistribute it and/or modify 12 * it under the terms of the GNU Lesser General Public License version 3 13 * only, as published by the Free Software Foundation. 14 * 15 * OpenOffice.org is distributed in the hope that it will be useful, 16 * but WITHOUT ANY WARRANTY; without even the implied warranty of 17 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 18 * GNU Lesser General Public License version 3 for more details 19 * (a copy is included in the LICENSE file that accompanied this code). 20 * 21 * You should have received a copy of the GNU Lesser General Public License 22 * version 3 along with OpenOffice.org. If not, see 23 * <http://www.openoffice.org/license.html> 24 * for a copy of the LGPLv3 License. 25 * 26 ************************************************************************/ 27 28 // MARKER(update_precomp.py): autogen include statement, do not remove 29 #include "precompiled_tools.hxx" 30 31 #define _LINE_CXX 32 #include <tools/link.hxx> 33 #include <tools/line.hxx> 34 #include <tools/debug.hxx> 35 36 #include <cstdlib> 37 #include <math.h> 38 39 // -------- 40 // - Line - 41 // -------- 42 43 double Line::GetLength() const 44 { 45 return hypot( maStart.X() - maEnd.X(), maStart.Y() - maEnd.Y() ); 46 } 47 48 // ------------------------------------------------------------------------ 49 50 sal_Bool Line::Intersection( const Line& rLine, Point& rIntersection ) const 51 { 52 double fX, fY; 53 sal_Bool bRet; 54 55 if( Intersection( rLine, fX, fY ) ) 56 { 57 rIntersection.X() = FRound( fX ); 58 rIntersection.Y() = FRound( fY ); 59 bRet = sal_True; 60 } 61 else 62 bRet = sal_False; 63 64 return bRet; 65 } 66 67 // ------------------------------------------------------------------------ 68 69 sal_Bool Line::Intersection( const Line& rLine, double& rIntersectionX, double& rIntersectionY ) const 70 { 71 const double fAx = maEnd.X() - maStart.X(); 72 const double fAy = maEnd.Y() - maStart.Y(); 73 const double fBx = rLine.maStart.X() - rLine.maEnd.X(); 74 const double fBy = rLine.maStart.Y() - rLine.maEnd.Y(); 75 const double fDen = fAy * fBx - fAx * fBy; 76 sal_Bool bOk = sal_False; 77 78 if( fDen != 0. ) 79 { 80 const double fCx = maStart.X() - rLine.maStart.X(); 81 const double fCy = maStart.Y() - rLine.maStart.Y(); 82 const double fA = fBy * fCx - fBx * fCy; 83 const sal_Bool bGreater = ( fDen > 0. ); 84 85 bOk = sal_True; 86 87 if ( bGreater ) 88 { 89 if ( ( fA < 0. ) || ( fA > fDen ) ) 90 bOk = sal_False; 91 } 92 else if ( ( fA > 0. ) || ( fA < fDen ) ) 93 bOk = sal_False; 94 95 if ( bOk ) 96 { 97 const double fB = fAx * fCy - fAy * fCx; 98 99 if ( bGreater ) 100 { 101 if ( ( fB < 0. ) || ( fB > fDen ) ) 102 bOk = sal_False; 103 } 104 else if ( ( fB > 0. ) || ( fB < fDen ) ) 105 bOk = sal_False; 106 107 if( bOk ) 108 { 109 const double fAlpha = fA / fDen; 110 111 rIntersectionX = ( maStart.X() + fAlpha * fAx ); 112 rIntersectionY = ( maStart.Y() + fAlpha * fAy ); 113 } 114 } 115 } 116 117 return bOk; 118 } 119 120 // ------------------------------------------------------------------------ 121 122 sal_Bool Line::Intersection( const Rectangle& rRect, Line& rIntersection ) const 123 { 124 const sal_Bool bStartInside = rRect.IsInside( maStart ); 125 const sal_Bool bEndInside = rRect.IsInside( maEnd ); 126 sal_Bool bRet = sal_True; 127 128 if( bStartInside && bEndInside ) 129 { 130 // line completely inside rect 131 rIntersection.maStart = maStart; 132 rIntersection.maEnd = maEnd; 133 } 134 else 135 { 136 // calculate intersections 137 const Point aTL( rRect.TopLeft() ), aTR( rRect.TopRight() ); 138 const Point aBR( rRect.BottomRight() ), aBL( rRect.BottomLeft() ); 139 Point aIntersect1, aIntersect2; 140 Point* pCurIntersection = &aIntersect1; 141 142 if( Intersection( Line( aTL, aTR ), *pCurIntersection ) ) 143 pCurIntersection = &aIntersect2; 144 145 if( Intersection( Line( aTR, aBR ), *pCurIntersection ) ) 146 pCurIntersection = ( pCurIntersection == &aIntersect1 ) ? &aIntersect2 : NULL; 147 148 if( pCurIntersection && Intersection( Line( aBR, aBL ), *pCurIntersection ) ) 149 pCurIntersection = ( pCurIntersection == &aIntersect1 ) ? &aIntersect2 : NULL; 150 151 if( pCurIntersection && Intersection( Line( aBL, aTL ), *pCurIntersection ) ) 152 pCurIntersection = ( pCurIntersection == &aIntersect1 ) ? &aIntersect2 : NULL; 153 154 if( !pCurIntersection ) 155 { 156 // two intersections 157 rIntersection.maStart = aIntersect1; 158 rIntersection.maEnd = aIntersect2; 159 } 160 else if( pCurIntersection == &aIntersect2 ) 161 { 162 // one intersection 163 rIntersection.maStart = aIntersect1; 164 165 if( ( maStart != aIntersect1 ) && bStartInside ) 166 rIntersection.maEnd = maStart; 167 else if( ( maEnd != aIntersect1 ) && bEndInside ) 168 rIntersection.maEnd = maEnd; 169 else 170 rIntersection.maEnd = rIntersection.maStart; 171 } 172 else 173 bRet = sal_False; 174 } 175 176 return bRet; 177 } 178 179 // ------------------------------------------------------------------------ 180 181 Point Line::NearestPoint( const Point& rPoint ) const 182 { 183 Point aRetPt; 184 185 if ( maStart != maEnd ) 186 { 187 const double fDistX = maEnd.X() - maStart.X(); 188 const double fDistY = maStart.Y() - maEnd.Y(); 189 const double fTau = ( ( maStart.Y() - rPoint.Y() ) * fDistY - 190 ( maStart.X() - rPoint.X() ) * fDistX ) / 191 ( fDistX * fDistX + fDistY * fDistY ); 192 193 if( fTau < 0.0 ) 194 aRetPt = maStart; 195 else if( fTau <= 1.0 ) 196 { 197 aRetPt.X() = FRound( maStart.X() + fTau * fDistX ); 198 aRetPt.Y() = FRound( maStart.Y() - fTau * fDistY ); 199 } 200 else 201 aRetPt = maEnd; 202 } 203 else 204 aRetPt = maStart; 205 206 return aRetPt; 207 } 208 209 // ------------------------------------------------------------------------ 210 211 double Line::GetDistance( const double& rPtX, const double& rPtY ) const 212 { 213 double fDist; 214 215 if( maStart != maEnd ) 216 { 217 const double fDistX = maEnd.X() - maStart.X(); 218 const double fDistY = maEnd.Y() - maStart.Y(); 219 const double fACX = maStart.X() - rPtX; 220 const double fACY = maStart.Y() - rPtY; 221 const double fL2 = fDistX * fDistX + fDistY * fDistY; 222 const double fR = ( fACY * -fDistY - fACX * fDistX ) / fL2; 223 const double fS = ( fACY * fDistX - fACX * fDistY ) / fL2; 224 225 if( fR < 0.0 ) 226 { 227 fDist = hypot( maStart.X() - rPtX, maStart.Y() - rPtY ); 228 229 if( fS < 0.0 ) 230 fDist *= -1.0; 231 } 232 else if( fR <= 1.0 ) 233 fDist = fS * sqrt( fL2 ); 234 else 235 { 236 fDist = hypot( maEnd.X() - rPtX, maEnd.Y() - rPtY ); 237 238 if( fS < 0.0 ) 239 fDist *= -1.0; 240 } 241 } 242 else 243 fDist = hypot( maStart.X() - rPtX, maStart.Y() - rPtY ); 244 245 return fDist; 246 } 247 248 // ------------------------------------------------------------------------ 249 250 void Line::Enum( const Link& rEnumLink ) 251 { 252 DBG_ASSERT( rEnumLink.IsSet(), "This call doesn't make any sense with !rEnumLink.IsSet()" ); 253 254 Point aEnum; 255 long nX; 256 long nY; 257 258 if( maStart.X() == maEnd.X() ) 259 { 260 const long nEndY = maEnd.Y(); 261 262 nX = maStart.X(); 263 nY = maStart.Y(); 264 265 if( nEndY > nY ) 266 { 267 while( nY <= nEndY ) 268 { 269 aEnum.X() = nX; 270 aEnum.Y() = nY++; 271 rEnumLink.Call( &aEnum ); 272 } 273 } 274 else 275 { 276 while( nY >= nEndY ) 277 { 278 aEnum.X() = nX; 279 aEnum.Y() = nY--; 280 rEnumLink.Call( &aEnum ); 281 } 282 } 283 } 284 else if( maStart.Y() == maEnd.Y() ) 285 { 286 const long nEndX = maEnd.X(); 287 288 nX = maStart.X(); 289 nY = maStart.Y(); 290 291 if( nEndX > nX ) 292 { 293 while( nX <= nEndX ) 294 { 295 aEnum.X() = nX++; 296 aEnum.Y() = nY; 297 rEnumLink.Call( &aEnum ); 298 } 299 } 300 else 301 { 302 while( nX >= nEndX ) 303 { 304 aEnum.X() = nX--; 305 aEnum.Y() = nY; 306 rEnumLink.Call( &aEnum ); 307 } 308 } 309 } 310 else 311 { 312 const long nDX = labs( maEnd.X() - maStart.X() ); 313 const long nDY = labs( maEnd.Y() - maStart.Y() ); 314 const long nStartX = maStart.X(); 315 const long nStartY = maStart.Y(); 316 const long nEndX = maEnd.X(); 317 const long nEndY = maEnd.Y(); 318 const long nXInc = ( nStartX < nEndX ) ? 1L : -1L; 319 const long nYInc = ( nStartY < nEndY ) ? 1L : -1L; 320 321 if( nDX >= nDY ) 322 { 323 const long nDYX = ( nDY - nDX ) << 1; 324 const long nDY2 = nDY << 1; 325 long nD = nDY2 - nDX; 326 327 for( nX = nStartX, nY = nStartY; nX != nEndX; nX += nXInc ) 328 { 329 aEnum.X() = nX; 330 aEnum.Y() = nY; 331 rEnumLink.Call( &aEnum ); 332 333 if( nD < 0L ) 334 nD += nDY2; 335 else 336 nD += nDYX, nY += nYInc; 337 } 338 } 339 else 340 { 341 const long nDYX = ( nDX - nDY ) << 1; 342 const long nDY2 = nDX << 1; 343 long nD = nDY2 - nDY; 344 345 for( nX = nStartX, nY = nStartY; nY != nEndY; nY += nYInc ) 346 { 347 aEnum.X() = nX; 348 aEnum.Y() = nY; 349 rEnumLink.Call( &aEnum ); 350 351 if( nD < 0L ) 352 nD += nDY2; 353 else 354 nD += nDYX, nX += nXInc; 355 } 356 } 357 358 // last point 359 aEnum.X() = nEndX; 360 aEnum.Y() = nEndY; 361 rEnumLink.Call( &aEnum ); 362 } 363 } 364