Mercurial > hg > vamp-build-and-test

comparison DEPENDENCIES/generic/include/boost/polygon/segment_concept.hpp @ 16:2665513ce2d3

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Add boost headers
author Chris Cannam
date Tue, 05 Aug 2014 11:11:38 +0100
parents
children
comparison
equal deleted inserted replaced
15:663ca0da4350 16:2665513ce2d3
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