1 #pragma once
2
3 #include <mapbox/geometry/wagyu/edge.hpp>
4 #include <mapbox/geometry/wagyu/local_minimum.hpp>
5
6 #include <algorithm>
7
8 #ifdef DEBUG
9 #include <stdexcept>
10 #endif
11
12 namespace mapbox {
13 namespace geometry {
14 namespace wagyu {
15
16 template <typename T>
reverse_horizontal(edge<T> & e)17 inline void reverse_horizontal(edge<T>& e) {
18 // swap horizontal edges' top and bottom x's so they follow the natural
19 // progression of the bounds - ie so their xbots will align with the
20 // adjoining lower edge. [Helpful in the process_horizontal() method.]
21 std::swap(e.top.x, e.bot.x);
22 }
23
24 // Make a list start on a local maximum by
25 // shifting all the points not on a local maximum to the
26 template <typename T>
start_list_on_local_maximum(edge_list<T> & edges)27 void start_list_on_local_maximum(edge_list<T>& edges) {
28 if (edges.size() <= 2) {
29 return;
30 }
31 // Find the first local maximum going forward in the list
32 auto prev_edge = edges.end();
33 --prev_edge;
34 bool prev_edge_is_horizontal = is_horizontal(*prev_edge);
35 auto edge = edges.begin();
36 bool edge_is_horizontal;
37 bool y_decreasing_before_last_horizontal = false; // assume false at start
38
39 while (edge != edges.end()) {
40 edge_is_horizontal = is_horizontal(*edge);
41 if ((!prev_edge_is_horizontal && !edge_is_horizontal && edge->top == prev_edge->top)) {
42 break;
43 }
44 if (!edge_is_horizontal && prev_edge_is_horizontal) {
45 if (y_decreasing_before_last_horizontal &&
46 (edge->top == prev_edge->bot || edge->top == prev_edge->top)) {
47 break;
48 }
49 } else if (!y_decreasing_before_last_horizontal && !prev_edge_is_horizontal &&
50 edge_is_horizontal &&
51 (prev_edge->top == edge->top || prev_edge->top == edge->bot)) {
52 y_decreasing_before_last_horizontal = true;
53 }
54 prev_edge_is_horizontal = edge_is_horizontal;
55 prev_edge = edge;
56 ++edge;
57 }
58 std::rotate(edges.begin(), edge, edges.end());
59 }
60
61 template <typename T>
create_bound_towards_minimum(edge_list<T> & edges)62 bound<T> create_bound_towards_minimum(edge_list<T>& edges) {
63 if (edges.size() == 1) {
64 if (is_horizontal(edges.front())) {
65 reverse_horizontal(edges.front());
66 }
67 bound<T> bnd;
68 std::swap(bnd.edges, edges);
69 return bnd;
70 }
71 auto next_edge = edges.begin();
72 auto edge = next_edge;
73 ++next_edge;
74 bool edge_is_horizontal = is_horizontal(*edge);
75 if (edge_is_horizontal) {
76 reverse_horizontal(*edge);
77 }
78 bool next_edge_is_horizontal;
79 bool y_increasing_before_last_horizontal = false; // assume false at start
80
81 while (next_edge != edges.end()) {
82 next_edge_is_horizontal = is_horizontal(*next_edge);
83 if ((!next_edge_is_horizontal && !edge_is_horizontal && edge->bot == next_edge->bot)) {
84 break;
85 }
86 if (!next_edge_is_horizontal && edge_is_horizontal) {
87 if (y_increasing_before_last_horizontal &&
88 (next_edge->bot == edge->bot || next_edge->bot == edge->top)) {
89 break;
90 }
91 } else if (!y_increasing_before_last_horizontal && !edge_is_horizontal &&
92 next_edge_is_horizontal &&
93 (edge->bot == next_edge->top || edge->bot == next_edge->bot)) {
94 y_increasing_before_last_horizontal = true;
95 }
96 edge_is_horizontal = next_edge_is_horizontal;
97 edge = next_edge;
98 if (edge_is_horizontal) {
99 reverse_horizontal(*edge);
100 }
101 ++next_edge;
102 }
103 bound<T> bnd;
104 if (next_edge == edges.end()) {
105 std::swap(edges, bnd.edges);
106 } else {
107 bnd.edges.reserve(static_cast<std::size_t>(std::distance(edges.begin(), next_edge)));
108 std::move(edges.begin(), next_edge, std::back_inserter(bnd.edges));
109 edges.erase(edges.begin(), next_edge);
110 }
111 std::reverse(bnd.edges.begin(), bnd.edges.end());
112 return bnd;
113 }
114
115 template <typename T>
create_bound_towards_maximum(edge_list<T> & edges)116 bound<T> create_bound_towards_maximum(edge_list<T>& edges) {
117 if (edges.size() == 1) {
118 bound<T> bnd;
119 std::swap(bnd.edges, edges);
120 return bnd;
121 }
122 auto next_edge = edges.begin();
123 auto edge = next_edge;
124 ++next_edge;
125 bool edge_is_horizontal = is_horizontal(*edge);
126 bool next_edge_is_horizontal;
127 bool y_decreasing_before_last_horizontal = false; // assume false at start
128
129 while (next_edge != edges.end()) {
130 next_edge_is_horizontal = is_horizontal(*next_edge);
131 if ((!next_edge_is_horizontal && !edge_is_horizontal && edge->top == next_edge->top)) {
132 break;
133 }
134 if (!next_edge_is_horizontal && edge_is_horizontal) {
135 if (y_decreasing_before_last_horizontal &&
136 (next_edge->top == edge->bot || next_edge->top == edge->top)) {
137 break;
138 }
139 } else if (!y_decreasing_before_last_horizontal && !edge_is_horizontal &&
140 next_edge_is_horizontal &&
141 (edge->top == next_edge->top || edge->top == next_edge->bot)) {
142 y_decreasing_before_last_horizontal = true;
143 }
144 edge_is_horizontal = next_edge_is_horizontal;
145 edge = next_edge;
146 ++next_edge;
147 }
148 bound<T> bnd;
149 if (next_edge == edges.end()) {
150 std::swap(bnd.edges, edges);
151 } else {
152 bnd.edges.reserve(static_cast<std::size_t>(std::distance(edges.begin(), next_edge)));
153 std::move(edges.begin(), next_edge, std::back_inserter(bnd.edges));
154 edges.erase(edges.begin(), next_edge);
155 }
156 return bnd;
157 }
158
159 template <typename T>
fix_horizontals(bound<T> & bnd)160 void fix_horizontals(bound<T>& bnd) {
161
162 auto edge_itr = bnd.edges.begin();
163 auto next_itr = std::next(edge_itr);
164 if (next_itr == bnd.edges.end()) {
165 return;
166 }
167 if (is_horizontal(*edge_itr) && next_itr->bot != edge_itr->top) {
168 reverse_horizontal(*edge_itr);
169 }
170 auto prev_itr = edge_itr++;
171 while (edge_itr != bnd.edges.end()) {
172 if (is_horizontal(*edge_itr) && prev_itr->top != edge_itr->bot) {
173 reverse_horizontal(*edge_itr);
174 }
175 prev_itr = edge_itr;
176 ++edge_itr;
177 }
178 }
179
180 template <typename T>
move_horizontals_on_left_to_right(bound<T> & left_bound,bound<T> & right_bound)181 void move_horizontals_on_left_to_right(bound<T>& left_bound, bound<T>& right_bound) {
182 // We want all the horizontal segments that are at the same Y as the minimum to be on the right
183 // bound
184 auto edge_itr = left_bound.edges.begin();
185 while (edge_itr != left_bound.edges.end()) {
186 if (!is_horizontal(*edge_itr)) {
187 break;
188 }
189 reverse_horizontal(*edge_itr);
190 ++edge_itr;
191 }
192 if (edge_itr == left_bound.edges.begin()) {
193 return;
194 }
195 std::reverse(left_bound.edges.begin(), edge_itr);
196 auto dist = std::distance(left_bound.edges.begin(), edge_itr);
197 std::move(left_bound.edges.begin(), edge_itr, std::back_inserter(right_bound.edges));
198 left_bound.edges.erase(left_bound.edges.begin(), edge_itr);
199 std::rotate(right_bound.edges.begin(), std::prev(right_bound.edges.end(), dist),
200 right_bound.edges.end());
201 }
202
203 template <typename T>
add_ring_to_local_minima_list(edge_list<T> & edges,local_minimum_list<T> & minima_list,polygon_type poly_type)204 void add_ring_to_local_minima_list(edge_list<T>& edges,
205 local_minimum_list<T>& minima_list,
206 polygon_type poly_type) {
207
208 if (edges.empty()) {
209 return;
210 }
211 // Adjust the order of the ring so we start on a local maximum
212 // therefore we start right away on a bound.
213 start_list_on_local_maximum(edges);
214
215 bound_ptr<T> first_minimum = nullptr;
216 bound_ptr<T> last_maximum = nullptr;
217 while (!edges.empty()) {
218 bool lm_minimum_has_horizontal = false;
219 auto to_minimum = create_bound_towards_minimum(edges);
220 if (edges.empty()) {
221 throw std::runtime_error("Edges is empty after only creating a single bound.");
222 }
223 auto to_maximum = create_bound_towards_maximum(edges);
224 fix_horizontals(to_minimum);
225 fix_horizontals(to_maximum);
226 auto to_max_first_non_horizontal = to_maximum.edges.begin();
227 auto to_min_first_non_horizontal = to_minimum.edges.begin();
228 bool minimum_is_left = true;
229 while (to_max_first_non_horizontal != to_maximum.edges.end() &&
230 is_horizontal(*to_max_first_non_horizontal)) {
231 lm_minimum_has_horizontal = true;
232 ++to_max_first_non_horizontal;
233 }
234 while (to_min_first_non_horizontal != to_minimum.edges.end() &&
235 is_horizontal(*to_min_first_non_horizontal)) {
236 lm_minimum_has_horizontal = true;
237 ++to_min_first_non_horizontal;
238 }
239
240 if (to_max_first_non_horizontal == to_maximum.edges.end() ||
241 to_min_first_non_horizontal == to_minimum.edges.end()) {
242 throw std::runtime_error("should not have a horizontal only bound for a ring");
243 }
244
245 if (lm_minimum_has_horizontal) {
246 if (to_max_first_non_horizontal->bot.x > to_min_first_non_horizontal->bot.x) {
247 minimum_is_left = true;
248 move_horizontals_on_left_to_right(to_minimum, to_maximum);
249 } else {
250 minimum_is_left = false;
251 move_horizontals_on_left_to_right(to_maximum, to_minimum);
252 }
253 } else {
254 if (to_max_first_non_horizontal->dx > to_min_first_non_horizontal->dx) {
255 minimum_is_left = false;
256 } else {
257 minimum_is_left = true;
258 }
259 }
260 assert(!to_minimum.edges.empty());
261 assert(!to_maximum.edges.empty());
262 auto const& min_front = to_minimum.edges.front();
263 if (last_maximum) {
264 to_minimum.maximum_bound = last_maximum;
265 }
266 to_minimum.poly_type = poly_type;
267 to_maximum.poly_type = poly_type;
268 if (!minimum_is_left) {
269 to_minimum.side = edge_right;
270 to_maximum.side = edge_left;
271 to_minimum.winding_delta = -1;
272 to_maximum.winding_delta = 1;
273 minima_list.emplace_back(std::move(to_maximum), std::move(to_minimum), min_front.bot.y,
274 lm_minimum_has_horizontal);
275 if (!last_maximum) {
276 first_minimum = &(minima_list.back().right_bound);
277 } else {
278 last_maximum->maximum_bound = &(minima_list.back().right_bound);
279 }
280 last_maximum = &(minima_list.back().left_bound);
281 } else {
282 to_minimum.side = edge_left;
283 to_maximum.side = edge_right;
284 to_minimum.winding_delta = -1;
285 to_maximum.winding_delta = 1;
286 minima_list.emplace_back(std::move(to_minimum), std::move(to_maximum), min_front.bot.y,
287 lm_minimum_has_horizontal);
288 if (!last_maximum) {
289 first_minimum = &(minima_list.back().left_bound);
290 } else {
291 last_maximum->maximum_bound = &(minima_list.back().left_bound);
292 }
293 last_maximum = &(minima_list.back().right_bound);
294 }
295 }
296 last_maximum->maximum_bound = first_minimum;
297 first_minimum->maximum_bound = last_maximum;
298 }
299
300 template <typename T>
initialize_lm(local_minimum_ptr_list_itr<T> & lm)301 void initialize_lm(local_minimum_ptr_list_itr<T>& lm) {
302 if (!(*lm)->left_bound.edges.empty()) {
303 (*lm)->left_bound.current_edge = (*lm)->left_bound.edges.begin();
304 (*lm)->left_bound.next_edge = std::next((*lm)->left_bound.current_edge);
305 (*lm)->left_bound.current_x = static_cast<double>((*lm)->left_bound.current_edge->bot.x);
306 (*lm)->left_bound.winding_count = 0;
307 (*lm)->left_bound.winding_count2 = 0;
308 (*lm)->left_bound.side = edge_left;
309 (*lm)->left_bound.ring = nullptr;
310 }
311 if (!(*lm)->right_bound.edges.empty()) {
312 (*lm)->right_bound.current_edge = (*lm)->right_bound.edges.begin();
313 (*lm)->right_bound.next_edge = std::next((*lm)->right_bound.current_edge);
314 (*lm)->right_bound.current_x = static_cast<double>((*lm)->right_bound.current_edge->bot.x);
315 (*lm)->right_bound.winding_count = 0;
316 (*lm)->right_bound.winding_count2 = 0;
317 (*lm)->right_bound.side = edge_right;
318 (*lm)->right_bound.ring = nullptr;
319 }
320 }
321 }
322 }
323 }
324