1 /*
2   Copyright 2012 Lucanus Simonson
3 
4   Use, modification and distribution are subject to the Boost Software License,
5   Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
6   http://www.boost.org/LICENSE_1_0.txt).
7 */
8 
9 #ifndef BOOST_POLYGON_SEGMENT_UTILS_HPP
10 #define BOOST_POLYGON_SEGMENT_UTILS_HPP
11 
12 #include <iterator>
13 #include <set>
14 #include <vector>
15 
16 #include "detail/scan_arbitrary.hpp"
17 #include "isotropy.hpp"
18 #include "rectangle_concept.hpp"
19 #include "segment_concept.hpp"
20 
21 namespace boost {
22 namespace polygon {
23 
24 template <typename Segment, typename SegmentIterator>
25 typename enable_if<
26   typename gtl_and<
27     typename gtl_if<
28       typename is_segment_concept<
29         typename geometry_concept<
30           typename std::iterator_traits<SegmentIterator>::value_type
31         >::type
32       >::type
33     >::type,
34     typename gtl_if<
35       typename is_segment_concept<
36         typename geometry_concept<Segment>::type
37       >::type
38     >::type
39   >::type,
40   void
41 >::type
intersect_segments(std::vector<std::pair<std::size_t,Segment>> & result,SegmentIterator first,SegmentIterator last)42 intersect_segments(
43     std::vector<std::pair<std::size_t, Segment> >& result,
44     SegmentIterator first, SegmentIterator last) {
45   typedef typename segment_traits<Segment>::coordinate_type Unit;
46   typedef typename scanline_base<Unit>::Point Point;
47   typedef typename scanline_base<Unit>::half_edge half_edge;
48   typedef int segment_id;
49   std::vector<std::pair<half_edge, segment_id> > half_edges;
50   std::vector<std::pair<half_edge, segment_id> > half_edges_out;
51   segment_id id_in = 0;
52   half_edges.reserve(std::distance(first, last));
53   for (; first != last; ++first) {
54     Point l, h;
55     assign(l, low(*first));
56     assign(h, high(*first));
57     half_edges.push_back(std::make_pair(half_edge(l, h), id_in++));
58   }
59   half_edges_out.reserve(half_edges.size());
60   // Apparently no need to pre-sort data when calling validate_scan.
61   if (half_edges.size() != 0) {
62     line_intersection<Unit>::validate_scan(
63         half_edges_out, half_edges.begin(), half_edges.end());
64   }
65 
66   result.reserve(result.size() + half_edges_out.size());
67   for (std::size_t i = 0; i < half_edges_out.size(); ++i) {
68     std::size_t id = (std::size_t)(half_edges_out[i].second);
69     Point l = half_edges_out[i].first.first;
70     Point h = half_edges_out[i].first.second;
71     result.push_back(std::make_pair(id, construct<Segment>(l, h)));
72   }
73 }
74 
75 template <typename SegmentContainer, typename SegmentIterator>
76 typename enable_if<
77   typename gtl_and<
78     typename gtl_if<
79       typename is_segment_concept<
80         typename geometry_concept<
81           typename std::iterator_traits<SegmentIterator>::value_type
82         >::type
83       >::type
84     >::type,
85     typename gtl_if<
86       typename is_segment_concept<
87         typename geometry_concept<
88           typename SegmentContainer::value_type
89         >::type
90       >::type
91     >::type
92   >::type,
93   void
94 >::type
intersect_segments(SegmentContainer & result,SegmentIterator first,SegmentIterator last)95 intersect_segments(
96     SegmentContainer& result,
97     SegmentIterator first,
98     SegmentIterator last) {
99   typedef typename SegmentContainer::value_type segment_type;
100   typedef typename segment_traits<segment_type>::coordinate_type Unit;
101   typedef typename scanline_base<Unit>::Point Point;
102   typedef typename scanline_base<Unit>::half_edge half_edge;
103   typedef int segment_id;
104   std::vector<std::pair<half_edge, segment_id> > half_edges;
105   std::vector<std::pair<half_edge, segment_id> > half_edges_out;
106   segment_id id_in = 0;
107   half_edges.reserve(std::distance(first, last));
108   for (; first != last; ++first) {
109     Point l, h;
110     assign(l, low(*first));
111     assign(h, high(*first));
112     half_edges.push_back(std::make_pair(half_edge(l, h), id_in++));
113   }
114   half_edges_out.reserve(half_edges.size());
115   // Apparently no need to pre-sort data when calling validate_scan.
116   if (half_edges.size() != 0) {
117     line_intersection<Unit>::validate_scan(
118         half_edges_out, half_edges.begin(), half_edges.end());
119   }
120 
121   result.reserve(result.size() + half_edges_out.size());
122   for (std::size_t i = 0; i < half_edges_out.size(); ++i) {
123     Point l = half_edges_out[i].first.first;
124     Point h = half_edges_out[i].first.second;
125     result.push_back(construct<segment_type>(l, h));
126   }
127 }
128 
129 template <typename Rectangle, typename SegmentIterator>
130 typename enable_if<
131   typename gtl_and<
132     typename gtl_if<
133       typename is_rectangle_concept<
134         typename geometry_concept<Rectangle>::type
135       >::type
136     >::type,
137     typename gtl_if<
138       typename is_segment_concept<
139         typename geometry_concept<
140           typename std::iterator_traits<SegmentIterator>::value_type
141         >::type
142       >::type
143     >::type
144   >::type,
145   bool
146 >::type
envelope_segments(Rectangle & rect,SegmentIterator first,SegmentIterator last)147 envelope_segments(
148     Rectangle& rect,
149     SegmentIterator first,
150     SegmentIterator last) {
151   for (SegmentIterator it = first; it != last; ++it) {
152     if (it == first) {
153       set_points(rect, low(*it), high(*it));
154     } else {
155       encompass(rect, low(*it));
156       encompass(rect, high(*it));
157     }
158   }
159   return first != last;
160 }
161 }  // polygon
162 }  // boost
163 
164 #endif  // BOOST_POLYGON_SEGMENT_UTILS_HPP
165