xref: /aoo42x/main/tools/source/generic/line.cxx (revision cdf0e10c)
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