1 // This is core/vgl/vgl_intersection.h
2 #ifndef vgl_intersection_h_
3 #define vgl_intersection_h_
4 //:
5 // \file
6 // \brief Set of intersection functions
7 // \author Jan 25, 2007 Gamze Tunali
8 //
9 // For intersections of "homogeneous coordinates" objects like vgl_homg_line_2d<T>,
10 // see the static methods of vgl/algo/vgl_homg_operators_2d<T> and _3d.
11 //
12 // \verbatim
13 // Modifications
14 // 01 Mar 2007 - Gamze Tunali - split up into vgl/algo and vgl parts
15 // 21 Jul 2009 - Peter Vanroose - added box intersection (2d and 3d)
16 // 21 Jul 2009 - Peter Vanroose - added inlined point intersection functions
17 // \endverbatim
18
19 #include <vector>
20 #include "vgl_fwd.h" // forward declare various vgl classes
21 #include "vgl_box_2d.h" // method "contains()"
22 #include "vgl_box_3d.h" // method "contains()"
23 #include "vgl_point_2d.h" // method "operator==()"
24 #include "vgl_point_3d.h" // method "operator==()"
25 #include "vgl_line_3d_2_points.h"
26 #include "vgl_line_segment_3d.h"
27 #include "vgl_infinite_line_3d.h"
28 #include "vgl_pointset_3d.h"
29 #ifdef _MSC_VER
30 # include <vcl_msvc_warnings.h>
31 #endif
32
33 //: Return true if the two points intersect, i.e., coincide
34 // \relatesalso vgl_point_2d
35 template <class T>
vgl_intersection(vgl_point_2d<T> const & p0,vgl_point_2d<T> const & p1)36 inline bool vgl_intersection(vgl_point_2d<T> const& p0,
37 vgl_point_2d<T> const& p1)
38 { return p0 == p1; }
39
40 //: Return true if the two points intersect, i.e., coincide
41 // \relatesalso vgl_point_2d
42 template <class T>
vgl_intersection(vgl_point_3d<T> const & p0,vgl_point_3d<T> const & p1)43 inline bool vgl_intersection(vgl_point_3d<T> const& p0,
44 vgl_point_3d<T> const& p1)
45 { return p0 == p1; }
46
47 //: Return true if line intersects box. If so, compute intersection points.
48 // \relatesalso vgl_line_2d
49 template <class T>
50 bool vgl_intersection(vgl_box_2d<T> const& box,
51 vgl_line_2d<T> const& line,
52 vgl_point_2d<T>& p0,
53 vgl_point_2d<T>& p1);
54
55 //: Return true if line intersects box.If so,return the line segment inside box.
56 // \relatesalso vgl_line_2d
57 template <class T>
58 bool vgl_intersection(vgl_box_2d<T> const& box,
59 vgl_line_segment_2d<T> const& line,
60 vgl_line_segment_2d<T>& int_line);
61
62 //: Returns the number of intersections of a line segment with a box, up to two are returned in p0 and p1.(warning! one intersection could be either p0 or p1)
63 // \relatesalso vgl_line_segment_2d
64 template <class T>
65 unsigned vgl_intersection(vgl_box_2d<T> const& box,
66 vgl_line_segment_2d<T> const& line,
67 vgl_point_2d<T>& p0,
68 vgl_point_2d<T>& p1);
69
70 //: Return true if two line segments intersect. If so,return the intersection point.
71 // \relatesalso vgl_line_segment_2d
72 template <class T>
73 bool vgl_intersection(vgl_line_segment_2d<T> const& line1,
74 vgl_line_segment_2d<T> const& line2,
75 vgl_point_2d<T>& int_pt);
76
77 //: Return the intersection point of two concurrent lines
78 // \relatesalso vgl_line_3d_2_points
79 //Allows intersection points outside the line segments
80 //Throws an assertion if lines not concurrent
81 template <class T>
82 vgl_point_3d<T> vgl_intersection(vgl_line_3d_2_points<T> const& l1,
83 vgl_line_3d_2_points<T> const& l2);
84
85 //: Return the intersection point of segments of two concurrent lines. Returns false if the intersection point is not inside both line segments
86 // \relatesalso vgl_line_segment_3d.
87 //
88 template <class T>
89 bool vgl_intersection(vgl_line_segment_3d<T> const& l1,
90 vgl_line_segment_3d<T> const& l2,
91 vgl_point_3d<T>& i_pnt);
92
93 //: Return the intersection point of segments of a concurrent line and line segment pair. Returns false if the intersection point is not inside both line segments
94 // \relatesalso vgl_line_segment_3d
95 // \relatesalso vgl_line_3d_2_points
96 template <class T>
97 bool vgl_intersection(vgl_line_3d_2_points<T> const& l1,
98 vgl_line_segment_3d<T> const& l2,
99 vgl_point_3d<T>& i_pnt);
100
101 template <class T> inline
vgl_intersection(vgl_line_segment_3d<T> const & l1,vgl_line_3d_2_points<T> const & l2,vgl_point_3d<T> & i_pnt)102 bool vgl_intersection(vgl_line_segment_3d<T> const& l1,
103 vgl_line_3d_2_points<T> const& l2,
104 vgl_point_3d<T>& i_pnt)
105 {
106 return vgl_intersection(l2, l1, i_pnt);
107 }
108
109 //: Return the intersection point of infinite lines, if concurrent.
110 // \relatesalso vgl_infinite_line_3d
111 template <class T>
112 bool vgl_intersection(vgl_infinite_line_3d<T> const& l1,
113 vgl_infinite_line_3d<T> const& l2,
114 vgl_point_3d<T>& i_pnt);
115
116 //: Return the intersection point of rays. Returns false if rays are parallel or intersect outside of positive ray domain
117 // \relatesalso vgl_ray_3d
118 template <class T>
119 bool vgl_intersection(vgl_ray_3d<T> const& r1,
120 vgl_ray_3d<T> const& r2,
121 vgl_point_3d<T>& i_pnt);
122
123 //: Return the intersection point of two lines. Return false if lines are parallel
124 // \relatesalso vgl_line_2d
125 template <class T>
126 bool vgl_intersection(vgl_line_2d<T> const& line0,
127 vgl_line_2d<T> const& line1,
128 vgl_point_2d<T> &intersection_point );
129
130
131 //: Return the intersection point of a line and a plane.
132 // \relatesalso vgl_line_3d_2_points
133 // \relatesalso vgl_plane_3d
134 template <class T>
135 vgl_point_3d<T> vgl_intersection(vgl_line_3d_2_points<T> const& line,
136 vgl_plane_3d<T> const& plane);
137
138 //: Return the intersection point of a line and a plane.
139 // \relatesalso vgl_line_segment_3d
140 // \relatesalso vgl_plane_3d
141 template <class T>
142 bool vgl_intersection(vgl_line_segment_3d<T> const& line,
143 vgl_plane_3d<T> const& plane,
144 vgl_point_3d<T> & i_pt);
145
146
147 //: Return the intersection point of a line and a plane.
148 // \relatesalso vgl_line_segment_3d
149 // \relatesalso vgl_plane_3d
150 template <class T>
151 bool vgl_intersection(vgl_infinite_line_3d<T> const& line,
152 vgl_plane_3d<T> const& plane,
153 vgl_point_3d<T> & i_pt);
154
155 //: Return the intersection point of a ray and a plane.
156 // \relatesalso vgl_line_segment_3d
157 // \relatesalso vgl_plane_3d
158 template <class T>
159 bool vgl_intersection(vgl_ray_3d<T> const& ray,
160 vgl_plane_3d<T> const& plane,
161 vgl_point_3d<T> & i_pt);
162
163 //: Return the intersection line of two planes.
164 // Returns false if planes are effectively parallel
165 // \relatesalso vgl_line_segment_3d
166 // \relatesalso vgl_plane_3d
167 template <class T>
vgl_intersection(vgl_plane_3d<T> const & plane0,vgl_plane_3d<T> const & plane1,vgl_line_segment_3d<T> & line)168 bool vgl_intersection(vgl_plane_3d<T> const& plane0,
169 vgl_plane_3d<T> const& plane1,
170 vgl_line_segment_3d<T> & line){
171 vgl_infinite_line_3d<T> inf_l;
172 bool status = vgl_intersection(plane0, plane1, inf_l);
173 if (status)
174 line.set(inf_l.point_t(T(0)), inf_l.point_t(T(1)));
175 return status;
176 }
177
178 template <class T>
vgl_intersection(vgl_plane_3d<T> const & plane0,vgl_plane_3d<T> const & plane1,vgl_line_3d_2_points<T> & line)179 bool vgl_intersection(vgl_plane_3d<T> const& plane0,
180 vgl_plane_3d<T> const& plane1,
181 vgl_line_3d_2_points<T> & line){
182 vgl_infinite_line_3d<T> inf_l;
183 bool status = vgl_intersection(plane0, plane1, inf_l);
184 if (status)
185 line.set(inf_l.point_t(T(0)), inf_l.point_t(T(1)));
186 return status;
187 }
188
189 template <class T>
190 bool vgl_intersection(vgl_plane_3d<T> const& plane0,
191 vgl_plane_3d<T> const& plane1,
192 vgl_infinite_line_3d<T> & line);
193
194 //: Return the intersection point of three planes.
195 // \relatesalso vgl_plane_3d
196 template <class T>
197 vgl_point_3d<T> vgl_intersection(vgl_plane_3d<T> const& p1,
198 vgl_plane_3d<T> const& p2,
199 vgl_plane_3d<T> const& p3);
200
201 //: Return true if any point on [p1,p2] is within tol of [q1,q2]
202 // Tests two line segments for intersection or near intersection
203 // (within given tolerance).
204 // \author Dan jackson
205 // \relatesalso vgl_point_2d
206 template <class T>
207 bool vgl_intersection(vgl_point_2d<T> const& p1,
208 vgl_point_2d<T> const& p2,
209 vgl_point_2d<T> const& q1,
210 vgl_point_2d<T> const& q2,
211 double tol = 1e-6);
212
213 //: Return true if the point lies inside the box
214 // \relatesalso vgl_point_2d
215 // \relatesalso vgl_box_2d
216 template <class T>
vgl_intersection(vgl_box_2d<T> const & b,vgl_point_2d<T> const & p)217 inline bool vgl_intersection(vgl_box_2d<T> const& b, vgl_point_2d<T> const& p)
218 { return b.contains(p); }
219
220 //: Return true if the point lies inside the box
221 // \relatesalso vgl_point_2d
222 // \relatesalso vgl_box_2d
223 template <class T>
vgl_intersection(vgl_point_2d<T> const & p,vgl_box_2d<T> const & b)224 inline bool vgl_intersection(vgl_point_2d<T> const& p, vgl_box_2d<T> const& b)
225 { return b.contains(p); }
226
227 //: Return true if the point lies inside the box
228 // \relatesalso vgl_point_3d
229 // \relatesalso vgl_box_3d
230 template <class T>
vgl_intersection(vgl_box_3d<T> const & b,vgl_point_3d<T> const & p)231 inline bool vgl_intersection(vgl_box_3d<T> const& b, vgl_point_3d<T> const& p)
232 { return b.contains(p); }
233
234 //: Return true if the point lies inside the box
235 // \relatesalso vgl_point_3d
236 // \relatesalso vgl_box_3d
237 template <class T>
vgl_intersection(vgl_point_3d<T> const & p,vgl_box_3d<T> const & b)238 inline bool vgl_intersection(vgl_point_3d<T> const& p, vgl_box_3d<T> const& b)
239 { return b.contains(p); }
240
241 //: Return true if line intersects box. If so, compute intersection points.
242 // \relatesalso vgl_infinite_line_3d
243 template <class T>
244 bool vgl_intersection(vgl_box_3d<T> const& box,
245 vgl_infinite_line_3d<T> const& line,
246 vgl_point_3d<T>& p0,
247 vgl_point_3d<T>& p1);
248 //: Return true if ray intersects box. If so, compute intersection points.
249 // If ray origin is inside box then p0==p1
250 // \relatesalso vgl_ray_3d
251 template <class T>
252 bool vgl_intersection(vgl_box_3d<T> const& box,
253 vgl_ray_3d<T> const& ray,
254 vgl_point_3d<T>& p0,
255 vgl_point_3d<T>& p1);
256 //: Return true if a box and plane intersect in 3D
257 // \relatesalso vgl_plane_3d
258 // \relatesalso vgl_box_3d
259 template <class T>
260 bool vgl_intersection(vgl_box_3d<T> const& b, vgl_plane_3d<T> const& plane);
261
262
263 //: Return the intersection of two boxes (which is itself either a box, or empty)
264 // \relatesalso vgl_box_2d
265 template <class T>
266 vgl_box_2d<T> vgl_intersection(vgl_box_2d<T> const&,vgl_box_2d<T> const&);
267
268 //: Return the intersection of two boxes (which is itself either a box, or empty)
269 // \relatesalso vgl_box_3d
270 template <class T>
271 vgl_box_3d<T> vgl_intersection(vgl_box_3d<T> const&,vgl_box_3d<T> const&);
272
273 //: Return true if the box and polygon regions intersect, regions include boundaries
274 // \relatesalso vgl_polygon
275 // \relatesalso vgl_box_2d
276 template <class T>
277 bool vgl_intersection(vgl_box_2d<T> const& b, vgl_polygon<T> const& poly);
278
279 //: Return the points from the list that lie inside the box
280 // \relatesalso vgl_point_2d
281 // \relatesalso vgl_box_2d
282 template <class T>
283 std::vector<vgl_point_2d<T> > vgl_intersection(vgl_box_2d<T> const& b, std::vector<vgl_point_2d<T> > const& p);
284
285 //: Return the points from the list that lie inside the box
286 // \relatesalso vgl_point_2d
287 // \relatesalso vgl_box_2d
288 template <class T>
289 std::vector<vgl_point_2d<T> > vgl_intersection(std::vector<vgl_point_2d<T> > const& p, vgl_box_2d<T> const& b);
290
291 //: Return the points from the list that lie inside the box
292 // \relatesalso vgl_point_3d
293 // \relatesalso vgl_box_3d
294 template <class T>
295 std::vector<vgl_point_3d<T> > vgl_intersection(vgl_box_3d<T> const& b, std::vector<vgl_point_3d<T> > const& p);
296
297 //: Return the points from the list that lie inside the box
298 // \relatesalso vgl_point_3d
299 // \relatesalso vgl_box_3d
300 template <class T>
301 std::vector<vgl_point_3d<T> > vgl_intersection(std::vector<vgl_point_3d<T> > const& p, vgl_box_3d<T> const& b);
302
303 //: Find the intersections of a line with a polygon( can have multiple sheets)
304 // \relatesalso vgl_line_2d
305 // \relatesalso vgl_point_2d
306 template <class T>
307 std::vector<vgl_point_2d<T> > vgl_intersection(vgl_polygon<T> const& poly,
308 vgl_line_2d<T> const& line);
309 template <class T>
vgl_intersection(vgl_line_2d<T> const & line,vgl_polygon<T> const & poly)310 std::vector<vgl_point_2d<T> > vgl_intersection(vgl_line_2d<T> const& line,
311 vgl_polygon<T> const& poly){
312 return vgl_intersection(poly, line);
313 }
314 // SEE vgl_clip.h to compute the intersection (as well as other boolean operations) of two vgl_polygons
315
316 //: return the intersection of a pointset with a plane, given a tolerance tol
317 // the normal distance from the plane to the point is compared to the tolerance
318 // the points within tolerance are projected along the normal direction onto the plane
319 template <class T>
320 vgl_pointset_3d<T> vgl_intersection(vgl_plane_3d<T> const& plane, vgl_pointset_3d<T> const& ptset, T tol);
321
322 template <class T>
vgl_intersection(vgl_pointset_3d<T> const & ptset,vgl_plane_3d<T> const & plane,T tol)323 vgl_pointset_3d<T> vgl_intersection(vgl_pointset_3d<T> const& ptset, vgl_plane_3d<T> const& plane, T tol){
324 return vgl_intersection(plane, ptset, tol);}
325
326 //: intersection of a box with the pointset
327 template <class T>
328 vgl_pointset_3d<T> vgl_intersection(vgl_box_3d<T> const& box, vgl_pointset_3d<T> const& ptset);
329
330 template <class T>
vgl_intersection(vgl_pointset_3d<T> const & ptset,vgl_box_3d<T> const & box)331 vgl_pointset_3d<T> vgl_intersection(vgl_pointset_3d<T> const& ptset, vgl_box_3d<T> const& box){
332 return vgl_intersection(box, ptset);}
333
334
335 template <class T>
336 vgl_pointset_3d<T> vgl_intersection(vgl_plane_3d<T> const& plane, vgl_pointset_3d<T> const& ptset, T tol);
337
338 #define VGL_INTERSECTION_INSTANTIATE(T) extern "please include vgl/vgl_intersection.hxx first"
339 #define VGL_INTERSECTION_BOX_INSTANTIATE(T) extern "please include vgl/vgl_intersection.hxx first"
340
341 #endif // vgl_intersection_h_
342