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
GetLength() const39 double Line::GetLength() const
40 {
41 return hypot( maStart.X() - maEnd.X(), maStart.Y() - maEnd.Y() );
42 }
43
44 // ------------------------------------------------------------------------
45
Intersection(const Line & rLine,Point & rIntersection) const46 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
Intersection(const Line & rLine,double & rIntersectionX,double & rIntersectionY) const65 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
Intersection(const Rectangle & rRect,Line & rIntersection) const118 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
NearestPoint(const Point & rPoint) const177 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
GetDistance(const double & rPtX,const double & rPtY) const207 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
Enum(const Link & rEnumLink)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