1 #pragma once
2 
3 #include <mapbox/geometry/line_string.hpp>
4 #include <mapbox/geometry/point.hpp>
5 #include <mapbox/geometry/polygon.hpp>
6 
7 #include <mapbox/geometry/wagyu/config.hpp>
8 #include <mapbox/geometry/wagyu/edge.hpp>
9 #include <mapbox/geometry/wagyu/local_minimum.hpp>
10 #include <mapbox/geometry/wagyu/util.hpp>
11 
12 namespace mapbox {
13 namespace geometry {
14 namespace wagyu {
15 
16 template <typename T>
process_horizontal_left_to_right(T scanline_y,active_bound_list_itr<T> & horz_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)17 active_bound_list_itr<T> process_horizontal_left_to_right(T scanline_y,
18                                                           active_bound_list_itr<T>& horz_bound,
19                                                           active_bound_list<T>& active_bounds,
20                                                           ring_manager<T>& rings,
21                                                           scanbeam_list<T>& scanbeam,
22                                                           clip_type cliptype,
23                                                           fill_type subject_fill_type,
24                                                           fill_type clip_fill_type) {
25     auto horizontal_itr_behind = horz_bound;
26     bool shifted = false;
27     bool is_maxima_edge = is_maxima(horz_bound, scanline_y);
28     auto bound_max_pair = active_bounds.end();
29     if (is_maxima_edge) {
30         bound_max_pair = get_maxima_pair<T>(horz_bound, active_bounds);
31     }
32 
33     auto hp_itr = rings.current_hp_itr;
34     while (hp_itr != rings.hot_pixels.end() &&
35            (hp_itr->y > scanline_y ||
36             (hp_itr->y == scanline_y && hp_itr->x < (*horz_bound)->current_edge->bot.x))) {
37         ++hp_itr;
38     }
39 
40     auto bnd = std::next(horz_bound);
41 
42     while (bnd != active_bounds.end()) {
43         if (*bnd == nullptr) {
44             ++bnd;
45             continue;
46         }
47         // this code block inserts extra coords into horizontal edges (in output
48         // polygons) wherever hot pixels touch these horizontal edges. This helps
49         //'simplifying' polygons (ie if the Simplify property is set).
50         while (hp_itr != rings.hot_pixels.end() && hp_itr->y == scanline_y &&
51                hp_itr->x < wround<T>((*bnd)->current_x) &&
52                hp_itr->x < (*horz_bound)->current_edge->top.x) {
53             if ((*horz_bound)->ring) {
54                 add_point_to_ring(*(*horz_bound), *hp_itr, rings);
55             }
56             ++hp_itr;
57         }
58 
59         if ((*bnd)->current_x > static_cast<double>((*horz_bound)->current_edge->top.x)) {
60             break;
61         }
62 
63         // Also break if we've got to the end of an intermediate horizontal edge ...
64         // nb: Smaller Dx's are to the right of larger Dx's ABOVE the horizontal.
65         if (wround<T>((*bnd)->current_x) == (*horz_bound)->current_edge->top.x &&
66             (*horz_bound)->next_edge != (*horz_bound)->edges.end() &&
67             (*horz_bound)->current_edge->dx < (*horz_bound)->next_edge->dx) {
68             break;
69         }
70 
71         // note: may be done multiple times
72         if ((*horz_bound)->ring) {
73             add_point_to_ring(*(*horz_bound),
74                               mapbox::geometry::point<T>(wround<T>((*bnd)->current_x), scanline_y),
75                               rings);
76         }
77 
78         // OK, so far we're still in range of the horizontal Edge  but make sure
79         // we're at the last of consec. horizontals when matching with eMaxPair
80         if (is_maxima_edge && bnd == bound_max_pair) {
81             if ((*horz_bound)->ring) {
82                 add_local_maximum_point(*(*horz_bound), *(*bound_max_pair),
83                                         (*horz_bound)->current_edge->top, rings, active_bounds);
84             }
85             *bound_max_pair = nullptr;
86             *horz_bound = nullptr;
87             if (!shifted) {
88                 ++horizontal_itr_behind;
89             }
90             return horizontal_itr_behind;
91         }
92 
93         intersect_bounds(*(*horz_bound), *(*bnd),
94                          mapbox::geometry::point<T>(wround<T>((*bnd)->current_x), scanline_y),
95                          cliptype, subject_fill_type, clip_fill_type, rings, active_bounds);
96         std::iter_swap(horz_bound, bnd);
97         horz_bound = bnd;
98         ++bnd;
99         shifted = true;
100     } // end while (bnd != active_bounds.end())
101 
102     if ((*horz_bound)->ring) {
103         while (hp_itr != rings.hot_pixels.end() && hp_itr->y == scanline_y &&
104                hp_itr->x < (*horz_bound)->current_edge->top.x) {
105             add_point_to_ring(*(*horz_bound), *hp_itr, rings);
106             ++hp_itr;
107         }
108     }
109 
110     if ((*horz_bound)->ring) {
111         add_point_to_ring(*(*horz_bound), (*horz_bound)->current_edge->top, rings);
112     }
113 
114     if ((*horz_bound)->next_edge != (*horz_bound)->edges.end()) {
115         next_edge_in_bound(*(*horz_bound), scanbeam);
116     } else {
117         *horz_bound = nullptr;
118     }
119     if (!shifted) {
120         ++horizontal_itr_behind;
121     }
122     return horizontal_itr_behind;
123 }
124 
125 template <typename T>
process_horizontal_right_to_left(T scanline_y,active_bound_list_itr<T> & horz_bound_fwd,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)126 active_bound_list_itr<T> process_horizontal_right_to_left(T scanline_y,
127                                                           active_bound_list_itr<T>& horz_bound_fwd,
128                                                           active_bound_list<T>& active_bounds,
129                                                           ring_manager<T>& rings,
130                                                           scanbeam_list<T>& scanbeam,
131                                                           clip_type cliptype,
132                                                           fill_type subject_fill_type,
133                                                           fill_type clip_fill_type) {
134     auto next_bnd_itr = std::next(horz_bound_fwd);
135     bool is_maxima_edge = is_maxima(horz_bound_fwd, scanline_y);
136     auto bound_max_pair = active_bounds.rend();
137     if (is_maxima_edge) {
138         bound_max_pair =
139             active_bound_list_rev_itr<T>(get_maxima_pair<T>(horz_bound_fwd, active_bounds));
140         --bound_max_pair;
141     }
142     auto hp_itr_fwd = rings.current_hp_itr;
143     while (
144         hp_itr_fwd != rings.hot_pixels.end() &&
145         (hp_itr_fwd->y < scanline_y ||
146          (hp_itr_fwd->y == scanline_y && hp_itr_fwd->x < (*horz_bound_fwd)->current_edge->top.x))) {
147         ++hp_itr_fwd;
148     }
149     auto hp_itr = hot_pixel_rev_itr<T>(hp_itr_fwd);
150 
151     auto bnd = active_bound_list_rev_itr<T>(horz_bound_fwd);
152     auto horz_bound = std::prev(bnd);
153     while (bnd != active_bounds.rend()) {
154         if (*bnd == nullptr) {
155             ++bnd;
156             continue;
157         }
158         // this code block inserts extra coords into horizontal edges (in output
159         // polygons) wherever hot pixels touch these horizontal edges.
160         while (hp_itr != rings.hot_pixels.rend() && hp_itr->y == scanline_y &&
161                hp_itr->x > wround<T>((*bnd)->current_x) &&
162                hp_itr->x > (*horz_bound)->current_edge->top.x) {
163             if ((*horz_bound)->ring) {
164                 add_point_to_ring(*(*horz_bound), *hp_itr, rings);
165             }
166             ++hp_itr;
167         }
168 
169         if ((*bnd)->current_x < static_cast<double>((*horz_bound)->current_edge->top.x)) {
170             break;
171         }
172 
173         // Also break if we've got to the end of an intermediate horizontal edge ...
174         // nb: Smaller Dx's are to the right of larger Dx's ABOVE the horizontal.
175         if (wround<T>((*bnd)->current_x) == (*horz_bound)->current_edge->top.x &&
176             (*horz_bound)->next_edge != (*horz_bound)->edges.end() &&
177             (*horz_bound)->current_edge->dx < (*horz_bound)->next_edge->dx) {
178             break;
179         }
180 
181         // note: may be done multiple times
182         if ((*horz_bound)->ring) {
183             add_point_to_ring(*(*horz_bound),
184                               mapbox::geometry::point<T>(wround<T>((*bnd)->current_x), scanline_y),
185                               rings);
186         }
187 
188         // OK, so far we're still in range of the horizontal Edge  but make sure
189         // we're at the last of consec. horizontals when matching with eMaxPair
190         if (is_maxima_edge && bnd == bound_max_pair) {
191             if ((*horz_bound)->ring) {
192                 add_local_maximum_point(*(*horz_bound), *(*bound_max_pair),
193                                         (*horz_bound)->current_edge->top, rings, active_bounds);
194             }
195             *bound_max_pair = nullptr;
196             *horz_bound = nullptr;
197             return next_bnd_itr;
198         }
199 
200         intersect_bounds(*(*bnd), *(*horz_bound),
201                          mapbox::geometry::point<T>(wround<T>((*bnd)->current_x), scanline_y),
202                          cliptype, subject_fill_type, clip_fill_type, rings, active_bounds);
203         std::iter_swap(horz_bound, bnd);
204         horz_bound = bnd;
205         ++bnd;
206     } // end while (bnd != active_bounds.rend())
207 
208     if ((*horz_bound)->ring) {
209         while (hp_itr != rings.hot_pixels.rend() && hp_itr->y == scanline_y &&
210                hp_itr->x > (*horz_bound)->current_edge->top.x) {
211             add_point_to_ring(*(*horz_bound), *hp_itr, rings);
212             ++hp_itr;
213         }
214     }
215     if ((*horz_bound)->ring) {
216         add_point_to_ring(*(*horz_bound), (*horz_bound)->current_edge->top, rings);
217     }
218 
219     if ((*horz_bound)->next_edge != (*horz_bound)->edges.end()) {
220         next_edge_in_bound(*(*horz_bound), scanbeam);
221     } else {
222         *horz_bound = nullptr;
223     }
224     return next_bnd_itr;
225 }
226 
227 template <typename T>
process_horizontal(T scanline_y,active_bound_list_itr<T> & horz_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)228 active_bound_list_itr<T> process_horizontal(T scanline_y,
229                                             active_bound_list_itr<T>& horz_bound,
230                                             active_bound_list<T>& active_bounds,
231                                             ring_manager<T>& rings,
232                                             scanbeam_list<T>& scanbeam,
233                                             clip_type cliptype,
234                                             fill_type subject_fill_type,
235                                             fill_type clip_fill_type) {
236     if ((*horz_bound)->current_edge->bot.x < (*horz_bound)->current_edge->top.x) {
237         return process_horizontal_left_to_right(scanline_y, horz_bound, active_bounds, rings,
238                                                 scanbeam, cliptype, subject_fill_type,
239                                                 clip_fill_type);
240     } else {
241         return process_horizontal_right_to_left(scanline_y, horz_bound, active_bounds, rings,
242                                                 scanbeam, cliptype, subject_fill_type,
243                                                 clip_fill_type);
244     }
245 }
246 
247 template <typename T>
process_horizontals(T scanline_y,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)248 void process_horizontals(T scanline_y,
249                          active_bound_list<T>& active_bounds,
250                          ring_manager<T>& rings,
251                          scanbeam_list<T>& scanbeam,
252                          clip_type cliptype,
253                          fill_type subject_fill_type,
254                          fill_type clip_fill_type) {
255     for (auto bnd_itr = active_bounds.begin(); bnd_itr != active_bounds.end();) {
256         if (*bnd_itr != nullptr && current_edge_is_horizontal<T>(bnd_itr)) {
257             bnd_itr = process_horizontal(scanline_y, bnd_itr, active_bounds, rings, scanbeam,
258                                          cliptype, subject_fill_type, clip_fill_type);
259         } else {
260             ++bnd_itr;
261         }
262     }
263     active_bounds.erase(std::remove(active_bounds.begin(), active_bounds.end(), nullptr),
264                         active_bounds.end());
265 }
266 }
267 }
268 }
269