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