]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
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 |