1 // Boost.Geometry (aka GGL, Generic Geometry Library)
2 //
3 // Copyright (c) 2012-2014 Barend Gehrels, Amsterdam, the Netherlands.
4
5 // Use, modification and distribution is subject to the Boost Software License,
6 // Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
7 // http://www.boost.org/LICENSE_1_0.txt)
8
9 #include <geometry_test_common.hpp>
10
11 #include <boost/algorithm/string/trim.hpp>
12 #include <boost/assign/list_of.hpp>
13
14 #include <boost/geometry/geometries/point_xy.hpp>
15 #include <boost/geometry/algorithms/detail/get_left_turns.hpp>
16
17 #if defined(TEST_WITH_SVG)
18 # include <boost/geometry/io/svg/svg_mapper.hpp>
19 #endif
20
21
22 NOTE: this unit test is out of date.
23 get_left_turns is used by buffer and might be used in the future by solving self-tangencies in overlays.
24 it is currently being changed by buffer.
25
26 namespace bglt = boost::geometry::detail::left_turns;
27
28 #if defined(TEST_WITH_SVG)
29 template <typename Point>
further_than(Point const & p,Point const & origin,int mul,int div)30 inline Point further_than(Point const& p, Point const& origin, int mul, int div)
31 {
32 typedef Point vector_type;
33
34 vector_type v = p;
35 bg::subtract_point(v, origin);
36
37 bg::divide_value(v, div);
38 bg::multiply_value(v, mul);
39 Point result = origin;
40 bg::add_point(result, v);
41 return result;
42 }
43
get_color(int index)44 inline std::string get_color(int index)
45 {
46 switch (index)
47 {
48 case 0 : return "rgb(0,192,0)";
49 case 1 : return "rgb(0,0,255)";
50 case 2 : return "rgb(255,0,0)";
51 case 3 : return "rgb(255,255,0)";
52 }
53 return "rgb(128,128,128)";
54 }
55 #endif
56
57
58 template <typename Point>
test_one(std::string const & caseid,Point const & p,std::vector<bglt::turn_angle_info<Point>> const & angles,std::string const & expected_sorted_indices,std::string const & expected_left_indices)59 void test_one(std::string const& caseid,
60 Point const& p,
61 std::vector<bglt::turn_angle_info<Point> > const& angles,
62 std::string const& expected_sorted_indices,
63 std::string const& expected_left_indices)
64 {
65 typedef Point vector_type;
66
67 std::vector<bglt::angle_info<Point> > sorted;
68 for (typename std::vector<bglt::turn_angle_info<Point> >::const_iterator it =
69 angles.begin(); it != angles.end(); ++it)
70 {
71 for (int i = 0; i < 2; i++)
72 {
73 bglt::angle_info<Point> info(it->seg_id, i == 0, it->points[i]);
74 sorted.push_back(info);
75 }
76 }
77
78 // Sort on angle
79 std::sort(sorted.begin(), sorted.end(), bglt::angle_less<Point>(p));
80
81 // Block all turns on the right side of any turn
82 bglt::block_turns_on_right_sides(angles, sorted);
83
84 // Check the sorting
85 {
86 std::ostringstream out;
87 out << std::boolalpha;
88 for (typename std::vector<bglt::angle_info<Point> >::const_iterator it =
89 sorted.begin(); it != sorted.end(); ++it)
90 {
91 out << " " << it->seg_id.segment_index
92 << "-" << it->incoming;
93 }
94 std::string detected = boost::trim_copy(out.str());
95 BOOST_CHECK_EQUAL(expected_sorted_indices, detected);
96 }
97
98
99 // Check outgoing lines
100 std::vector<bglt::left_turn> seg_ids;
101 bglt::get_left_turns(sorted, p, seg_ids);
102 {
103 std::ostringstream out;
104 out << std::boolalpha;
105 for (std::vector<bglt::left_turn>::const_iterator it =
106 seg_ids.begin(); it != seg_ids.end(); ++it)
107 {
108 out
109 << " " << it->from.segment_index
110 << "->" << it->to.segment_index
111 ;
112 }
113 std::string detected = boost::trim_copy(out.str());
114 BOOST_CHECK_EQUAL(expected_left_indices, detected);
115 }
116
117 #if defined(TEST_WITH_SVG)
118 {
119 std::ostringstream filename;
120 filename << "get_left_turns_" << caseid
121 << "_" << string_from_type<typename bg::coordinate_type<Point>::type>::name()
122 << ".svg";
123
124 std::ofstream svg(filename.str().c_str());
125
126 bg::svg_mapper<Point> mapper(svg, 500, 500);
127 mapper.add(p);
128 for (typename std::vector<bglt::turn_angle_info<Point> >::const_iterator it =
129 angles.begin(); it != angles.end(); ++it)
130 {
131 // Add a point further then it->to_point, just for the mapping
132 for (int i = 0; i < 2; i++)
133 {
134 mapper.add(further_than(it->points[i], p, 12, 10));
135 }
136 }
137
138 int color_index = 0;
139 typedef bg::model::referring_segment<Point const> segment_type;
140 for (typename std::vector<bglt::turn_angle_info<Point> >::const_iterator it =
141 angles.begin(); it != angles.end(); ++it, color_index++)
142 {
143 for (int i = 0; i < 2; i++)
144 {
145 std::string style = "opacity:0.5;stroke-width:1;stroke:rgb(0,0,0);fill:" + get_color(color_index);
146
147 bool const incoming = i == 0;
148 Point const& pf = incoming ? it->points[i] : p;
149 Point const& pt = incoming ? p : it->points[i];
150 vector_type v = pt;
151 bg::subtract_point(v, pf);
152
153 bg::divide_value(v, 10.0);
154
155 // Generate perpendicular vector to right-side
156 vector_type perpendicular;
157 bg::set<0>(perpendicular, bg::get<1>(v));
158 bg::set<1>(perpendicular, -bg::get<0>(v));
159
160 bg::model::ring<Point> ring;
161 ring.push_back(pf);
162 ring.push_back(pt);
163
164 // Extra point at 9/10
165 {
166 Point pe = pt;
167 bg::add_point(pe, perpendicular);
168 ring.push_back(pe);
169 }
170 {
171 Point pe = pf;
172 bg::add_point(pe, perpendicular);
173 ring.push_back(pe);
174 }
175 ring.push_back(pf);
176
177 mapper.map(ring, style);
178
179 segment_type s(pf, pt);
180 mapper.map(s, "opacity:0.9;stroke-width:4;stroke:rgb(0,0,0);");
181 }
182 }
183
184 // Output angles for left-turns
185 for (std::vector<bglt::left_turn>::const_iterator ltit =
186 seg_ids.begin(); ltit != seg_ids.end(); ++ltit)
187 {
188 for (typename std::vector<bglt::angle_info<Point> >::const_iterator sit =
189 sorted.begin(); sit != sorted.end(); ++sit, color_index++)
190 {
191 Point pf, pt;
192 int factor = 0;
193 if (sit->seg_id == ltit->from && sit->incoming)
194 {
195 pf = sit->point;
196 pt = p;
197 factor = -1; // left side
198 }
199 else if (sit->seg_id == ltit->to && ! sit->incoming)
200 {
201 pf = p;
202 pt = sit->point;
203 factor = -1; // left side
204 }
205 if (factor != 0)
206 {
207 vector_type v = pt;
208 bg::subtract_point(v, pf);
209 bg::divide_value(v, 10.0);
210
211 // Generate perpendicular vector to right-side
212 vector_type perpendicular;
213 bg::set<0>(perpendicular, factor * bg::get<1>(v));
214 bg::set<1>(perpendicular, -factor * bg::get<0>(v));
215
216 bg::add_point(pf, v);
217 bg::subtract_point(pt, v);
218
219 bg::add_point(pf, perpendicular);
220 bg::add_point(pt, perpendicular);
221
222 segment_type s(pf, pt);
223 mapper.map(s, "opacity:0.9;stroke-width:4;stroke:rgb(255,0,0);");
224 }
225 }
226 }
227
228 // Output texts with info about sorted/blocked
229 int index = 0;
230 for (typename std::vector<bglt::angle_info<Point> >::const_iterator it =
231 sorted.begin(); it != sorted.end(); ++it, ++index)
232 {
233 std::ostringstream out;
234 out << std::boolalpha;
235 out << " seg:" << it->seg_id.segment_index
236 << " " << (it->incoming ? "in" : "out")
237 << " idx:" << index
238 << (it->blocked ? " blocked" : "")
239 ;
240 mapper.text(further_than(it->point, p, 11, 10), out.str(), "fill:rgb(0,0,0);font-family='Verdana'");
241 }
242
243 mapper.map(p, "fill:rgb(255,0,0)");
244
245 }
246
247 #endif
248
249 }
250
251
252 template <typename P>
test_all()253 void test_all()
254 {
255 using bglt::turn_angle_info;
256
257 test_one<P>("cross",
258 bg::make<P>(50, 50), // ip
259 boost::assign::list_of
260 (turn_angle_info<P>(bg::segment_identifier(0, -1, -1, 1), bg::make<P>(100, 100), bg::make<P>(0, 0)))
261 (turn_angle_info<P>(bg::segment_identifier(0, -1, -1, 2), bg::make<P>(100, 0), bg::make<P>(0, 100)))
262 , "1-true 2-true 1-false 2-false"
263 , "2->1"
264 );
265
266 test_one<P>("occupied",
267 bg::make<P>(50, 50), // ip
268 boost::assign::list_of
269 (turn_angle_info<P>(bg::segment_identifier(0, -1, -1, 1), bg::make<P>(100, 100), bg::make<P>(0, 0)))
270 (turn_angle_info<P>(bg::segment_identifier(0, -1, -1, 2), bg::make<P>(100, 0), bg::make<P>(0, 100)))
271 (turn_angle_info<P>(bg::segment_identifier(0, -1, -1, 3), bg::make<P>(0, 30), bg::make<P>(100, 70)))
272 , "1-true 3-false 2-true 1-false 3-true 2-false"
273 , ""
274 );
275
276 test_one<P>("uu",
277 bg::make<P>(50, 50), // ip
278 boost::assign::list_of
279 (turn_angle_info<P>(bg::segment_identifier(0, -1, -1, 1), bg::make<P>(0, 0), bg::make<P>(100, 0)))
280 (turn_angle_info<P>(bg::segment_identifier(0, -1, -1, 2), bg::make<P>(100, 100), bg::make<P>(0, 100)))
281 , "2-true 1-false 1-true 2-false"
282 , "2->1 1->2"
283 );
284
285 test_one<P>("uu2",
286 bg::make<P>(50, 50), // ip
287 boost::assign::list_of
288 (turn_angle_info<P>(bg::segment_identifier(0, -1, -1, 1), bg::make<P>(0, 0), bg::make<P>(100, 0)))
289 (turn_angle_info<P>(bg::segment_identifier(0, -1, -1, 2), bg::make<P>(100, 100), bg::make<P>(0, 100)))
290 (turn_angle_info<P>(bg::segment_identifier(0, -1, -1, 3), bg::make<P>(0, 50), bg::make<P>(100, 50)))
291 , "2-true 3-false 1-false 1-true 3-true 2-false"
292 , "2->3 3->2"
293 );
294
295 test_one<P>("uu3",
296 bg::make<P>(50, 50), // ip
297 boost::assign::list_of
298 (turn_angle_info<P>(bg::segment_identifier(0, -1, -1, 1), bg::make<P>(0, 0), bg::make<P>(100, 0)))
299 (turn_angle_info<P>(bg::segment_identifier(0, -1, -1, 2), bg::make<P>(100, 100), bg::make<P>(0, 100)))
300 (turn_angle_info<P>(bg::segment_identifier(0, -1, -1, 3), bg::make<P>(50, 0), bg::make<P>(50, 100)))
301 , "3-false 2-true 1-false 3-true 1-true 2-false"
302 , "1->2"
303 );
304
305 test_one<P>("longer",
306 bg::make<P>(50, 50), // ip
307 boost::assign::list_of
308 (turn_angle_info<P>(bg::segment_identifier(0, -1, -1, 1), bg::make<P>(100, 100), bg::make<P>(0, 0)))
309 (turn_angle_info<P>(bg::segment_identifier(0, -1, -1, 2), bg::make<P>(100, 0), bg::make<P>(0, 100)))
310 (turn_angle_info<P>(bg::segment_identifier(0, -1, -1, 3), bg::make<P>(90, 10), bg::make<P>(10, 10)))
311 , "1-true 2-true 3-true 1-false 3-false 2-false"
312 , "3->1"
313 );
314 }
315
test_main(int,char * [])316 int test_main( int , char* [] )
317 {
318 test_all<bg::model::d2::point_xy<int> >();
319
320 return 0;
321 }
322