1 /*
2 * Infinite Straight Line
3 *
4 * Copyright 2008 Marco Cecchetti <mrcekets at gmail.com>
5 * Nathan Hurst
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 */
32 #include <2geom/line.h>
34 #include <algorithm>
37 namespace Geom
38 {
40 namespace detail
41 {
43 inline
44 OptCrossing intersection_impl(Point const& V1, Point const O1,
45 Point const& V2, Point const O2 )
46 {
47 double detV1V2 = V1[X] * V2[Y] - V2[X] * V1[Y];
48 if (are_near(detV1V2, 0)) return OptCrossing();
50 Point B = O2 - O1;
51 double detBV2 = B[X] * V2[Y] - V2[X] * B[Y];
52 double detV1B = B[X] * V1[Y] - V1[X] * B[Y];
53 double inv_detV1V2 = 1 / detV1V2;
55 Crossing c;
56 c.ta = detBV2 * inv_detV1V2;
57 c.tb = detV1B * inv_detV1V2;
58 // std::cerr << "ta = " << solution.ta << std::endl;
59 // std::cerr << "tb = " << solution.tb << std::endl;
60 return OptCrossing(c);
61 }
64 OptCrossing intersection_impl(Ray const& r1, Line const& l2, unsigned int i)
65 {
66 OptCrossing crossing =
67 intersection_impl(r1.versor(), r1.origin(),
68 l2.versor(), l2.origin() );
70 if (crossing)
71 {
72 if (crossing->ta < 0)
73 {
74 return OptCrossing();
75 }
76 else
77 {
78 if (i != 0)
79 {
80 std::swap(crossing->ta, crossing->tb);
81 }
82 return crossing;
83 }
84 }
85 if (are_near(r1.origin(), l2))
86 {
87 THROW_INFINITESOLUTIONS();
88 }
89 else
90 {
91 return OptCrossing();
92 }
93 }
96 OptCrossing intersection_impl( LineSegment const& ls1,
97 Line const& l2,
98 unsigned int i )
99 {
100 OptCrossing crossing =
101 intersection_impl(ls1.finalPoint() - ls1.initialPoint(),
102 ls1.initialPoint(),
103 l2.versor(),
104 l2.origin() );
106 if (crossing)
107 {
108 if ( crossing->getTime(0) < 0
109 || crossing->getTime(0) > 1 )
110 {
111 return OptCrossing();
112 }
113 else
114 {
115 if (i != 0)
116 {
117 std::swap((*crossing).ta, (*crossing).tb);
118 }
119 return crossing;
120 }
121 }
122 if (are_near(ls1.initialPoint(), l2))
123 {
124 THROW_INFINITESOLUTIONS();
125 }
126 else
127 {
128 return OptCrossing();
129 }
130 }
133 OptCrossing intersection_impl( LineSegment const& ls1,
134 Ray const& r2,
135 unsigned int i )
136 {
137 Point direction = ls1.finalPoint() - ls1.initialPoint();
138 OptCrossing crossing =
139 intersection_impl( direction,
140 ls1.initialPoint(),
141 r2.versor(),
142 r2.origin() );
144 if (crossing)
145 {
146 if ( crossing->getTime(0) < 0
147 || crossing->getTime(0) > 1
148 || crossing->getTime(1) < 0 )
149 {
150 return OptCrossing();
151 }
152 else
153 {
154 if (i != 0)
155 {
156 std::swap(crossing->ta, crossing->tb);
157 }
158 return crossing;
159 }
160 }
162 if ( are_near(r2.origin(), ls1) )
163 {
164 bool eqvs = (dot(direction, r2.versor()) > 0);
165 if ( are_near(ls1.initialPoint(), r2.origin()) && !eqvs )
166 {
167 crossing->ta = crossing->tb = 0;
168 return crossing;
169 }
170 else if ( are_near(ls1.finalPoint(), r2.origin()) && eqvs )
171 {
172 if (i == 0)
173 {
174 crossing->ta = 1;
175 crossing->tb = 0;
176 }
177 else
178 {
179 crossing->ta = 0;
180 crossing->tb = 1;
181 }
182 return crossing;
183 }
184 else
185 {
186 THROW_INFINITESOLUTIONS();
187 }
188 }
189 else if ( are_near(ls1.initialPoint(), r2) )
190 {
191 THROW_INFINITESOLUTIONS();
192 }
193 else
194 {
195 OptCrossing no_crossing;
196 return no_crossing;
197 }
198 }
200 } // end namespace detail
204 OptCrossing intersection(Line const& l1, Line const& l2)
205 {
206 OptCrossing crossing =
207 detail::intersection_impl( l1.versor(), l1.origin(),
208 l2.versor(), l2.origin() );
209 if (crossing)
210 {
211 return crossing;
212 }
213 if (are_near(l1.origin(), l2))
214 {
215 THROW_INFINITESOLUTIONS();
216 }
217 else
218 {
219 return crossing;
220 }
221 }
224 OptCrossing intersection(Ray const& r1, Ray const& r2)
225 {
226 OptCrossing crossing =
227 detail::intersection_impl( r1.versor(), r1.origin(),
228 r2.versor(), r2.origin() );
230 if (crossing)
231 {
232 if ( crossing->ta < 0
233 || crossing->tb < 0 )
234 {
235 OptCrossing no_crossing;
236 return no_crossing;
237 }
238 else
239 {
240 return crossing;
241 }
242 }
244 if ( are_near(r1.origin(), r2) || are_near(r2.origin(), r1) )
245 {
246 if ( are_near(r1.origin(), r2.origin())
247 && !are_near(r1.versor(), r2.versor()) )
248 {
249 crossing->ta = crossing->tb = 0;
250 return crossing;
251 }
252 else
253 {
254 THROW_INFINITESOLUTIONS();
255 }
256 }
257 else
258 {
259 OptCrossing no_crossing;
260 return no_crossing;
261 }
262 }
265 OptCrossing intersection( LineSegment const& ls1, LineSegment const& ls2 )
266 {
267 Point direction1 = ls1.finalPoint() - ls1.initialPoint();
268 Point direction2 = ls2.finalPoint() - ls2.initialPoint();
269 OptCrossing crossing =
270 detail::intersection_impl( direction1,
271 ls1.initialPoint(),
272 direction2,
273 ls2.initialPoint() );
275 if (crossing)
276 {
277 if ( crossing->getTime(0) < 0
278 || crossing->getTime(0) > 1
279 || crossing->getTime(1) < 0
280 || crossing->getTime(1) > 1 )
281 {
282 OptCrossing no_crossing;
283 return no_crossing;
284 }
285 else
286 {
287 return crossing;
288 }
289 }
291 bool eqvs = (dot(direction1, direction2) > 0);
292 if ( are_near(ls2.initialPoint(), ls1) )
293 {
294 if ( are_near(ls1.initialPoint(), ls2.initialPoint()) && !eqvs )
295 {
296 crossing->ta = crossing->tb = 0;
297 return crossing;
298 }
299 else if ( are_near(ls1.finalPoint(), ls2.initialPoint()) && eqvs )
300 {
301 crossing->ta = 1;
302 crossing->tb = 0;
303 return crossing;
304 }
305 else
306 {
307 THROW_INFINITESOLUTIONS();
308 }
309 }
310 else if ( are_near(ls2.finalPoint(), ls1) )
311 {
312 if ( are_near(ls1.finalPoint(), ls2.finalPoint()) && !eqvs )
313 {
314 crossing->ta = crossing->tb = 1;
315 return crossing;
316 }
317 else if ( are_near(ls1.initialPoint(), ls2.finalPoint()) && eqvs )
318 {
319 crossing->ta = 0;
320 crossing->tb = 1;
321 return crossing;
322 }
323 else
324 {
325 THROW_INFINITESOLUTIONS();
326 }
327 }
328 else
329 {
330 OptCrossing no_crossing;
331 return no_crossing;
332 }
333 }
337 Line make_angle_bisector_line(Line const& l1, Line const& l2)
338 {
339 OptCrossing crossing;
340 try
341 {
342 crossing = intersection(l1, l2);
343 }
344 catch(InfiniteSolutions e)
345 {
346 return l1;
347 }
348 if (!crossing)
349 {
350 THROW_RANGEERROR("passed lines are parallel");
351 }
352 Point O = l1.pointAt(crossing->ta);
353 Point A = l1.pointAt(crossing->ta + 1);
354 double angle = angle_between(l1.versor(), l2.versor());
355 Point B = (angle > 0) ? l2.pointAt(crossing->tb + 1)
356 : l2.pointAt(crossing->tb - 1);
358 return make_angle_bisector_line(A, O, B);
359 }
362 } // end namespace Geom
366 /*
367 Local Variables:
368 mode:c++
369 c-file-style:"stroustrup"
370 c-file-offsets:((innamespace . 0)(substatement-open . 0))
371 indent-tabs-mode:nil
372 c-brace-offset:0
373 fill-column:99
374 End:
375 vim: filetype=cpp:expandtab:shiftwidth=4:tabstop=8:softtabstop=4 :
376 */