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, active_bound_list<T>& active_bounds, ring_manager<T>& manager) {
39 if (active_bounds.empty()) {
40 return;
41 }
42 update_current_x(active_bounds, top_y);
43 bubble_sort(active_bounds.begin(), active_bounds.end(), intersection_compare<T>(),
44 hp_intersection_swap<T>(manager));
45 }
46
47 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)48 bool horizontals_at_top_scanbeam(T top_y,
49 active_bound_list_itr<T>& bnd_curr,
50 active_bound_list<T>& active_bounds,
51 ring_manager<T>& manager) {
52 bool shifted = false;
53 auto& current_edge = (*bnd_curr)->current_edge;
54 (*bnd_curr)->current_x = static_cast<double>(current_edge->top.x);
55 if (current_edge->bot.x < current_edge->top.x) {
56 // left to right
57 auto bnd_next = std::next(bnd_curr);
58 while (bnd_next != active_bounds.end() &&
59 (*bnd_next == nullptr || (*bnd_next)->current_x < (*bnd_curr)->current_x)) {
60 if (*bnd_next != nullptr && (*bnd_next)->current_edge->top.y != top_y &&
61 (*bnd_next)->current_edge->bot.y != top_y) {
62 mapbox::geometry::point<T> pt(wround<T>((*bnd_next)->current_x), top_y);
63 add_to_hot_pixels(pt, manager);
64 }
65 std::iter_swap(bnd_curr, bnd_next);
66 ++bnd_curr;
67 ++bnd_next;
68 shifted = true;
69 }
70 } else {
71 // right to left
72 if (bnd_curr != active_bounds.begin()) {
73 auto bnd_prev = std::prev(bnd_curr);
74 while (bnd_curr != active_bounds.begin() &&
75 (*bnd_prev == nullptr || (*bnd_prev)->current_x > (*bnd_curr)->current_x)) {
76 if (*bnd_prev != nullptr && (*bnd_prev)->current_edge->top.y != top_y &&
77 (*bnd_prev)->current_edge->bot.y != top_y) {
78 mapbox::geometry::point<T> pt(wround<T>((*bnd_prev)->current_x), top_y);
79 add_to_hot_pixels(pt, manager);
80 }
81 std::iter_swap(bnd_curr, bnd_prev);
82 --bnd_curr;
83 if (bnd_curr != active_bounds.begin()) {
84 --bnd_prev;
85 }
86 }
87 }
88 }
89 return shifted;
90 }
91
92 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)93 void process_hot_pixel_edges_at_top_of_scanbeam(T top_y,
94 scanbeam_list<T>& scanbeam,
95 active_bound_list<T>& active_bounds,
96 ring_manager<T>& manager) {
97 for (auto bnd = active_bounds.begin(); bnd != active_bounds.end();) {
98 if (*bnd == nullptr) {
99 ++bnd;
100 continue;
101 }
102 bound<T>& current_bound = *(*bnd);
103 auto bnd_curr = bnd;
104 bool shifted = false;
105 auto& current_edge = current_bound.current_edge;
106 while (current_edge != current_bound.edges.end() && current_edge->top.y == top_y) {
107 add_to_hot_pixels(current_edge->top, manager);
108 if (is_horizontal(*current_edge)) {
109 if (horizontals_at_top_scanbeam(top_y, bnd_curr, active_bounds, manager)) {
110 shifted = true;
111 }
112 }
113 next_edge_in_bound(current_bound, scanbeam);
114 }
115 if (current_edge == current_bound.edges.end()) {
116 *bnd_curr = nullptr;
117 }
118 if (!shifted) {
119 ++bnd;
120 }
121 }
122 active_bounds.erase(std::remove(active_bounds.begin(), active_bounds.end(), nullptr), active_bounds.end());
123 }
124
125 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)126 void insert_local_minima_into_ABL_hot_pixel(T top_y,
127 local_minimum_ptr_list<T>& minima_sorted,
128 local_minimum_ptr_list_itr<T>& lm,
129 active_bound_list<T>& active_bounds,
130 ring_manager<T>& manager,
131 scanbeam_list<T>& scanbeam) {
132 while (lm != minima_sorted.end() && (*lm)->y == top_y) {
133 add_to_hot_pixels((*lm)->left_bound.edges.front().bot, manager);
134 auto& left_bound = (*lm)->left_bound;
135 auto& right_bound = (*lm)->right_bound;
136 left_bound.current_edge = left_bound.edges.begin();
137 left_bound.next_edge = std::next(left_bound.current_edge);
138 left_bound.current_x = static_cast<double>(left_bound.current_edge->bot.x);
139 right_bound.current_edge = right_bound.edges.begin();
140 right_bound.next_edge = std::next(right_bound.current_edge);
141 right_bound.current_x = static_cast<double>(right_bound.current_edge->bot.x);
142 auto lb_abl_itr = insert_bound_into_ABL(left_bound, right_bound, active_bounds);
143 if (!current_edge_is_horizontal<T>(lb_abl_itr)) {
144 insert_sorted_scanbeam(scanbeam, (*lb_abl_itr)->current_edge->top.y);
145 }
146 auto rb_abl_itr = std::next(lb_abl_itr);
147 if (!current_edge_is_horizontal<T>(rb_abl_itr)) {
148 insert_sorted_scanbeam(scanbeam, (*rb_abl_itr)->current_edge->top.y);
149 }
150 ++lm;
151 }
152 }
153
154 template <typename T>
build_hot_pixels(local_minimum_list<T> & minima_list,ring_manager<T> & manager)155 void build_hot_pixels(local_minimum_list<T>& minima_list, ring_manager<T>& manager) {
156 active_bound_list<T> active_bounds;
157 scanbeam_list<T> scanbeam;
158 T scanline_y = std::numeric_limits<T>::max();
159
160 local_minimum_ptr_list<T> minima_sorted;
161 minima_sorted.reserve(minima_list.size());
162 for (auto& lm : minima_list) {
163 minima_sorted.push_back(&lm);
164 }
165 std::stable_sort(minima_sorted.begin(), minima_sorted.end(), local_minimum_sorter<T>());
166 local_minimum_ptr_list_itr<T> current_lm = minima_sorted.begin();
167
168 setup_scanbeam(minima_list, scanbeam);
169
170 // Estimate size for reserving hot pixels
171 std::size_t reserve = 0;
172 for (auto& lm : minima_list) {
173 reserve += lm.left_bound.edges.size() + 2;
174 reserve += lm.right_bound.edges.size() + 2;
175 }
176 manager.hot_pixels.reserve(reserve);
177
178 while (pop_from_scanbeam(scanline_y, scanbeam) || current_lm != minima_sorted.end()) {
179
180 process_hot_pixel_intersections(scanline_y, active_bounds, manager);
181
182 insert_local_minima_into_ABL_hot_pixel(scanline_y, minima_sorted, current_lm, active_bounds, manager, scanbeam);
183
184 process_hot_pixel_edges_at_top_of_scanbeam(scanline_y, scanbeam, active_bounds, manager);
185 }
186 preallocate_point_memory(manager, manager.hot_pixels.size());
187 sort_hot_pixels(manager);
188 }
189 } // namespace wagyu
190 } // namespace geometry
191 } // namespace mapbox
192