1 #pragma once
2 
3 #ifdef DEBUG
4 #include <iostream>
5 #include <sstream>
6 #endif
7 
8 #include <mapbox/geometry/wagyu/bound.hpp>
9 #include <mapbox/geometry/wagyu/config.hpp>
10 #include <mapbox/geometry/wagyu/edge.hpp>
11 #include <mapbox/geometry/wagyu/local_minimum.hpp>
12 #include <mapbox/geometry/wagyu/local_minimum_util.hpp>
13 #include <mapbox/geometry/wagyu/ring.hpp>
14 #include <mapbox/geometry/wagyu/scanbeam.hpp>
15 #include <mapbox/geometry/wagyu/util.hpp>
16 
17 namespace mapbox {
18 namespace geometry {
19 namespace wagyu {
20 
21 template <typename T>
22 using active_bound_list = std::vector<bound_ptr<T>>;
23 
24 template <typename T>
25 using active_bound_list_itr = typename active_bound_list<T>::iterator;
26 
27 template <typename T>
28 using active_bound_list_rev_itr = typename active_bound_list<T>::reverse_iterator;
29 
30 #ifdef DEBUG
31 
32 template <class charT, class traits, typename T>
operator <<(std::basic_ostream<charT,traits> & out,const active_bound_list<T> & bnds)33 inline std::basic_ostream<charT, traits>& operator<<(std::basic_ostream<charT, traits>& out,
34                                                      const active_bound_list<T>& bnds) {
35     std::size_t c = 0;
36     for (auto const& bnd : bnds) {
37         out << "Index: " << c++ << std::endl;
38         out << *bnd;
39     }
40     return out;
41 }
42 
43 template <typename T>
output_edges(active_bound_list<T> const & bnds)44 std::string output_edges(active_bound_list<T> const& bnds) {
45     std::ostringstream out;
46     out << "[";
47     bool first = true;
48     for (auto const& bnd : bnds) {
49         if (first) {
50             first = false;
51         } else {
52             out << ",";
53         }
54         out << "[[" << bnd->current_edge->bot.x << "," << bnd->current_edge->bot.y << "],[";
55         out << bnd->current_edge->top.x << "," << bnd->current_edge->top.y << "]]";
56     }
57     out << "]";
58     return out.str();
59 }
60 
61 #endif
62 
63 template <typename T>
is_even_odd_fill_type(bound<T> const & bound,fill_type subject_fill_type,fill_type clip_fill_type)64 bool is_even_odd_fill_type(bound<T> const& bound,
65                            fill_type subject_fill_type,
66                            fill_type clip_fill_type) {
67     if (bound.poly_type == polygon_type_subject) {
68         return subject_fill_type == fill_type_even_odd;
69     } else {
70         return clip_fill_type == fill_type_even_odd;
71     }
72 }
73 
74 template <typename T>
is_even_odd_alt_fill_type(bound<T> const & bound,fill_type subject_fill_type,fill_type clip_fill_type)75 bool is_even_odd_alt_fill_type(bound<T> const& bound,
76                                fill_type subject_fill_type,
77                                fill_type clip_fill_type) {
78     if (bound.poly_type == polygon_type_subject) {
79         return clip_fill_type == fill_type_even_odd;
80     } else {
81         return subject_fill_type == fill_type_even_odd;
82     }
83 }
84 
85 template <typename T>
86 struct bound_insert_location {
87 
88     bound<T> const& bound2;
89 
bound_insert_locationmapbox::geometry::wagyu::bound_insert_location90     bound_insert_location(bound<T> const& b) : bound2(b) {
91     }
92 
operator ()mapbox::geometry::wagyu::bound_insert_location93     bool operator()(bound_ptr<T> const& b) {
94         auto const& bound1 = *b;
95         if (values_are_equal(bound2.current_x, bound1.current_x)) {
96             if (bound2.current_edge->top.y > bound1.current_edge->top.y) {
97                 return static_cast<double>(bound2.current_edge->top.x) <
98                        get_current_x(*(bound1.current_edge), bound2.current_edge->top.y);
99             } else {
100                 return static_cast<double>(bound1.current_edge->top.x) >
101                        get_current_x(*(bound2.current_edge), bound1.current_edge->top.y);
102             }
103         } else {
104             return bound2.current_x < bound1.current_x;
105         }
106     }
107 };
108 
109 template <typename T>
110 active_bound_list_itr<T>
insert_bound_into_ABL(bound<T> & left,bound<T> & right,active_bound_list<T> & active_bounds)111 insert_bound_into_ABL(bound<T>& left, bound<T>& right, active_bound_list<T>& active_bounds) {
112 
113     auto itr =
114         std::find_if(active_bounds.begin(), active_bounds.end(), bound_insert_location<T>(left));
115     return active_bounds.insert(itr, { &left, &right });
116 }
117 
118 template <typename T>
is_maxima(bound<T> & bnd,T y)119 inline bool is_maxima(bound<T>& bnd, T y) {
120     return bnd.next_edge == bnd.edges.end() && bnd.current_edge->top.y == y;
121 }
122 
123 template <typename T>
is_maxima(active_bound_list_itr<T> & bnd,T y)124 inline bool is_maxima(active_bound_list_itr<T>& bnd, T y) {
125     return is_maxima(*(*bnd), y);
126 }
127 
128 template <typename T>
is_intermediate(bound<T> & bnd,T y)129 inline bool is_intermediate(bound<T>& bnd, T y) {
130     return bnd.next_edge != bnd.edges.end() && bnd.current_edge->top.y == y;
131 }
132 
133 template <typename T>
is_intermediate(active_bound_list_itr<T> & bnd,T y)134 inline bool is_intermediate(active_bound_list_itr<T>& bnd, T y) {
135     return is_intermediate(*(*bnd), y);
136 }
137 
138 template <typename T>
current_edge_is_horizontal(active_bound_list_itr<T> & bnd)139 inline bool current_edge_is_horizontal(active_bound_list_itr<T>& bnd) {
140     return is_horizontal(*((*bnd)->current_edge));
141 }
142 
143 template <typename T>
next_edge_is_horizontal(active_bound_list_itr<T> & bnd)144 inline bool next_edge_is_horizontal(active_bound_list_itr<T>& bnd) {
145     return is_horizontal(*((*bnd)->next_edge));
146 }
147 
148 template <typename T>
next_edge_in_bound(bound<T> & bnd,scanbeam_list<T> & scanbeam)149 void next_edge_in_bound(bound<T>& bnd, scanbeam_list<T>& scanbeam) {
150     auto& current_edge = bnd.current_edge;
151     ++current_edge;
152     if (current_edge != bnd.edges.end()) {
153         ++(bnd.next_edge);
154         bnd.current_x = static_cast<double>(current_edge->bot.x);
155         if (!is_horizontal<T>(*current_edge)) {
156             scanbeam.push_back(current_edge->top.y);
157         }
158     }
159 }
160 
161 template <typename T>
get_maxima_pair(active_bound_list_itr<T> const & bnd,active_bound_list<T> & active_bounds)162 active_bound_list_itr<T> get_maxima_pair(active_bound_list_itr<T> const& bnd,
163                                          active_bound_list<T>& active_bounds) {
164     bound_ptr<T> maximum = (*bnd)->maximum_bound;
165     return std::find(active_bounds.begin(), active_bounds.end(), maximum);
166 }
167 
168 template <typename T>
set_winding_count(active_bound_list_itr<T> & bnd_itr,active_bound_list<T> & active_bounds,fill_type subject_fill_type,fill_type clip_fill_type)169 void set_winding_count(active_bound_list_itr<T>& bnd_itr,
170                        active_bound_list<T>& active_bounds,
171                        fill_type subject_fill_type,
172                        fill_type clip_fill_type) {
173 
174     auto rev_bnd_itr = active_bound_list_rev_itr<T>(bnd_itr);
175     if (rev_bnd_itr == active_bounds.rend()) {
176         (*bnd_itr)->winding_count = (*bnd_itr)->winding_delta;
177         (*bnd_itr)->winding_count2 = 0;
178         return;
179     }
180 
181     // find the edge of the same polytype that immediately preceeds 'edge' in
182     // AEL
183     while (rev_bnd_itr != active_bounds.rend() &&
184            (*rev_bnd_itr)->poly_type != (*bnd_itr)->poly_type) {
185         ++rev_bnd_itr;
186     }
187     if (rev_bnd_itr == active_bounds.rend()) {
188         (*bnd_itr)->winding_count = (*bnd_itr)->winding_delta;
189         (*bnd_itr)->winding_count2 = 0;
190     } else if (is_even_odd_fill_type(*(*bnd_itr), subject_fill_type, clip_fill_type)) {
191         // EvenOdd filling ...
192         (*bnd_itr)->winding_count = (*bnd_itr)->winding_delta;
193         (*bnd_itr)->winding_count2 = (*rev_bnd_itr)->winding_count2;
194     } else {
195         // nonZero, Positive or Negative filling ...
196         if ((*rev_bnd_itr)->winding_count * (*rev_bnd_itr)->winding_delta < 0) {
197             // prev edge is 'decreasing' WindCount (WC) toward zero
198             // so we're outside the previous polygon ...
199             if (std::abs(static_cast<int>((*rev_bnd_itr)->winding_count)) > 1) {
200                 // outside prev poly but still inside another.
201                 // when reversing direction of prev poly use the same WC
202                 if ((*rev_bnd_itr)->winding_delta * (*bnd_itr)->winding_delta < 0) {
203                     (*bnd_itr)->winding_count = (*rev_bnd_itr)->winding_count;
204                 } else {
205                     // otherwise continue to 'decrease' WC ...
206                     (*bnd_itr)->winding_count =
207                         (*rev_bnd_itr)->winding_count + (*bnd_itr)->winding_delta;
208                 }
209             } else {
210                 // now outside all polys of same polytype so set own WC ...
211                 (*bnd_itr)->winding_count = (*bnd_itr)->winding_delta;
212             }
213         } else {
214             // prev edge is 'increasing' WindCount (WC) away from zero
215             // so we're inside the previous polygon ...
216             if ((*rev_bnd_itr)->winding_delta * (*bnd_itr)->winding_delta < 0) {
217                 // if wind direction is reversing prev then use same WC
218                 (*bnd_itr)->winding_count = (*rev_bnd_itr)->winding_count;
219             } else {
220                 // otherwise add to WC ...
221                 (*bnd_itr)->winding_count =
222                     (*rev_bnd_itr)->winding_count + (*bnd_itr)->winding_delta;
223             }
224         }
225         (*bnd_itr)->winding_count2 = (*rev_bnd_itr)->winding_count2;
226     }
227 
228     // update winding_count2 ...
229     auto bnd_itr_forward = rev_bnd_itr.base();
230     if (is_even_odd_alt_fill_type(*(*bnd_itr), subject_fill_type, clip_fill_type)) {
231         // EvenOdd filling ...
232         while (bnd_itr_forward != bnd_itr) {
233             (*bnd_itr)->winding_count2 = ((*bnd_itr)->winding_count2 == 0 ? 1 : 0);
234             ++bnd_itr_forward;
235         }
236     } else {
237         // nonZero, Positive or Negative filling ...
238         while (bnd_itr_forward != bnd_itr) {
239             (*bnd_itr)->winding_count2 += (*bnd_itr_forward)->winding_delta;
240             ++bnd_itr_forward;
241         }
242     }
243 }
244 
245 template <typename T>
is_contributing(bound<T> const & bnd,clip_type cliptype,fill_type subject_fill_type,fill_type clip_fill_type)246 bool is_contributing(bound<T> const& bnd,
247                      clip_type cliptype,
248                      fill_type subject_fill_type,
249                      fill_type clip_fill_type) {
250     fill_type pft = subject_fill_type;
251     fill_type pft2 = clip_fill_type;
252     if (bnd.poly_type != polygon_type_subject) {
253         pft = clip_fill_type;
254         pft2 = subject_fill_type;
255     }
256 
257     switch (pft) {
258     case fill_type_even_odd:
259         break;
260     case fill_type_non_zero:
261         if (std::abs(static_cast<int>(bnd.winding_count)) != 1) {
262             return false;
263         }
264         break;
265     case fill_type_positive:
266         if (bnd.winding_count != 1) {
267             return false;
268         }
269         break;
270     case fill_type_negative:
271     default:
272         if (bnd.winding_count != -1) {
273             return false;
274         }
275     }
276 
277     switch (cliptype) {
278     case clip_type_intersection:
279         switch (pft2) {
280         case fill_type_even_odd:
281         case fill_type_non_zero:
282             return (bnd.winding_count2 != 0);
283         case fill_type_positive:
284             return (bnd.winding_count2 > 0);
285         case fill_type_negative:
286         default:
287             return (bnd.winding_count2 < 0);
288         }
289         break;
290     case clip_type_union:
291         switch (pft2) {
292         case fill_type_even_odd:
293         case fill_type_non_zero:
294             return (bnd.winding_count2 == 0);
295         case fill_type_positive:
296             return (bnd.winding_count2 <= 0);
297         case fill_type_negative:
298         default:
299             return (bnd.winding_count2 >= 0);
300         }
301         break;
302     case clip_type_difference:
303         if (bnd.poly_type == polygon_type_subject) {
304             switch (pft2) {
305             case fill_type_even_odd:
306             case fill_type_non_zero:
307                 return (bnd.winding_count2 == 0);
308             case fill_type_positive:
309                 return (bnd.winding_count2 <= 0);
310             case fill_type_negative:
311             default:
312                 return (bnd.winding_count2 >= 0);
313             }
314         } else {
315             switch (pft2) {
316             case fill_type_even_odd:
317             case fill_type_non_zero:
318                 return (bnd.winding_count2 != 0);
319             case fill_type_positive:
320                 return (bnd.winding_count2 > 0);
321             case fill_type_negative:
322             default:
323                 return (bnd.winding_count2 < 0);
324             }
325         }
326         break;
327     case clip_type_x_or:
328         return true;
329         break;
330     default:
331         return true;
332     }
333 }
334 
335 template <typename T>
insert_lm_left_and_right_bound(bound<T> & left_bound,bound<T> & right_bound,active_bound_list<T> & active_bounds,ring_manager<T> & rings,scanbeam_list<T> & scanbeam,clip_type cliptype,fill_type subject_fill_type,fill_type clip_fill_type)336 void insert_lm_left_and_right_bound(bound<T>& left_bound,
337                                     bound<T>& right_bound,
338                                     active_bound_list<T>& active_bounds,
339                                     ring_manager<T>& rings,
340                                     scanbeam_list<T>& scanbeam,
341                                     clip_type cliptype,
342                                     fill_type subject_fill_type,
343                                     fill_type clip_fill_type) {
344 
345     // Both left and right bound
346     auto lb_abl_itr = insert_bound_into_ABL(left_bound, right_bound, active_bounds);
347     auto rb_abl_itr = std::next(lb_abl_itr);
348     set_winding_count(lb_abl_itr, active_bounds, subject_fill_type, clip_fill_type);
349     (*rb_abl_itr)->winding_count = (*lb_abl_itr)->winding_count;
350     (*rb_abl_itr)->winding_count2 = (*lb_abl_itr)->winding_count2;
351     if (is_contributing(left_bound, cliptype, subject_fill_type, clip_fill_type)) {
352         add_local_minimum_point(*(*lb_abl_itr), *(*rb_abl_itr), active_bounds,
353                                 (*lb_abl_itr)->current_edge->bot, rings);
354     }
355 
356     // Add top of edges to scanbeam
357     scanbeam.push_back((*lb_abl_itr)->current_edge->top.y);
358 
359     if (!current_edge_is_horizontal<T>(rb_abl_itr)) {
360         scanbeam.push_back((*rb_abl_itr)->current_edge->top.y);
361     }
362 }
363 
364 template <typename T>
insert_local_minima_into_ABL(T const bot_y,local_minimum_ptr_list<T> const & minima_sorted,local_minimum_ptr_list_itr<T> & current_lm,active_bound_list<T> & active_bounds,ring_manager<T> & rings,scanbeam_list<T> & scanbeam,clip_type cliptype,fill_type subject_fill_type,fill_type clip_fill_type)365 void insert_local_minima_into_ABL(T const bot_y,
366                                   local_minimum_ptr_list<T> const& minima_sorted,
367                                   local_minimum_ptr_list_itr<T>& current_lm,
368                                   active_bound_list<T>& active_bounds,
369                                   ring_manager<T>& rings,
370                                   scanbeam_list<T>& scanbeam,
371                                   clip_type cliptype,
372                                   fill_type subject_fill_type,
373                                   fill_type clip_fill_type) {
374     while (current_lm != minima_sorted.end() && bot_y == (*current_lm)->y) {
375         initialize_lm<T>(current_lm);
376         auto& left_bound = (*current_lm)->left_bound;
377         auto& right_bound = (*current_lm)->right_bound;
378         insert_lm_left_and_right_bound(left_bound, right_bound, active_bounds, rings, scanbeam,
379                                        cliptype, subject_fill_type, clip_fill_type);
380         ++current_lm;
381     }
382 }
383 
384 template <typename T>
insert_horizontal_local_minima_into_ABL(T const top_y,local_minimum_ptr_list<T> const & minima_sorted,local_minimum_ptr_list_itr<T> & current_lm,active_bound_list<T> & active_bounds,ring_manager<T> & rings,scanbeam_list<T> & scanbeam,clip_type cliptype,fill_type subject_fill_type,fill_type clip_fill_type)385 void insert_horizontal_local_minima_into_ABL(T const top_y,
386                                              local_minimum_ptr_list<T> const& minima_sorted,
387                                              local_minimum_ptr_list_itr<T>& current_lm,
388                                              active_bound_list<T>& active_bounds,
389                                              ring_manager<T>& rings,
390                                              scanbeam_list<T>& scanbeam,
391                                              clip_type cliptype,
392                                              fill_type subject_fill_type,
393                                              fill_type clip_fill_type) {
394     while (current_lm != minima_sorted.end() && top_y == (*current_lm)->y &&
395            (*current_lm)->minimum_has_horizontal) {
396         initialize_lm<T>(current_lm);
397         auto& left_bound = (*current_lm)->left_bound;
398         auto& right_bound = (*current_lm)->right_bound;
399         insert_lm_left_and_right_bound(left_bound, right_bound, active_bounds, rings, scanbeam,
400                                        cliptype, subject_fill_type, clip_fill_type);
401         ++current_lm;
402     }
403 }
404 }
405 }
406 }
407