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 |
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 |
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 |
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 | |