1 #pragma once
2 
3 #include <mapbox/geometry/wagyu/active_bound_list.hpp>
4 #include <mapbox/geometry/wagyu/bound.hpp>
5 #include <mapbox/geometry/wagyu/bubble_sort.hpp>
6 #include <mapbox/geometry/wagyu/config.hpp>
7 #include <mapbox/geometry/wagyu/edge.hpp>
8 #include <mapbox/geometry/wagyu/intersect.hpp>
9 #include <mapbox/geometry/wagyu/intersect_util.hpp>
10 #include <mapbox/geometry/wagyu/ring.hpp>
11 #include <mapbox/geometry/wagyu/ring_util.hpp>
12 #include <mapbox/geometry/wagyu/util.hpp>
13 
14 namespace mapbox {
15 namespace geometry {
16 namespace wagyu {
17 
18 template <typename T>
19 struct hp_intersection_swap {
20 
21     ring_manager<T>& manager;
22 
hp_intersection_swapmapbox::geometry::wagyu::hp_intersection_swap23     hp_intersection_swap(ring_manager<T>& m) : manager(m) {
24     }
25 
operator ()mapbox::geometry::wagyu::hp_intersection_swap26     void operator()(bound_ptr<T> const& b1, bound_ptr<T> const& b2) {
27         mapbox::geometry::point<double> pt;
28         if (!get_edge_intersection<T, double>(*(b1->current_edge), *(b2->current_edge), pt)) {
29             // LCOV_EXCL_START
30             throw std::runtime_error("Trying to find intersection of lines that do not intersect");
31             // LCOV_EXCL_END
32         }
33         add_to_hot_pixels(round_point<T>(pt), manager);
34     }
35 };
36 
37 template <typename T>
process_hot_pixel_intersections(T top_y,active_bound_list<T> & active_bounds,ring_manager<T> & manager)38 void process_hot_pixel_intersections(T top_y,
39                                      active_bound_list<T>& active_bounds,
40                                      ring_manager<T>& manager) {
41     if (active_bounds.empty()) {
42         return;
43     }
44     update_current_x(active_bounds, top_y);
45     bubble_sort(active_bounds.begin(), active_bounds.end(), intersection_compare<T>(),
46                 hp_intersection_swap<T>(manager));
47 }
48 
49 template <typename T>
horizontals_at_top_scanbeam(T top_y,active_bound_list_itr<T> & bnd_curr,active_bound_list<T> & active_bounds,ring_manager<T> & manager)50 bool horizontals_at_top_scanbeam(T top_y,
51                                  active_bound_list_itr<T>& bnd_curr,
52                                  active_bound_list<T>& active_bounds,
53                                  ring_manager<T>& manager) {
54     bool shifted = false;
55     auto& current_edge = (*bnd_curr)->current_edge;
56     (*bnd_curr)->current_x = static_cast<double>(current_edge->top.x);
57     if (current_edge->bot.x < current_edge->top.x) {
58         // left to right
59         auto bnd_next = std::next(bnd_curr);
60         while (bnd_next != active_bounds.end() &&
61                (*bnd_next == nullptr || (*bnd_next)->current_x < (*bnd_curr)->current_x)) {
62             if (*bnd_next != nullptr && (*bnd_next)->current_edge->top.y != top_y &&
63                 (*bnd_next)->current_edge->bot.y != top_y) {
64                 mapbox::geometry::point<T> pt(wround<T>((*bnd_next)->current_x), top_y);
65                 add_to_hot_pixels(pt, manager);
66             }
67             std::iter_swap(bnd_curr, bnd_next);
68             ++bnd_curr;
69             ++bnd_next;
70             shifted = true;
71         }
72     } else {
73         // right to left
74         if (bnd_curr != active_bounds.begin()) {
75             auto bnd_prev = std::prev(bnd_curr);
76             while (bnd_curr != active_bounds.begin() &&
77                    (*bnd_prev == nullptr || (*bnd_prev)->current_x > (*bnd_curr)->current_x)) {
78                 if (*bnd_prev != nullptr && (*bnd_prev)->current_edge->top.y != top_y &&
79                     (*bnd_prev)->current_edge->bot.y != top_y) {
80                     mapbox::geometry::point<T> pt(wround<T>((*bnd_prev)->current_x), top_y);
81                     add_to_hot_pixels(pt, manager);
82                 }
83                 std::iter_swap(bnd_curr, bnd_prev);
84                 --bnd_curr;
85                 if (bnd_curr != active_bounds.begin()) {
86                     --bnd_prev;
87                 }
88             }
89         }
90     }
91     return shifted;
92 }
93 
94 template <typename T>
process_hot_pixel_edges_at_top_of_scanbeam(T top_y,scanbeam_list<T> & scanbeam,active_bound_list<T> & active_bounds,ring_manager<T> & manager)95 void process_hot_pixel_edges_at_top_of_scanbeam(T top_y,
96                                                 scanbeam_list<T>& scanbeam,
97                                                 active_bound_list<T>& active_bounds,
98                                                 ring_manager<T>& manager) {
99     for (auto bnd = active_bounds.begin(); bnd != active_bounds.end();) {
100         if (*bnd == nullptr) {
101             ++bnd;
102             continue;
103         }
104         bound<T>& current_bound = *(*bnd);
105         auto bnd_curr = bnd;
106         bool shifted = false;
107         auto& current_edge = current_bound.current_edge;
108         while (current_edge != current_bound.edges.end() && current_edge->top.y == top_y) {
109             add_to_hot_pixels(current_edge->top, manager);
110             if (is_horizontal(*current_edge)) {
111                 if (horizontals_at_top_scanbeam(top_y, bnd_curr, active_bounds, manager)) {
112                     shifted = true;
113                 }
114             }
115             next_edge_in_bound(current_bound, scanbeam);
116         }
117         if (current_edge == current_bound.edges.end()) {
118             *bnd_curr = nullptr;
119         }
120         if (!shifted) {
121             ++bnd;
122         }
123     }
124     active_bounds.erase(std::remove(active_bounds.begin(), active_bounds.end(), nullptr),
125                         active_bounds.end());
126 }
127 
128 template <typename T>
insert_local_minima_into_ABL_hot_pixel(T top_y,local_minimum_ptr_list<T> & minima_sorted,local_minimum_ptr_list_itr<T> & lm,active_bound_list<T> & active_bounds,ring_manager<T> & manager,scanbeam_list<T> & scanbeam)129 void insert_local_minima_into_ABL_hot_pixel(T top_y,
130                                             local_minimum_ptr_list<T>& minima_sorted,
131                                             local_minimum_ptr_list_itr<T>& lm,
132                                             active_bound_list<T>& active_bounds,
133                                             ring_manager<T>& manager,
134                                             scanbeam_list<T>& scanbeam) {
135     while (lm != minima_sorted.end() && (*lm)->y == top_y) {
136         add_to_hot_pixels((*lm)->left_bound.edges.front().bot, manager);
137         auto& left_bound = (*lm)->left_bound;
138         auto& right_bound = (*lm)->right_bound;
139         left_bound.current_edge = left_bound.edges.begin();
140         left_bound.next_edge = std::next(left_bound.current_edge);
141         left_bound.current_x = static_cast<double>(left_bound.current_edge->bot.x);
142         right_bound.current_edge = right_bound.edges.begin();
143         right_bound.next_edge = std::next(right_bound.current_edge);
144         right_bound.current_x = static_cast<double>(right_bound.current_edge->bot.x);
145         auto lb_abl_itr = insert_bound_into_ABL(left_bound, right_bound, active_bounds);
146         if (!current_edge_is_horizontal<T>(lb_abl_itr)) {
147             scanbeam.push_back((*lb_abl_itr)->current_edge->top.y);
148         }
149         auto rb_abl_itr = std::next(lb_abl_itr);
150         if (!current_edge_is_horizontal<T>(rb_abl_itr)) {
151             scanbeam.push_back((*rb_abl_itr)->current_edge->top.y);
152         }
153         ++lm;
154     }
155 }
156 
157 template <typename T>
build_hot_pixels(local_minimum_list<T> & minima_list,ring_manager<T> & manager)158 void build_hot_pixels(local_minimum_list<T>& minima_list, ring_manager<T>& manager) {
159     active_bound_list<T> active_bounds;
160     scanbeam_list<T> scanbeam;
161     T scanline_y = std::numeric_limits<T>::max();
162 
163     local_minimum_ptr_list<T> minima_sorted;
164     minima_sorted.reserve(minima_list.size());
165     for (auto& lm : minima_list) {
166         minima_sorted.push_back(&lm);
167     }
168     std::stable_sort(minima_sorted.begin(), minima_sorted.end(), local_minimum_sorter<T>());
169     local_minimum_ptr_list_itr<T> current_lm = minima_sorted.begin();
170 
171     setup_scanbeam(minima_list, scanbeam);
172 
173     // Estimate size for reserving hot pixels
174     std::size_t reserve = 0;
175     for (auto& lm : minima_list) {
176         reserve += lm.left_bound.edges.size() + 2;
177         reserve += lm.right_bound.edges.size() + 2;
178     }
179     manager.hot_pixels.reserve(reserve);
180 
181     while (pop_from_scanbeam(scanline_y, scanbeam) || current_lm != minima_sorted.end()) {
182 
183         process_hot_pixel_intersections(scanline_y, active_bounds, manager);
184 
185         insert_local_minima_into_ABL_hot_pixel(scanline_y, minima_sorted, current_lm, active_bounds,
186                                                manager, scanbeam);
187 
188         process_hot_pixel_edges_at_top_of_scanbeam(scanline_y, scanbeam, active_bounds, manager);
189     }
190     preallocate_point_memory(manager, manager.hot_pixels.size());
191     sort_hot_pixels(manager);
192 }
193 }
194 }
195 }
196