]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
1 | // Boost.Polygon library segment_concept.hpp header file |
2 | ||
3 | // Copyright (c) Intel Corporation 2008. | |
4 | // Copyright (c) 2008-2012 Simonson Lucanus. | |
5 | // Copyright (c) 2012-2012 Andrii Sydorchuk. | |
6 | ||
7 | // See http://www.boost.org for updates, documentation, and revision history. | |
8 | // Use, modification and distribution is subject to the Boost Software License, | |
9 | // Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at | |
10 | // http://www.boost.org/LICENSE_1_0.txt) | |
11 | ||
12 | #ifndef BOOST_POLYGON_SEGMENT_CONCEPT_HPP | |
13 | #define BOOST_POLYGON_SEGMENT_CONCEPT_HPP | |
14 | ||
15 | #include "isotropy.hpp" | |
16 | #include "segment_traits.hpp" | |
17 | #include "rectangle_concept.hpp" | |
18 | ||
19 | namespace boost { | |
20 | namespace polygon { | |
21 | ||
22 | struct segment_concept {}; | |
23 | ||
24 | template <typename ConceptType> | |
25 | struct is_segment_concept { | |
26 | typedef gtl_no type; | |
27 | }; | |
28 | ||
29 | template <> | |
30 | struct is_segment_concept<segment_concept> { | |
31 | typedef gtl_yes type; | |
32 | }; | |
33 | ||
34 | template <typename ConceptType> | |
35 | struct is_mutable_segment_concept { | |
36 | typedef gtl_no type; | |
37 | }; | |
38 | ||
39 | template <> | |
40 | struct is_mutable_segment_concept<segment_concept> { | |
41 | typedef gtl_yes type; | |
42 | }; | |
43 | ||
44 | template <typename GeometryType, typename BoolType> | |
45 | struct segment_distance_type_by_concept { | |
46 | typedef void type; | |
47 | }; | |
48 | ||
49 | template <typename GeometryType> | |
50 | struct segment_distance_type_by_concept<GeometryType, gtl_yes> { | |
51 | typedef typename coordinate_traits< | |
52 | typename segment_traits<GeometryType>::coordinate_type | |
53 | >::coordinate_distance type; | |
54 | }; | |
55 | ||
56 | template <typename GeometryType> | |
57 | struct segment_distance_type { | |
58 | typedef typename segment_distance_type_by_concept< | |
59 | GeometryType, | |
60 | typename is_segment_concept< | |
61 | typename geometry_concept<GeometryType>::type | |
62 | >::type | |
63 | >::type type; | |
64 | }; | |
65 | ||
66 | template <typename GeometryType, typename BoolType> | |
67 | struct segment_point_type_by_concept { | |
68 | typedef void type; | |
69 | }; | |
70 | ||
71 | template <typename GeometryType> | |
72 | struct segment_point_type_by_concept<GeometryType, gtl_yes> { | |
73 | typedef typename segment_traits<GeometryType>::point_type type; | |
74 | }; | |
75 | ||
76 | template <typename GeometryType> | |
77 | struct segment_point_type { | |
78 | typedef typename segment_point_type_by_concept< | |
79 | GeometryType, | |
80 | typename is_segment_concept< | |
81 | typename geometry_concept<GeometryType>::type | |
82 | >::type | |
83 | >::type type; | |
84 | }; | |
85 | ||
86 | template <typename GeometryType, typename BoolType> | |
87 | struct segment_coordinate_type_by_concept { | |
88 | typedef void type; | |
89 | }; | |
90 | ||
91 | template <typename GeometryType> | |
92 | struct segment_coordinate_type_by_concept<GeometryType, gtl_yes> { | |
93 | typedef typename segment_traits<GeometryType>::coordinate_type type; | |
94 | }; | |
95 | ||
96 | template <typename GeometryType> | |
97 | struct segment_coordinate_type { | |
98 | typedef typename segment_coordinate_type_by_concept< | |
99 | GeometryType, | |
100 | typename is_segment_concept< | |
101 | typename geometry_concept<GeometryType>::type | |
102 | >::type | |
103 | >::type type; | |
104 | }; | |
105 | ||
106 | struct y_s_get : gtl_yes {}; | |
107 | ||
108 | template <typename Segment> | |
109 | typename enable_if< | |
110 | typename gtl_and< | |
111 | y_s_get, | |
112 | typename is_segment_concept< | |
113 | typename geometry_concept<Segment>::type | |
114 | >::type | |
115 | >::type, | |
116 | typename segment_point_type<Segment>::type>::type | |
117 | get(const Segment& segment, direction_1d dir) { | |
118 | return segment_traits<Segment>::get(segment, dir); | |
119 | } | |
120 | ||
121 | struct y_s_set : gtl_yes {}; | |
122 | ||
123 | template <typename Segment, typename Point> | |
124 | typename enable_if< | |
125 | typename gtl_and_3< | |
126 | y_s_set, | |
127 | typename is_mutable_segment_concept< | |
128 | typename geometry_concept<Segment>::type | |
129 | >::type, | |
130 | typename is_point_concept< | |
131 | typename geometry_concept<Point>::type | |
132 | >::type | |
133 | >::type, | |
134 | void>::type set(Segment& segment, direction_1d dir, const Point& point) { | |
135 | segment_mutable_traits<Segment>::set(segment, dir, point); | |
136 | } | |
137 | ||
138 | struct y_s_construct : gtl_yes {}; | |
139 | ||
140 | template <typename Segment, typename Point1, typename Point2> | |
141 | typename enable_if< | |
142 | typename gtl_and_4< | |
143 | y_s_construct, | |
144 | typename is_mutable_segment_concept< | |
145 | typename geometry_concept<Segment>::type | |
146 | >::type, | |
147 | typename is_point_concept< | |
148 | typename geometry_concept<Point1>::type | |
149 | >::type, | |
150 | typename is_point_concept< | |
151 | typename geometry_concept<Point2>::type | |
152 | >::type | |
153 | >::type, | |
154 | Segment>::type construct(const Point1& low, const Point2& high) { | |
155 | return segment_mutable_traits<Segment>::construct(low, high); | |
156 | } | |
157 | ||
158 | struct y_s_copy_construct : gtl_yes {}; | |
159 | ||
160 | template <typename Segment1, typename Segment2> | |
161 | typename enable_if< | |
162 | typename gtl_and_3< | |
163 | y_s_copy_construct, | |
164 | typename is_mutable_segment_concept< | |
165 | typename geometry_concept<Segment1>::type | |
166 | >::type, | |
167 | typename is_segment_concept< | |
168 | typename geometry_concept<Segment2>::type | |
169 | >::type | |
170 | >::type, | |
171 | Segment1>::type copy_construct(const Segment2& segment) { | |
172 | return construct<Segment1>(get(segment, LOW), get(segment, HIGH)); | |
173 | } | |
174 | ||
175 | struct y_s_assign : gtl_yes {}; | |
176 | ||
177 | template <typename Segment1, typename Segment2> | |
178 | typename enable_if< | |
179 | typename gtl_and_3< | |
180 | y_s_assign, | |
181 | typename is_mutable_segment_concept< | |
182 | typename geometry_concept<Segment1>::type | |
183 | >::type, | |
184 | typename is_segment_concept< | |
185 | typename geometry_concept<Segment2>::type | |
186 | >::type | |
187 | >::type, | |
188 | Segment1>::type& assign(Segment1& segment1, const Segment2& segment2) { | |
189 | return segment1 = copy_construct<Segment1>(segment2); | |
190 | } | |
191 | ||
192 | struct y_s_equivalence : gtl_yes {}; | |
193 | ||
194 | template <typename Segment1, typename Segment2> | |
195 | typename enable_if< | |
196 | typename gtl_and_3< | |
197 | y_s_equivalence, | |
198 | typename is_segment_concept< | |
199 | typename geometry_concept<Segment1>::type | |
200 | >::type, | |
201 | typename is_segment_concept< | |
202 | typename geometry_concept<Segment2>::type | |
203 | >::type | |
204 | >::type, | |
205 | bool>::type equivalence(const Segment1& segment1, const Segment2& segment2) { | |
206 | return get(segment1, LOW) == get(segment2, LOW) && | |
207 | get(segment1, HIGH) == get(segment2, HIGH); | |
208 | } | |
209 | ||
210 | struct y_s_low : gtl_yes {}; | |
211 | ||
212 | template <typename Segment> | |
213 | typename enable_if< | |
214 | typename gtl_and< | |
215 | y_s_low, | |
216 | typename is_segment_concept< | |
217 | typename geometry_concept<Segment>::type | |
218 | >::type | |
219 | >::type, | |
220 | typename segment_point_type<Segment>::type>::type low(const Segment& segment) { | |
221 | return get(segment, LOW); | |
222 | } | |
223 | ||
224 | struct y_s_high : gtl_yes {}; | |
225 | ||
226 | template <typename Segment> | |
227 | typename enable_if< | |
228 | typename gtl_and< | |
229 | y_s_high, | |
230 | typename is_segment_concept< | |
231 | typename geometry_concept<Segment>::type | |
232 | >::type | |
233 | >::type, | |
234 | typename segment_point_type<Segment>::type>::type high(const Segment& segment) { | |
235 | return get(segment, HIGH); | |
236 | } | |
237 | ||
238 | struct y_s_center : gtl_yes {}; | |
239 | ||
240 | template <typename Segment> | |
241 | typename enable_if< | |
242 | typename gtl_and< | |
243 | y_s_center, | |
244 | typename is_segment_concept< | |
245 | typename geometry_concept<Segment>::type | |
246 | >::type | |
247 | >::type, | |
248 | typename segment_point_type<Segment>::type>::type | |
249 | center(const Segment& segment) { | |
250 | return construct<typename segment_point_type<Segment>::type>( | |
251 | (x(high(segment)) + x(low(segment)))/2, | |
252 | (y(high(segment)) + y(low(segment)))/2); | |
253 | } | |
254 | ||
255 | struct y_s_low2 : gtl_yes {}; | |
256 | ||
257 | template <typename Segment, typename Point> | |
258 | typename enable_if< | |
259 | typename gtl_and_3< | |
260 | y_s_low2, | |
261 | typename is_mutable_segment_concept< | |
262 | typename geometry_concept<Segment>::type | |
263 | >::type, | |
264 | typename is_point_concept< | |
265 | typename geometry_concept<Point>::type | |
266 | >::type | |
267 | >::type, | |
268 | void>::type low(Segment& segment, const Point& point) { | |
269 | set(segment, LOW, point); | |
270 | } | |
271 | ||
272 | struct y_s_high2 : gtl_yes {}; | |
273 | ||
274 | template <typename Segment, typename Point> | |
275 | typename enable_if< | |
276 | typename gtl_and_3< | |
277 | y_s_high2, | |
278 | typename is_mutable_segment_concept< | |
279 | typename geometry_concept<Segment>::type | |
280 | >::type, | |
281 | typename is_point_concept< | |
282 | typename geometry_concept<Point>::type | |
283 | >::type | |
284 | >::type, | |
285 | void>::type high(Segment& segment, const Point& point) { | |
286 | set(segment, HIGH, point); | |
287 | } | |
288 | ||
289 | struct y_s_orientation1 : gtl_yes {}; | |
290 | ||
291 | // -1 for CW, 0 for collinear and 1 for CCW. | |
292 | template <typename Segment1, typename Segment2> | |
293 | typename enable_if< | |
294 | typename gtl_and_3< | |
295 | y_s_orientation1, | |
296 | typename is_segment_concept< | |
297 | typename geometry_concept<Segment1>::type | |
298 | >::type, | |
299 | typename is_segment_concept< | |
300 | typename geometry_concept<Segment2>::type | |
301 | >::type | |
302 | >::type, | |
303 | int>::type orientation(const Segment1& segment1, const Segment2& segment2) { | |
304 | typedef typename coordinate_traits< | |
305 | typename segment_traits<Segment1>::coordinate_type | |
306 | >::manhattan_area_type int_x2; | |
307 | typedef typename coordinate_traits< | |
308 | typename segment_traits<Segment1>::coordinate_type | |
309 | >::unsigned_area_type uint_x2; | |
310 | int_x2 a1 = (int_x2)x(high(segment1)) - (int_x2)x(low(segment1)); | |
311 | int_x2 b1 = (int_x2)y(high(segment1)) - (int_x2)y(low(segment1)); | |
312 | int_x2 a2 = (int_x2)x(high(segment2)) - (int_x2)x(low(segment2)); | |
313 | int_x2 b2 = (int_x2)y(high(segment2)) - (int_x2)y(low(segment2)); | |
314 | ||
315 | int sign1 = 0; | |
316 | int sign2 = 0; | |
317 | if (a1 && b2) | |
318 | sign1 = ((a1 > 0) ^ (b2 > 0)) ? -1 : 1; | |
319 | if (a2 && b1) | |
320 | sign2 = ((a2 > 0) ^ (b1 > 0)) ? -1 : 1; | |
321 | ||
322 | if (sign1 != sign2) | |
323 | return (sign1 < sign2) ? -1 : 1; | |
324 | uint_x2 a3 = (uint_x2)(a1 < 0 ? -a1 : a1) * (uint_x2)(b2 < 0 ? -b2 : b2); | |
325 | uint_x2 b3 = (uint_x2)(b1 < 0 ? -b1 : b1) * (uint_x2)(a2 < 0 ? -a2 : a2); | |
326 | if (a3 == b3) | |
327 | return 0; | |
328 | return ((a3 < b3) ^ (sign1 == 1)) ? 1 : -1; | |
329 | } | |
330 | ||
331 | struct y_s_orientation2 : gtl_yes {}; | |
332 | ||
333 | // -1 for right, 0 for collinear and 1 for left. | |
334 | template <typename Segment, typename Point> | |
335 | typename enable_if< | |
336 | typename gtl_and_3< | |
337 | y_s_orientation2, | |
338 | typename is_segment_concept< | |
339 | typename geometry_concept<Segment>::type | |
340 | >::type, | |
341 | typename is_point_concept< | |
342 | typename geometry_concept<Point>::type | |
343 | >::type | |
344 | >::type, | |
345 | int>::type orientation(const Segment& segment, const Point& point) { | |
346 | Segment segment2 = construct<Segment>(high(segment), point); | |
347 | return orientation(segment, segment2); | |
348 | } | |
349 | ||
350 | struct y_s_contains : gtl_yes {}; | |
351 | ||
352 | template <typename Segment, typename Point> | |
353 | typename enable_if< | |
354 | typename gtl_and_3< | |
355 | y_s_contains, | |
356 | typename is_segment_concept< | |
357 | typename geometry_concept<Segment>::type | |
358 | >::type, | |
359 | typename is_point_concept< | |
360 | typename geometry_concept<Point>::type | |
361 | >::type | |
362 | >::type, | |
363 | bool>::type contains(const Segment& segment, | |
364 | const Point& point, bool consider_touch = true ) { | |
365 | if (orientation(segment, point)) | |
366 | return false; | |
367 | rectangle_data<typename segment_coordinate_type<Segment>::type> rect; | |
368 | set_points(rect, low(segment), high(segment)); | |
369 | if (!contains(rect, point, true)) | |
370 | return false; | |
371 | if (!consider_touch && | |
372 | (equivalence(low(segment), point) || | |
373 | equivalence(high(segment), point))) | |
374 | return false; | |
375 | return true; | |
376 | } | |
377 | ||
378 | struct y_s_contains2 : gtl_yes {}; | |
379 | ||
380 | template <typename Segment1, typename Segment2> | |
381 | typename enable_if< | |
382 | typename gtl_and_3< | |
383 | y_s_contains2, | |
384 | typename is_segment_concept< | |
385 | typename geometry_concept<Segment1>::type | |
386 | >::type, | |
387 | typename is_segment_concept< | |
388 | typename geometry_concept<Segment2>::type | |
389 | >::type | |
390 | >::type, | |
391 | bool>::type contains(const Segment1& segment1, | |
392 | const Segment2& segment2, bool consider_touch = true) { | |
393 | return contains(segment1, get(segment2, LOW), consider_touch) && | |
394 | contains(segment1, get(segment2, HIGH), consider_touch); | |
395 | } | |
396 | ||
397 | struct y_s_length : gtl_yes {}; | |
398 | ||
399 | template <typename Segment> | |
400 | typename enable_if< | |
401 | typename gtl_and< | |
402 | y_s_length, | |
403 | typename is_segment_concept< | |
404 | typename geometry_concept<Segment>::type | |
405 | >::type | |
406 | >::type, | |
407 | typename segment_distance_type<Segment>::type>::type | |
408 | length(const Segment& segment) { | |
409 | return euclidean_distance(low(segment), high(segment)); | |
410 | } | |
411 | ||
412 | struct y_s_scale_up : gtl_yes {}; | |
413 | ||
414 | template <typename Segment> | |
415 | typename enable_if< | |
416 | typename gtl_and< | |
417 | y_s_scale_up, | |
418 | typename is_mutable_segment_concept< | |
419 | typename geometry_concept<Segment>::type | |
420 | >::type | |
421 | >::type, | |
422 | Segment>::type& scale_up(Segment& segment, | |
423 | typename coordinate_traits< | |
424 | typename segment_coordinate_type<Segment>::type | |
425 | >::unsigned_area_type factor) { | |
426 | typename segment_point_type<Segment>::type l = low(segment); | |
427 | typename segment_point_type<Segment>::type h = high(segment); | |
428 | low(segment, scale_up(l, factor)); | |
429 | high(segment, scale_up(h, factor)); | |
430 | return segment; | |
431 | } | |
432 | ||
433 | struct y_s_scale_down : gtl_yes {}; | |
434 | ||
435 | template <typename Segment> | |
436 | typename enable_if< | |
437 | typename gtl_and< | |
438 | y_s_scale_down, | |
439 | typename is_mutable_segment_concept< | |
440 | typename geometry_concept<Segment>::type | |
441 | >::type | |
442 | >::type, | |
443 | Segment>::type& scale_down(Segment& segment, | |
444 | typename coordinate_traits< | |
445 | typename segment_coordinate_type<Segment>::type | |
446 | >::unsigned_area_type factor) { | |
447 | typename segment_point_type<Segment>::type l = low(segment); | |
448 | typename segment_point_type<Segment>::type h = high(segment); | |
449 | low(segment, scale_down(l, factor)); | |
450 | high(segment, scale_down(h, factor)); | |
451 | return segment; | |
452 | } | |
453 | ||
454 | struct y_s_scale : gtl_yes {}; | |
455 | ||
456 | template <typename Segment, typename Scale> | |
457 | typename enable_if< | |
458 | typename gtl_and< | |
459 | y_s_scale, | |
460 | typename is_mutable_segment_concept< | |
461 | typename geometry_concept<Segment>::type | |
462 | >::type | |
463 | >::type, | |
464 | Segment>::type& scale(Segment& segment, const Scale& sc) { | |
465 | typename segment_point_type<Segment>::type l = low(segment); | |
466 | typename segment_point_type<Segment>::type h = high(segment); | |
467 | low(segment, scale(l, sc)); | |
468 | high(segment, scale(h, sc)); | |
469 | return segment; | |
470 | } | |
471 | ||
472 | struct y_s_transform : gtl_yes {}; | |
473 | ||
474 | template <typename Segment, typename Transform> | |
475 | typename enable_if< | |
476 | typename gtl_and< | |
477 | y_s_transform, | |
478 | typename is_mutable_segment_concept< | |
479 | typename geometry_concept<Segment>::type | |
480 | >::type | |
481 | >::type, | |
482 | Segment>::type& transform(Segment& segment, const Transform& tr) { | |
483 | typename segment_point_type<Segment>::type l = low(segment); | |
484 | typename segment_point_type<Segment>::type h = high(segment); | |
485 | low(segment, transform(l, tr)); | |
486 | high(segment, transform(h, tr)); | |
487 | return segment; | |
488 | } | |
489 | ||
490 | struct y_s_move : gtl_yes {}; | |
491 | ||
492 | template <typename Segment> | |
493 | typename enable_if< | |
494 | typename gtl_and< | |
495 | y_s_move, | |
496 | typename is_mutable_segment_concept< | |
497 | typename geometry_concept<Segment>::type | |
498 | >::type | |
499 | >::type, | |
500 | Segment>::type& move(Segment& segment, orientation_2d orient, | |
501 | typename segment_coordinate_type<Segment>::type displacement) { | |
502 | typename segment_point_type<Segment>::type l = low(segment); | |
503 | typename segment_point_type<Segment>::type h = high(segment); | |
504 | low(segment, move(l, orient, displacement)); | |
505 | high(segment, move(h, orient, displacement)); | |
506 | return segment; | |
507 | } | |
508 | ||
509 | struct y_s_convolve : gtl_yes {}; | |
510 | ||
511 | template <typename Segment, typename Point> | |
512 | typename enable_if< | |
513 | typename gtl_and_3< | |
514 | y_s_convolve, | |
515 | typename is_mutable_segment_concept< | |
516 | typename geometry_concept<Segment>::type | |
517 | >::type, | |
518 | typename is_point_concept< | |
519 | typename geometry_concept<Point>::type | |
520 | >::type | |
521 | >::type, | |
522 | Segment>::type& convolve(Segment& segment, const Point& point) { | |
523 | typename segment_point_type<Segment>::type l = low(segment); | |
524 | typename segment_point_type<Segment>::type h = high(segment); | |
525 | low(segment, convolve(l, point)); | |
526 | high(segment, convolve(h, point)); | |
527 | return segment; | |
528 | } | |
529 | ||
530 | struct y_s_deconvolve : gtl_yes {}; | |
531 | ||
532 | template <typename Segment, typename Point> | |
533 | typename enable_if< | |
534 | typename gtl_and_3< | |
535 | y_s_deconvolve, | |
536 | typename is_mutable_segment_concept< | |
537 | typename geometry_concept<Segment>::type | |
538 | >::type, | |
539 | typename is_point_concept< | |
540 | typename geometry_concept<Point>::type | |
541 | >::type | |
542 | >::type, | |
543 | Segment>::type& deconvolve(Segment& segment, const Point& point) { | |
544 | typename segment_point_type<Segment>::type l = low(segment); | |
545 | typename segment_point_type<Segment>::type h = high(segment); | |
546 | low(segment, deconvolve(l, point)); | |
547 | high(segment, deconvolve(h, point)); | |
548 | return segment; | |
549 | } | |
550 | ||
551 | struct y_s_abuts1 : gtl_yes {}; | |
552 | ||
553 | template <typename Segment1, typename Segment2> | |
554 | typename enable_if< | |
555 | typename gtl_and_3< | |
556 | y_s_abuts1, | |
557 | typename is_segment_concept< | |
558 | typename geometry_concept<Segment1>::type | |
559 | >::type, | |
560 | typename is_segment_concept< | |
561 | typename geometry_concept<Segment2>::type | |
562 | >::type | |
563 | >::type, | |
564 | bool>::type abuts(const Segment1& segment1, | |
565 | const Segment2& segment2, direction_1d dir) { | |
566 | return dir.to_int() ? equivalence(low(segment2) , high(segment1)) : | |
567 | equivalence(low(segment1) , high(segment2)); | |
568 | } | |
569 | ||
570 | struct y_s_abuts2 : gtl_yes {}; | |
571 | ||
572 | template <typename Segment1, typename Segment2> | |
573 | typename enable_if< | |
574 | typename gtl_and_3< | |
575 | y_s_abuts2, | |
576 | typename is_segment_concept< | |
577 | typename geometry_concept<Segment1>::type | |
578 | >::type, | |
579 | typename is_segment_concept< | |
580 | typename geometry_concept<Segment2>::type | |
581 | >::type | |
582 | >::type, | |
583 | bool>::type abuts(const Segment1& segment1, const Segment2& segment2) { | |
584 | return abuts(segment1, segment2, HIGH) || abuts(segment1, segment2, LOW); | |
585 | } | |
586 | ||
587 | struct y_s_e_intersects : gtl_yes {}; | |
588 | ||
589 | template <typename Segment1, typename Segment2> | |
590 | typename enable_if< | |
591 | typename gtl_and_3< | |
592 | y_s_e_intersects, | |
593 | typename is_segment_concept< | |
594 | typename geometry_concept<Segment1>::type | |
595 | >::type, | |
596 | typename is_segment_concept< | |
597 | typename geometry_concept<Segment2>::type | |
598 | >::type | |
599 | >::type, | |
600 | bool | |
601 | >::type intersects(const Segment1& segment1, const Segment2& segment2, | |
602 | bool consider_touch = true) { | |
603 | rectangle_data<typename segment_coordinate_type<Segment1>::type> rect1, rect2; | |
604 | set_points(rect1, low(segment1), high(segment1)); | |
605 | set_points(rect2, low(segment2), high(segment2)); | |
606 | // Check if axis-parallel rectangles containing segments intersect. | |
607 | if (!intersects(rect1, rect2, true)) | |
608 | return false; | |
609 | int or1_1 = orientation(segment1, low(segment2)); | |
610 | int or1_2 = orientation(segment1, high(segment2)); | |
611 | if (or1_1 * or1_2 > 0) | |
612 | return false; | |
613 | int or2_1 = orientation(segment2, low(segment1)); | |
614 | int or2_2 = orientation(segment2, high(segment1)); | |
615 | if (or2_1 * or2_2 > 0) | |
616 | return false; | |
617 | if (consider_touch || (or1_1 && or1_2) || (or2_1 && or2_2)) | |
618 | return true; | |
619 | if (or1_1 || or1_2) | |
620 | return false; | |
621 | return intersects(vertical(rect1), vertical(rect2), false) || | |
622 | intersects(horizontal(rect1), horizontal(rect2), false); | |
623 | } | |
624 | ||
625 | struct y_s_e_dist : gtl_yes {}; | |
626 | ||
627 | template <typename Segment, typename Point> | |
628 | typename enable_if< | |
629 | typename gtl_and_3< | |
630 | y_s_e_dist, | |
631 | typename is_segment_concept< | |
632 | typename geometry_concept<Segment>::type | |
633 | >::type, | |
634 | typename is_point_concept< | |
635 | typename geometry_concept<Point>::type | |
636 | >::type | |
637 | >::type, | |
638 | typename segment_distance_type<Segment>::type>::type | |
639 | euclidean_distance(const Segment& segment, const Point& point) { | |
640 | typedef typename segment_distance_type<Segment>::type Unit; | |
641 | Unit x1 = x(low(segment)); | |
642 | Unit y1 = y(low(segment)); | |
643 | Unit x2 = x(high(segment)); | |
644 | Unit y2 = y(high(segment)); | |
645 | Unit X = x(point); | |
646 | Unit Y = y(point); | |
647 | Unit A = X - x1; | |
648 | Unit B = Y - y1; | |
649 | Unit C = x2 - x1; | |
650 | Unit D = y2 - y1; | |
651 | Unit param = (A * C + B * D); | |
652 | Unit length_sq = C * C + D * D; | |
653 | if (param > length_sq) { | |
654 | return euclidean_distance(high(segment), point); | |
655 | } else if (param < 0.0) { | |
656 | return euclidean_distance(low(segment), point); | |
657 | } | |
658 | if (length_sq == 0.0) | |
659 | return 0.0; | |
660 | Unit denom = std::sqrt(length_sq); | |
661 | Unit result = (A * D - C * B) / denom; | |
662 | return (result < 0.0) ? -result : result; | |
663 | } | |
664 | ||
665 | struct y_s_e_dist2 : gtl_yes {}; | |
666 | ||
667 | template <typename Segment1, typename Segment2> | |
668 | typename enable_if< | |
669 | typename gtl_and_3< | |
670 | y_s_e_dist2, | |
671 | typename is_segment_concept< | |
672 | typename geometry_concept<Segment1>::type | |
673 | >::type, | |
674 | typename is_segment_concept< | |
675 | typename geometry_concept<Segment2>::type | |
676 | >::type | |
677 | >::type, | |
678 | typename segment_distance_type<Segment1>::type>::type | |
679 | euclidean_distance(const Segment1& segment1, const Segment2& segment2) { | |
680 | if (intersects(segment1, segment2)) | |
681 | return 0.0; | |
682 | typename segment_distance_type<Segment1>::type | |
683 | result1 = euclidean_distance(segment1, low(segment2)), | |
684 | result2 = euclidean_distance(segment1, high(segment2)), | |
685 | result3 = euclidean_distance(segment2, low(segment1)), | |
686 | result4 = euclidean_distance(segment2, high(segment1)); | |
687 | if (result2 < result1) | |
688 | result1 = result2; | |
689 | if (result4 < result3) | |
690 | result3 = result4; | |
691 | return (result1 < result3) ? result1 : result3; | |
692 | } | |
693 | } // polygon | |
694 | } // boost | |
695 | ||
696 | #endif // BOOST_POLYGON_SEGMENT_CONCEPT_HPP |