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 }
82 static Line fromPointDirection(Point o, Point v) {
83 Line l;
84 l.m_origin = o;
85 l.m_versor = v;
86 return l;
87 }
89 Line* duplicate() const
90 {
91 return new Line(*this);
92 }
94 Point origin() const
95 {
96 return m_origin;
97 }
99 Point versor() const
100 {
101 return m_versor;
102 }
104 void origin(Point const& _point)
105 {
106 m_origin = _point;
107 }
109 void versor(Point const& _versor)
110 {
111 m_versor = _versor;
112 }
114 // return the angle described by rotating the X-axis in cw direction
115 // until it overlaps the line
116 // the returned value is in the interval [0, PI[
117 Coord angle() const
118 {
119 double a = std::atan2(m_versor[Y], m_versor[X]);
120 if (a < 0) a += M_PI;
121 if (a == M_PI) a = 0;
122 return a;
123 }
125 void angle(Coord _angle)
126 {
127 m_versor[X] = std::cos(_angle);
128 m_versor[Y] = std::sin(_angle);
129 }
131 void setBy2Points(Point const& A, Point const& B)
132 {
133 m_origin = A;
134 m_versor = B - A;
135 if ( are_near(m_versor, Point(0,0)) )
136 m_versor = Point(0,0);
137 else
138 m_versor.normalize();
139 }
141 bool isDegenerate() const
142 {
143 return ( m_versor[X] == 0 && m_versor[Y] == 0 );
144 }
146 Point pointAt(Coord t) const
147 {
148 return m_origin + m_versor * t;
149 }
151 Coord valueAt(Coord t, Dim2 d) const
152 {
153 if (d < 0 || d > 1)
154 THROW_RANGEERROR("Ray::valueAt, dimension argument out of range");
155 return m_origin[d] + m_versor[d] * t;
156 }
158 std::vector<Coord> roots(Coord v, Dim2 d) const
159 {
160 if (d < 0 || d > 1)
161 THROW_RANGEERROR("Ray::roots, dimension argument out of range");
162 std::vector<Coord> result;
163 if ( m_versor[d] != 0 )
164 {
165 result.push_back( (v - m_origin[d]) / m_versor[d] );
166 }
167 // TODO: else ?
168 return result;
169 }
171 // require are_near(_point, *this)
172 // on the contrary the result value is meaningless
173 Coord timeAt(Point const& _point) const
174 {
175 Coord t;
176 if ( m_versor[X] != 0 )
177 {
178 t = (_point[X] - m_origin[X]) / m_versor[X];
179 }
180 else if ( m_versor[Y] != 0 )
181 {
182 t = (_point[Y] - m_origin[Y]) / m_versor[Y];
183 }
184 else // degenerate case
185 {
186 t = 0;
187 }
188 return t;
189 }
191 Coord timeAtProjection(Point const& _point) const
192 {
193 if ( isDegenerate() ) return 0;
194 return dot( _point - m_origin, m_versor );
195 }
197 Coord nearestPoint(Point const& _point) const
198 {
199 return timeAtProjection(_point);
200 }
202 Line reverse() const
203 {
204 Line result;
205 result.origin(m_origin);
206 result.versor(-m_versor);
207 return result;
208 }
210 Curve* portion(Coord f, Coord t) const
211 {
212 LineSegment* seg = new LineSegment(pointAt(f), pointAt(t));
213 return seg;
214 }
216 LineSegment segment(Coord f, Coord t) const
217 {
218 return LineSegment(pointAt(f), pointAt(t));
219 }
221 Ray ray(Coord t)
222 {
223 Ray result;
224 result.origin(pointAt(t));
225 result.versor(m_versor);
226 return result;
227 }
229 Line derivative() const
230 {
231 Line result;
232 result.origin(m_versor);
233 result.versor(Point(0,0));
234 return result;
235 }
237 Line transformed(Matrix const& m) const
238 {
239 return Line(m_origin * m, (m_origin + m_versor) * m);
240 }
242 static Line from_normal_and_dist(Point const &n, double d) {
243 return Line(n*d, n*d + rot90(n));
244 }
246 private:
247 Point m_origin;
248 Point m_versor;
250 }; // end class Line
253 inline
254 double distance(Point const& _point, Line const& _line)
255 {
256 if ( _line.isDegenerate() )
257 {
258 return distance( _point, _line.origin() );
259 }
260 else
261 {
262 return fabs( dot(_point - _line.origin(), _line.versor().ccw()) );
263 }
264 }
266 inline
267 bool are_near(Point const& _point, Line const& _line, double eps = EPSILON)
268 {
269 return are_near(distance(_point, _line), 0, eps);
270 }
272 inline
273 bool are_parallel(Line const& l1, Line const& l2, double eps = EPSILON)
274 {
275 return ( are_near(l1.versor(), l2.versor(), eps)
276 || are_near(l1.versor(), -l2.versor(), eps) );
277 }
279 inline
280 bool are_same(Line const& l1, Line const& l2, double eps = EPSILON)
281 {
282 return are_parallel(l1, l2, eps) && are_near(l1.origin(), l2, eps);
283 }
285 inline
286 bool are_orthogonal(Line const& l1, Line const& l2, double eps = EPSILON)
287 {
288 return ( are_near(l1.versor(), l2.versor().cw(), eps)
289 || are_near(l1.versor(), l2.versor().ccw(), eps) );
290 }
292 inline
293 bool are_collinear(Point const& p1, Point const& p2, Point const& p3,
294 double eps = EPSILON)
295 {
296 return are_near( cross(p3, p2) - cross(p3, p1) + cross(p2, p1), 0, eps);
297 }
299 // evaluate the angle between l1 and l2 rotating l1 in cw direction
300 // until it overlaps l2
301 // the returned value is an angle in the interval [0, PI[
302 inline
303 double angle_between(Line const& l1, Line const& l2)
304 {
305 double angle = angle_between(l1.versor(), l2.versor());
306 if (angle < 0) angle += M_PI;
307 if (angle == M_PI) angle = 0;
308 return angle;
309 }
311 inline
312 double distance(Point const& _point, LineSegment const& _segment)
313 {
314 double t = _segment.nearestPoint(_point);
315 return L2(_point - _segment.pointAt(t));
316 }
318 inline
319 bool are_near(Point const& _point, LineSegment const& _segment,
320 double eps = EPSILON)
321 {
322 return are_near(distance(_point, _segment), 0, eps);
323 }
325 // build a line passing by _point and orthogonal to _line
326 inline
327 Line make_orthogonal_line(Point const& _point, Line const& _line)
328 {
329 Line l;
330 l.origin(_point);
331 l.versor(_line.versor().cw());
332 return l;
333 }
335 // build a line passing by _point and parallel to _line
336 inline
337 Line make_parallel_line(Point const& _point, Line const& _line)
338 {
339 Line l(_line);
340 l.origin(_point);
341 return l;
342 }
344 // build a line passing by the middle point of _segment and orthogonal to it.
345 inline
346 Line make_bisector_line(LineSegment const& _segment)
347 {
348 return make_orthogonal_line( middle_point(_segment), Line(_segment) );
349 }
351 // build the bisector line of the angle between ray(O,A) and ray(O,B)
352 inline
353 Line make_angle_bisector_line(Point const& A, Point const& O, Point const& B)
354 {
355 Point M = middle_point(A,B);
356 return Line(O,M);
357 }
359 // prj(P) = rot(v, Point( rot(-v, P-O)[X], 0 )) + O
360 inline
361 Point projection(Point const& _point, Line const& _line)
362 {
363 return _line.pointAt( _line.nearestPoint(_point) );
364 }
366 inline
367 LineSegment projection(LineSegment const& _segment, Line const& _line)
368 {
369 return _line.segment( _line.nearestPoint(_segment.initialPoint()),
370 _line.nearestPoint(_segment.finalPoint()) );
371 }
376 namespace detail
377 {
379 OptCrossing intersection_impl(Ray const& r1, Line const& l2, unsigned int i);
380 OptCrossing intersection_impl( LineSegment const& ls1,
381 Line const& l2,
382 unsigned int i );
383 OptCrossing intersection_impl( LineSegment const& ls1,
384 Ray const& r2,
385 unsigned int i );
386 }
389 inline
390 OptCrossing intersection(Ray const& r1, Line const& l2)
391 {
392 return detail::intersection_impl(r1, l2, 0);
394 }
396 inline
397 OptCrossing intersection(Line const& l1, Ray const& r2)
398 {
399 return detail::intersection_impl(r2, l1, 1);
400 }
402 inline
403 OptCrossing intersection(LineSegment const& ls1, Line const& l2)
404 {
405 return detail::intersection_impl(ls1, l2, 0);
406 }
408 inline
409 OptCrossing intersection(Line const& l1, LineSegment const& ls2)
410 {
411 return detail::intersection_impl(ls2, l1, 1);
412 }
414 inline
415 OptCrossing intersection(LineSegment const& ls1, Ray const& r2)
416 {
417 return detail::intersection_impl(ls1, r2, 0);
419 }
421 inline
422 OptCrossing intersection(Ray const& r1, LineSegment const& ls2)
423 {
424 return detail::intersection_impl(ls2, r1, 1);
425 }
428 OptCrossing intersection(Line const& l1, Line const& l2);
430 OptCrossing intersection(Ray const& r1, Ray const& r2);
432 OptCrossing intersection(LineSegment const& ls1, LineSegment const& ls2);
435 } // end namespace Geom
438 #endif // _2GEOM_LINE_H_
441 /*
442 Local Variables:
443 mode:c++
444 c-file-style:"stroustrup"
445 c-file-offsets:((innamespace . 0)(substatement-open . 0))
446 indent-tabs-mode:nil
447 c-brace-offset:0
448 fill-column:99
449 End:
450 vim: filetype=cpp:expandtab:shiftwidth=4:tabstop=8:softtabstop=4 :
451 */