1 /**
2 * \file
3 * \brief Infinite Straight Line
4 *
5 * Copyright 2008 Marco Cecchetti <mrcekets at gmail.com>
6 *
7 * This library is free software; you can redistribute it and/or
8 * modify it either under the terms of the GNU Lesser General Public
9 * License version 2.1 as published by the Free Software Foundation
10 * (the "LGPL") or, at your option, under the terms of the Mozilla
11 * Public License Version 1.1 (the "MPL"). If you do not alter this
12 * notice, a recipient may use your version of this file under either
13 * the MPL or the LGPL.
14 *
15 * You should have received a copy of the LGPL along with this library
16 * in the file COPYING-LGPL-2.1; if not, write to the Free Software
17 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
18 * You should have received a copy of the MPL along with this library
19 * in the file COPYING-MPL-1.1
20 *
21 * The contents of this file are subject to the Mozilla Public License
22 * Version 1.1 (the "License"); you may not use this file except in
23 * compliance with the License. You may obtain a copy of the License at
24 * http://www.mozilla.org/MPL/
25 *
26 * This software is distributed on an "AS IS" basis, WITHOUT WARRANTY
27 * OF ANY KIND, either express or implied. See the LGPL or the MPL for
28 * the specific language governing rights and limitations.
29 */
31 #ifndef _2GEOM_LINE_H_
32 #define _2GEOM_LINE_H_
35 #include <cmath>
37 #include <2geom/bezier-curve.h> // for LineSegment
38 #include <2geom/crossing.h>
39 #include <2geom/exception.h>
41 #include <2geom/ray.h>
44 namespace Geom
45 {
47 class Line
48 {
49 public:
50 Line()
51 : m_origin(0,0), m_versor(1,0)
52 {
53 }
55 Line(Point const& _origin, Coord angle )
56 : m_origin(_origin), m_versor(std::cos(angle), std::sin(angle))
57 {
58 }
60 Line(Point const& A, Point const& B)
61 {
62 setBy2Points(A, B);
63 }
65 explicit
66 Line(LineSegment const& _segment)
67 {
68 setBy2Points(_segment.initialPoint(), _segment.finalPoint());
69 }
71 explicit
72 Line(Ray const& _ray)
73 : m_origin(_ray.origin()), m_versor(_ray.versor())
74 {
75 }
77 static Line fromNormalDistance(Point n, double c) {
78 Point P = n*c/(dot(n,n));
80 return Line(P, P+rot90(n));
81 }
83 Line* duplicate() const
84 {
85 return new Line(*this);
86 }
88 Point origin() const
89 {
90 return m_origin;
91 }
93 Point versor() const
94 {
95 return m_versor;
96 }
98 void origin(Point const& _point)
99 {
100 m_origin = _point;
101 }
103 void versor(Point const& _versor)
104 {
105 m_versor = _versor;
106 }
108 // return the angle described by rotating the X-axis in cw direction
109 // until it overlaps the line
110 // the returned value is in the interval [0, PI[
111 Coord angle() const
112 {
113 double a = std::atan2(m_versor[Y], m_versor[X]);
114 if (a < 0) a += M_PI;
115 if (a == M_PI) a = 0;
116 return a;
117 }
119 void angle(Coord _angle)
120 {
121 m_versor[X] = std::cos(_angle);
122 m_versor[Y] = std::sin(_angle);
123 }
125 void setBy2Points(Point const& A, Point const& B)
126 {
127 m_origin = A;
128 m_versor = B - A;
129 if ( are_near(m_versor, Point(0,0)) )
130 m_versor = Point(0,0);
131 else
132 m_versor.normalize();
133 }
135 bool isDegenerate() const
136 {
137 return ( m_versor[X] == 0 && m_versor[Y] == 0 );
138 }
140 Point pointAt(Coord t) const
141 {
142 return m_origin + m_versor * t;
143 }
145 Coord valueAt(Coord t, Dim2 d) const
146 {
147 if (d < 0 || d > 1)
148 THROW_RANGEERROR("Ray::valueAt, dimension argument out of range");
149 return m_origin[d] + m_versor[d] * t;
150 }
152 std::vector<Coord> roots(Coord v, Dim2 d) const
153 {
154 if (d < 0 || d > 1)
155 THROW_RANGEERROR("Ray::roots, dimension argument out of range");
156 std::vector<Coord> result;
157 if ( m_versor[d] != 0 )
158 {
159 result.push_back( (v - m_origin[d]) / m_versor[d] );
160 }
161 // TODO: else ?
162 return result;
163 }
165 // require are_near(_point, *this)
166 // on the contrary the result value is meaningless
167 Coord timeAt(Point const& _point) const
168 {
169 Coord t;
170 if ( m_versor[X] != 0 )
171 {
172 t = (_point[X] - m_origin[X]) / m_versor[X];
173 }
174 else if ( m_versor[Y] != 0 )
175 {
176 t = (_point[Y] - m_origin[Y]) / m_versor[Y];
177 }
178 else // degenerate case
179 {
180 t = 0;
181 }
182 return t;
183 }
185 Coord timeAtProjection(Point const& _point) const
186 {
187 if ( isDegenerate() ) return 0;
188 return dot( _point - m_origin, m_versor );
189 }
191 Coord nearestPoint(Point const& _point) const
192 {
193 return timeAtProjection(_point);
194 }
196 Line reverse() const
197 {
198 Line result;
199 result.origin(m_origin);
200 result.versor(-m_versor);
201 return result;
202 }
204 Curve* portion(Coord f, Coord t) const
205 {
206 LineSegment* seg = new LineSegment(pointAt(f), pointAt(t));
207 return seg;
208 }
210 LineSegment segment(Coord f, Coord t) const
211 {
212 return LineSegment(pointAt(f), pointAt(t));
213 }
215 Ray ray(Coord t)
216 {
217 Ray result;
218 result.origin(pointAt(t));
219 result.versor(m_versor);
220 return result;
221 }
223 Line derivative() const
224 {
225 Line result;
226 result.origin(m_versor);
227 result.versor(Point(0,0));
228 return result;
229 }
231 Line transformed(Matrix const& m) const
232 {
233 return Line(m_origin * m, (m_origin + m_versor) * m);
234 }
236 static Line from_normal_and_dist(Point const &n, double d) {
237 return Line(n*d, n*d + rot90(n));
238 }
240 private:
241 Point m_origin;
242 Point m_versor;
244 }; // end class Line
247 inline
248 double distance(Point const& _point, Line const& _line)
249 {
250 if ( _line.isDegenerate() )
251 {
252 return distance( _point, _line.origin() );
253 }
254 else
255 {
256 return fabs( dot(_point - _line.origin(), _line.versor().ccw()) );
257 }
258 }
260 inline
261 bool are_near(Point const& _point, Line const& _line, double eps = EPSILON)
262 {
263 return are_near(distance(_point, _line), 0, eps);
264 }
266 inline
267 bool are_parallel(Line const& l1, Line const& l2, double eps = EPSILON)
268 {
269 return ( are_near(l1.versor(), l2.versor(), eps)
270 || are_near(l1.versor(), -l2.versor(), eps) );
271 }
273 inline
274 bool are_same(Line const& l1, Line const& l2, double eps = EPSILON)
275 {
276 return are_parallel(l1, l2, eps) && are_near(l1.origin(), l2, eps);
277 }
279 inline
280 bool are_orthogonal(Line const& l1, Line const& l2, double eps = EPSILON)
281 {
282 return ( are_near(l1.versor(), l2.versor().cw(), eps)
283 || are_near(l1.versor(), l2.versor().ccw(), eps) );
284 }
286 inline
287 bool are_collinear(Point const& p1, Point const& p2, Point const& p3,
288 double eps = EPSILON)
289 {
290 return are_near( cross(p3, p2) - cross(p3, p1) + cross(p2, p1), 0, eps);
291 }
293 // evaluate the angle between l1 and l2 rotating l1 in cw direction
294 // until it overlaps l2
295 // the returned value is an angle in the interval [0, PI[
296 inline
297 double angle_between(Line const& l1, Line const& l2)
298 {
299 double angle = angle_between(l1.versor(), l2.versor());
300 if (angle < 0) angle += M_PI;
301 if (angle == M_PI) angle = 0;
302 return angle;
303 }
305 inline
306 double distance(Point const& _point, LineSegment const& _segment)
307 {
308 double t = _segment.nearestPoint(_point);
309 return L2(_point - _segment.pointAt(t));
310 }
312 inline
313 bool are_near(Point const& _point, LineSegment const& _segment,
314 double eps = EPSILON)
315 {
316 return are_near(distance(_point, _segment), 0, eps);
317 }
319 // build a line passing by _point and orthogonal to _line
320 inline
321 Line make_orthogonal_line(Point const& _point, Line const& _line)
322 {
323 Line l;
324 l.origin(_point);
325 l.versor(_line.versor().cw());
326 return l;
327 }
329 // build a line passing by _point and parallel to _line
330 inline
331 Line make_parallel_line(Point const& _point, Line const& _line)
332 {
333 Line l(_line);
334 l.origin(_point);
335 return l;
336 }
338 // build a line passing by the middle point of _segment and orthogonal to it.
339 inline
340 Line make_bisector_line(LineSegment const& _segment)
341 {
342 return make_orthogonal_line( middle_point(_segment), Line(_segment) );
343 }
345 // build the bisector line of the angle between ray(O,A) and ray(O,B)
346 inline
347 Line make_angle_bisector_line(Point const& A, Point const& O, Point const& B)
348 {
349 Point M = middle_point(A,B);
350 return Line(O,M);
351 }
353 // prj(P) = rot(v, Point( rot(-v, P-O)[X], 0 )) + O
354 inline
355 Point projection(Point const& _point, Line const& _line)
356 {
357 return _line.pointAt( _line.nearestPoint(_point) );
358 }
360 inline
361 LineSegment projection(LineSegment const& _segment, Line const& _line)
362 {
363 return _line.segment( _line.nearestPoint(_segment.initialPoint()),
364 _line.nearestPoint(_segment.finalPoint()) );
365 }
370 namespace detail
371 {
373 OptCrossing intersection_impl(Ray const& r1, Line const& l2, unsigned int i);
374 OptCrossing intersection_impl( LineSegment const& ls1,
375 Line const& l2,
376 unsigned int i );
377 OptCrossing intersection_impl( LineSegment const& ls1,
378 Ray const& r2,
379 unsigned int i );
380 }
383 inline
384 OptCrossing intersection(Ray const& r1, Line const& l2)
385 {
386 return detail::intersection_impl(r1, l2, 0);
388 }
390 inline
391 OptCrossing intersection(Line const& l1, Ray const& r2)
392 {
393 return detail::intersection_impl(r2, l1, 1);
394 }
396 inline
397 OptCrossing intersection(LineSegment const& ls1, Line const& l2)
398 {
399 return detail::intersection_impl(ls1, l2, 0);
400 }
402 inline
403 OptCrossing intersection(Line const& l1, LineSegment const& ls2)
404 {
405 return detail::intersection_impl(ls2, l1, 1);
406 }
408 inline
409 OptCrossing intersection(LineSegment const& ls1, Ray const& r2)
410 {
411 return detail::intersection_impl(ls1, r2, 0);
413 }
415 inline
416 OptCrossing intersection(Ray const& r1, LineSegment const& ls2)
417 {
418 return detail::intersection_impl(ls2, r1, 1);
419 }
422 OptCrossing intersection(Line const& l1, Line const& l2);
424 OptCrossing intersection(Ray const& r1, Ray const& r2);
426 OptCrossing intersection(LineSegment const& ls1, LineSegment const& ls2);
429 } // end namespace Geom
432 #endif // _2GEOM_LINE_H_
435 /*
436 Local Variables:
437 mode:c++
438 c-file-style:"stroustrup"
439 c-file-offsets:((innamespace . 0)(substatement-open . 0))
440 indent-tabs-mode:nil
441 c-brace-offset:0
442 fill-column:99
443 End:
444 vim: filetype=cpp:expandtab:shiftwidth=4:tabstop=8:softtabstop=4 :
445 */