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/util.hpp>
10
11 namespace mapbox {
12 namespace geometry {
13 namespace wagyu {
14
15 template <typename T>
point_2_is_between_point_1_and_point_3(mapbox::geometry::point<T> const & pt1,mapbox::geometry::point<T> const & pt2,mapbox::geometry::point<T> const & pt3)16 bool point_2_is_between_point_1_and_point_3(mapbox::geometry::point<T> const& pt1,
17 mapbox::geometry::point<T> const& pt2,
18 mapbox::geometry::point<T> const& pt3) {
19 if ((pt1 == pt3) || (pt1 == pt2) || (pt3 == pt2)) {
20 return false;
21 } else if (pt1.x != pt3.x) {
22 return (pt2.x > pt1.x) == (pt2.x < pt3.x);
23 } else {
24 return (pt2.y > pt1.y) == (pt2.y < pt3.y);
25 }
26 }
27
28 template <typename T1, typename T2>
build_edge_list(mapbox::geometry::linear_ring<T2> const & path_geometry,edge_list<T1> & edges)29 bool build_edge_list(mapbox::geometry::linear_ring<T2> const& path_geometry, edge_list<T1>& edges) {
30
31 if (path_geometry.size() < 3) {
32 return false;
33 }
34
35 // As this is a loop, we need to first go backwards from end to try and find
36 // the proper starting point for the iterators before the beginning
37
38 auto itr_rev = path_geometry.rbegin();
39 auto itr = path_geometry.begin();
40 mapbox::geometry::point<T2> pt1 = *itr_rev;
41 mapbox::geometry::point<T2> pt2 = *itr;
42
43 // Find next non repeated point going backwards from
44 // end for pt1
45 while (pt1 == pt2) {
46 ++itr_rev;
47 if (itr_rev == path_geometry.rend()) {
48 return false;
49 }
50 pt1 = *itr_rev;
51 }
52 ++itr;
53 mapbox::geometry::point<T2> pt3 = *itr;
54 auto itr_last = itr_rev.base();
55 mapbox::geometry::point<T2> front_pt;
56 mapbox::geometry::point<T2> back_pt;
57 while (true) {
58 if (pt3 == pt2) {
59 // Duplicate point advance itr, but do not
60 // advance other points
61 if (itr == itr_last) {
62 break;
63 }
64 ++itr;
65 if (itr == itr_last) {
66 if (edges.empty()) {
67 break;
68 }
69 pt3 = front_pt;
70 } else {
71 pt3 = *itr;
72 }
73 continue;
74 }
75
76 // Now check if slopes are equal between two segments - either
77 // a spike or a collinear point - if so drop point number 2.
78 if (slopes_equal(pt1, pt2, pt3)) {
79 // We need to reconsider previously added points
80 // because the point it was using was found to be collinear
81 // or a spike
82 pt2 = pt1;
83 if (!edges.empty()) {
84 edges.pop_back(); // remove previous edge (pt1)
85 }
86 if (!edges.empty()) {
87 auto const& back_top = edges.back().top;
88 if (static_cast<T1>(back_pt.x) == back_top.x &&
89 static_cast<T1>(back_pt.y) == back_top.y) {
90 auto const& back_bot = edges.back().bot;
91 pt1 = mapbox::geometry::point<T2>(static_cast<T2>(back_bot.x),
92 static_cast<T2>(back_bot.y));
93 } else {
94 pt1 = mapbox::geometry::point<T2>(static_cast<T2>(back_top.x),
95 static_cast<T2>(back_top.y));
96 }
97 back_pt = pt1;
98 } else {
99 // If this occurs we must look to the back of the
100 // ring for new points.
101 while (*itr_rev == pt2) {
102 ++itr_rev;
103 if ((itr + 1) == itr_rev.base()) {
104 return false;
105 }
106 }
107 pt1 = *itr_rev;
108 itr_last = itr_rev.base();
109 }
110 continue;
111 }
112
113 if (edges.empty()) {
114 front_pt = pt2;
115 }
116 edges.emplace_back(pt2, pt3);
117 back_pt = pt2;
118 if (itr == itr_last) {
119 break;
120 }
121 pt1 = pt2;
122 pt2 = pt3;
123 ++itr;
124 if (itr == itr_last) {
125 if (edges.empty()) {
126 break;
127 }
128 pt3 = front_pt;
129 } else {
130 pt3 = *itr;
131 }
132 }
133
134 bool modified = false;
135 do {
136 modified = false;
137 if (edges.size() < 3) {
138 return false;
139 }
140 auto& f = edges.front();
141 auto& b = edges.back();
142 if (slopes_equal(f, b)) {
143 if (f.bot == b.top) {
144 if (f.top == b.bot) {
145 edges.pop_back();
146 edges.erase(edges.begin());
147 } else {
148 f.bot = b.bot;
149 edges.pop_back();
150 }
151 modified = true;
152 } else if (f.top == b.bot) {
153 f.top = b.top;
154 edges.pop_back();
155 modified = true;
156 } else if (f.top == b.top && f.bot == b.bot) {
157 edges.pop_back();
158 edges.erase(edges.begin());
159 modified = true;
160 } else if (f.top == b.top) {
161 if (point_2_is_between_point_1_and_point_3(f.top, f.bot, b.bot)) {
162 b.top = f.bot;
163 edges.erase(edges.begin());
164 } else {
165 f.top = b.bot;
166 edges.pop_back();
167 }
168 modified = true;
169 } else if (f.bot == b.bot) {
170 if (point_2_is_between_point_1_and_point_3(f.bot, f.top, b.top)) {
171 b.bot = f.top;
172 edges.erase(edges.begin());
173 } else {
174 f.bot = b.top;
175 edges.pop_back();
176 }
177 modified = true;
178 }
179 }
180 } while (modified);
181
182 return true;
183 }
184 }
185 }
186 }
187