1 #pragma once
2
3 #include <mapbox/geojsonvt/types.hpp>
4
5 namespace mapbox {
6 namespace geojsonvt {
7 namespace detail {
8
9 template <uint8_t I>
10 class clipper {
11 public:
12 const double k1;
13 const double k2;
14
operator ()(const vt_point & point) const15 vt_geometry operator()(const vt_point& point) const {
16 return point;
17 }
18
operator ()(const vt_multi_point & points) const19 vt_geometry operator()(const vt_multi_point& points) const {
20 vt_multi_point part;
21 for (const auto& p : points) {
22 const double ak = get<I>(p);
23 if (ak >= k1 && ak <= k2)
24 part.push_back(p);
25 }
26 return part;
27 }
28
operator ()(const vt_line_string & line) const29 vt_geometry operator()(const vt_line_string& line) const {
30 vt_multi_line_string parts;
31 clipLine(line, parts);
32 if (parts.size() == 1)
33 return parts[0];
34 else
35 return parts;
36 }
37
operator ()(const vt_multi_line_string & lines) const38 vt_geometry operator()(const vt_multi_line_string& lines) const {
39 vt_multi_line_string parts;
40 for (const auto& line : lines) {
41 clipLine(line, parts);
42 }
43 if (parts.size() == 1)
44 return parts[0];
45 else
46 return parts;
47 }
48
operator ()(const vt_polygon & polygon) const49 vt_geometry operator()(const vt_polygon& polygon) const {
50 vt_polygon result;
51 for (const auto& ring : polygon) {
52 const auto new_ring = clipRing(ring);
53 if (!new_ring.empty())
54 result.push_back(new_ring);
55 }
56 return result;
57 }
58
operator ()(const vt_multi_polygon & polygons) const59 vt_geometry operator()(const vt_multi_polygon& polygons) const {
60 vt_multi_polygon result;
61 for (const auto& polygon : polygons) {
62 vt_polygon p;
63 for (const auto& ring : polygon) {
64 const auto new_ring = clipRing(ring);
65 if (!new_ring.empty())
66 p.push_back(new_ring);
67 }
68 if (!p.empty())
69 result.push_back(p);
70 }
71 return result;
72 }
73
operator ()(const vt_geometry_collection & geometries) const74 vt_geometry operator()(const vt_geometry_collection& geometries) const {
75 vt_geometry_collection result;
76 for (const auto& geometry : geometries) {
77 vt_geometry::visit(geometry,
78 [&](const auto& g) { result.push_back(this->operator()(g)); });
79 }
80 return result;
81 }
82
83 private:
newSlice(vt_multi_line_string & parts,vt_line_string & slice,double dist) const84 vt_line_string newSlice(vt_multi_line_string& parts, vt_line_string& slice, double dist) const {
85 if (!slice.empty()) {
86 slice.dist = dist;
87 parts.push_back(std::move(slice));
88 }
89 return {};
90 }
91
clipLine(const vt_line_string & line,vt_multi_line_string & slices) const92 void clipLine(const vt_line_string& line, vt_multi_line_string& slices) const {
93
94 const double dist = line.dist;
95 const size_t len = line.size();
96
97 if (len < 2)
98 return;
99
100 vt_line_string slice;
101
102 for (size_t i = 0; i < (len - 1); ++i) {
103 const auto& a = line[i];
104 const auto& b = line[i + 1];
105 const double ak = get<I>(a);
106 const double bk = get<I>(b);
107
108 if (ak < k1) {
109 if (bk > k2) { // ---|-----|-->
110 slice.push_back(intersect<I>(a, b, k1));
111 slice.push_back(intersect<I>(a, b, k2));
112 slice = newSlice(slices, slice, dist);
113
114 } else if (bk >= k1) { // ---|--> |
115 slice.push_back(intersect<I>(a, b, k1));
116 if (i == len - 2)
117 slice.push_back(b); // last point
118 }
119 } else if (ak >= k2) {
120 if (bk < k1) { // <--|-----|---
121 slice.push_back(intersect<I>(a, b, k2));
122 slice.push_back(intersect<I>(a, b, k1));
123 slice = newSlice(slices, slice, dist);
124
125 } else if (bk < k2) { // | <--|---
126 slice.push_back(intersect<I>(a, b, k2));
127 if (i == len - 2)
128 slice.push_back(b); // last point
129 }
130 } else {
131 slice.push_back(a);
132
133 if (bk < k1) { // <--|--- |
134 slice.push_back(intersect<I>(a, b, k1));
135 slice = newSlice(slices, slice, dist);
136
137 } else if (bk > k2) { // | ---|-->
138 slice.push_back(intersect<I>(a, b, k2));
139 slice = newSlice(slices, slice, dist);
140
141 } else if (i == len - 2) { // | --> |
142 slice.push_back(b);
143 }
144 }
145 }
146
147 // add the final slice
148 newSlice(slices, slice, dist);
149 }
150
clipRing(const vt_linear_ring & ring) const151 vt_linear_ring clipRing(const vt_linear_ring& ring) const {
152 const size_t len = ring.size();
153
154 vt_linear_ring slice;
155 slice.area = ring.area;
156
157 if (len < 2)
158 return slice;
159
160 for (size_t i = 0; i < (len - 1); ++i) {
161 const auto& a = ring[i];
162 const auto& b = ring[i + 1];
163 const double ak = get<I>(a);
164 const double bk = get<I>(b);
165
166 if (ak < k1) {
167 if (bk >= k1) {
168 slice.push_back(intersect<I>(a, b, k1)); // ---|--> |
169 if (bk > k2) // ---|-----|-->
170 slice.push_back(intersect<I>(a, b, k2));
171 else if (i == len - 2)
172 slice.push_back(b); // last point
173 }
174 } else if (ak >= k2) {
175 if (bk < k2) { // | <--|---
176 slice.push_back(intersect<I>(a, b, k2));
177 if (bk < k1) // <--|-----|---
178 slice.push_back(intersect<I>(a, b, k1));
179 else if (i == len - 2)
180 slice.push_back(b); // last point
181 }
182 } else {
183 slice.push_back(a);
184 if (bk < k1) // <--|--- |
185 slice.push_back(intersect<I>(a, b, k1));
186 else if (bk > k2) // | ---|-->
187 slice.push_back(intersect<I>(a, b, k2));
188 // | --> |
189 }
190 }
191
192 // close the polygon if its endpoints are not the same after clipping
193 if (!slice.empty()) {
194 const auto& first = slice.front();
195 const auto& last = slice.back();
196 if (first != last) {
197 slice.push_back(first);
198 }
199 }
200
201 return slice;
202 }
203 };
204
205 /* clip features between two axis-parallel lines:
206 * | |
207 * ___|___ | /
208 * / | \____|____/
209 * | |
210 */
211
212 template <uint8_t I>
clip(const vt_features & features,const double k1,const double k2,const double minAll,const double maxAll)213 inline vt_features clip(const vt_features& features,
214 const double k1,
215 const double k2,
216 const double minAll,
217 const double maxAll) {
218
219 if (minAll >= k1 && maxAll < k2) // trivial accept
220 return features;
221
222 if (maxAll < k1 || minAll >= k2) // trivial reject
223 return {};
224
225 vt_features clipped;
226
227 for (const auto& feature : features) {
228 const auto& geom = feature.geometry;
229 const auto& props = feature.properties;
230 const auto& id = feature.id;
231
232 const double min = get<I>(feature.bbox.min);
233 const double max = get<I>(feature.bbox.max);
234
235 if (min >= k1 && max < k2) { // trivial accept
236 clipped.push_back(feature);
237
238 } else if (max < k1 || min >= k2) { // trivial reject
239 continue;
240
241 } else {
242 clipped.emplace_back(vt_geometry::visit(geom, clipper<I>{ k1, k2 }), props, id);
243 }
244 }
245
246 return clipped;
247 }
248
249 } // namespace detail
250 } // namespace geojsonvt
251 } // namespace mapbox
252