1 // Boost.Geometry (aka GGL, Generic Geometry Library)
2 // Unit Test
3
4 // Copyright (c) 2007-2012 Barend Gehrels, Amsterdam, the Netherlands.
5 // Copyright (c) 2008-2012 Bruno Lalande, Paris, France.
6 // Copyright (c) 2009-2012 Mateusz Loskot, London, UK.
7
8 // Parts of Boost.Geometry are redesigned from Geodan's Geographic Library
9 // (geolib/GGL), copyright (c) 1995-2010 Geodan, Amsterdam, the Netherlands.
10
11 // Use, modification and distribution is subject to the Boost Software License,
12 // Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
13 // http://www.boost.org/LICENSE_1_0.txt)
14
15 #include <iostream>
16 #include <string>
17
18 #include <geometry_test_common.hpp>
19
20 #include <boost/geometry/algorithms/make.hpp>
21 #include <boost/geometry/algorithms/num_points.hpp>
22 #include <boost/geometry/algorithms/detail/sections/sectionalize.hpp>
23 #include <boost/geometry/geometries/geometries.hpp>
24 #include <boost/geometry/geometries/point_xy.hpp>
25 #include <boost/geometry/io/wkt/read.hpp>
26 #include <boost/geometry/io/wkt/write.hpp>
27
28
29 #include <test_common/test_point.hpp>
30
31 #if defined(TEST_WITH_SVG)
32 # include <boost/geometry/io/svg/svg_mapper.hpp>
33 # include <boost/geometry/algorithms/buffer.hpp>
34 # include <boost/geometry/algorithms/centroid.hpp>
35 #endif
36
37 template <int DimensionCount, typename Geometry>
test_sectionalize_part()38 void test_sectionalize_part()
39 {
40 typedef typename bg::point_type<Geometry>::type point_type;
41 typedef bg::model::box<point_type> box_type;
42
43 typedef bg::sections<box_type, DimensionCount> sections_type;
44 typedef typename boost::range_value<sections_type>::type section_type;
45
46 typedef boost::mpl::vector_c<std::size_t, 0> dimension_list;
47
48 typedef bg::detail::sectionalize::sectionalize_part
49 <
50 point_type, dimension_list
51 > sectionalize_part;
52
53 sections_type sections;
54 section_type section;
55
56
57 Geometry geometry;
58 geometry.push_back(bg::make<point_type>(1, 1));
59
60 bg::detail::no_rescale_policy rescale_policy;
61
62 bg::ring_identifier ring_id;
63 sectionalize_part::apply(sections, geometry.begin(), geometry.end(), rescale_policy, ring_id, 10);
64 // There should not yet be anything generated, because it is only ONE point
65
66 geometry.push_back(bg::make<point_type>(2, 2));
67 sectionalize_part::apply(sections, geometry.begin(), geometry.end(), rescale_policy, ring_id, 10);
68 }
69
70
71 template <typename DimensionVector, bool Reverse, typename G>
test_sectionalize(std::string const & caseid,G const & g,std::size_t section_count,std::string const & index_check,std::string const & dir_check,std::size_t max_count=10)72 void test_sectionalize(std::string const& caseid, G const& g, std::size_t section_count,
73 std::string const& index_check, std::string const& dir_check,
74 std::size_t max_count = 10)
75 {
76 boost::ignore_unused(caseid);
77
78 static const std::size_t dimension_count = boost::mpl::size<DimensionVector>::value;
79
80
81 typedef typename bg::point_type<G>::type point;
82 typedef bg::model::box<point> box;
83 typedef bg::sections<box, dimension_count> sections;
84
85 sections s;
86 bg::sectionalize<Reverse, DimensionVector>(g,
87 bg::detail::no_rescale_policy(), s, 0, max_count);
88
89 BOOST_CHECK_EQUAL(s.size(), section_count);
90
91 // Check if sections are consecutive and consistent
92 int previous_index = -1;
93 BOOST_FOREACH(typename sections::value_type const& sec, s)
94 {
95 if (sec.begin_index > 0)
96 {
97 BOOST_CHECK_EQUAL(previous_index, sec.begin_index);
98 }
99 BOOST_CHECK_EQUAL(int(sec.count), int(sec.end_index - sec.begin_index));
100 previous_index = sec.end_index;
101 }
102
103 // Output streams for sections, boxes, other
104 std::ostringstream out_sections;
105 std::ostringstream out_boxes;
106 std::ostringstream out_dirs;
107
108
109 for (typename sections::size_type i = 0; i < s.size(); i++)
110 {
111 box const& b = s[i].bounding_box;
112
113 if (i > 0)
114 {
115 out_sections << "|";
116 out_dirs << "|";
117 out_boxes << "|";
118 }
119
120 out_sections << s[i].begin_index << ".." << s[i].end_index;
121 out_boxes << bg::get<0,0>(b) << " " << bg::get<0,1>(b)
122 << ".." << bg::get<1,0>(b) << " " << bg::get<1,1>(b);
123 for (std::size_t d = 0; d < dimension_count; d++)
124 {
125 out_dirs << (d == 0 ? "" : " ");
126 switch(s[i].directions[d])
127 {
128 case -99: out_dirs << "DUP"; break;
129 case -1 : out_dirs << "-"; break;
130 case 0 : out_dirs << "."; break;
131 case +1 : out_dirs << "+"; break;
132 }
133 }
134 }
135
136 if (! index_check.empty())
137 {
138 BOOST_CHECK_EQUAL(out_sections.str(), index_check);
139 }
140 if (! dir_check.empty())
141 {
142 BOOST_CHECK_EQUAL(out_dirs.str(), dir_check);
143 }
144
145 #if defined(TEST_WITH_SVG)
146 {
147 std::ostringstream filename;
148 filename << "sectionalize_"
149 << caseid << ".svg";
150
151 std::ofstream svg(filename.str().c_str());
152
153 typedef typename bg::point_type<G>::type point_type;
154 bg::svg_mapper<point_type> mapper(svg, 500, 500);
155
156 mapper.add(g);
157
158 static const bool is_line = bg::geometry_id<G>::type::value == 2;
159 mapper.map(g, is_line
160 ? "opacity:0.6;stroke:rgb(0,0,255);stroke-width:5"
161 : "opacity:0.6;fill:rgb(0,0,255);stroke:rgb(0,0,0);stroke-width:0.5");
162
163
164 for (typename sections::size_type i = 0; i < s.size(); i++)
165 {
166 box b = s[i].bounding_box;
167 bg::buffer(b, b, 0.01);
168 mapper.map(b, s[i].duplicate
169 ? "fill-opacity:0.4;stroke-opacity:0.6;fill:rgb(0,128,0);stroke:rgb(0,255,0);stroke-width:2.0"
170 : "fill-opacity:0.2;stroke-opacity:0.4;fill:rgb(255,0,0);stroke:rgb(255,0,0);stroke-width:0.5");
171
172 std::ostringstream out;
173
174 for (int d = 0; d < dimension_count; d++)
175 {
176 out << (d == 0 ? "[" : " ");
177 switch(s[i].directions[d])
178 {
179 case -99: out << "DUP"; break;
180 case -1 : out << "-"; break;
181 case 0 : out << "."; break;
182 case +1 : out << "+"; break;
183 }
184 }
185 out << "] " << s[i].begin_index << ".." << s[i].end_index;
186
187
188 point_type p;
189 bg::centroid(b, p);
190 mapper.text(p, out.str(), "");
191 }
192 }
193 #endif
194
195 }
196
197 template <typename G, bool Reverse>
test_sectionalize(std::string const & caseid,std::string const & wkt,std::size_t count2,std::string const & s2,std::string const d2,std::size_t count1,std::string const & s1,std::string const d1,std::size_t max_count=10)198 void test_sectionalize(std::string const& caseid, std::string const& wkt,
199 std::size_t count2, std::string const& s2, std::string const d2,
200 std::size_t count1, std::string const& s1, std::string const d1,
201 std::size_t max_count = 10)
202 {
203 G g;
204 bg::read_wkt(wkt, g);
205
206 typedef boost::mpl::vector_c<std::size_t, 0, 1> dim2;
207 typedef boost::mpl::vector_c<std::size_t, 0> dim1;
208
209 test_sectionalize<dim2, Reverse>(caseid + "_d2", g, count2, s2, d2, max_count);
210 test_sectionalize<dim1, Reverse>(caseid + "_d1", g, count1, s1, d1, max_count);
211 }
212
213 template <typename P>
test_all()214 void test_all()
215 {
216 test_sectionalize_part<1, bg::model::linestring<P> >();
217
218 test_sectionalize<bg::model::linestring<P>, false>("ls",
219 "LINESTRING(1 1,2 2,3 0,5 0,5 8)",
220 4, "0..1|1..2|2..3|3..4", "+ +|+ -|+ .|. +",
221 2, "0..3|3..4", "+|.");
222
223 // These strings mean:
224 // 0..1|1..2 -> first section: [0, 1] | second section [1, 2], etc
225 // + +|+ - -> X increases, Y increases | X increases, Y decreases
226 // +|. -> (only X considered) X increases | X constant
227
228 test_sectionalize<bg::model::polygon<P>, false>("simplex",
229 "POLYGON((0 0,0 7,4 2,2 0,0 0))",
230 4, "0..1|1..2|2..3|3..4", ". +|+ -|- -|- .",
231 // . + - - -> 3 sections
232 3, "0..1|1..2|2..4", ".|+|-");
233
234 // CCW polygon - orientation is not (always) relevant for sections,
235 // they are just generated in the order they come.
236 test_sectionalize<bg::model::polygon<P, false>, false>("simplex_ccw",
237 "POLYGON((0 0,2 0,4 2,0 7,0 0))",
238 4, "0..1|1..2|2..3|3..4", "+ .|+ +|- +|. -",
239 // . + - - -> 3 sections
240 3, "0..2|2..3|3..4", "+|-|.");
241
242 // Open polygon - closeness IS relevant for sections, the
243 // last section which is not explicit here should be included.
244 // So results are the same as the pre-previous one.
245 test_sectionalize<bg::model::polygon<P, true, false>, false>("simplex_open",
246 "POLYGON((0 0,0 7,4 2,2 0))",
247 4, "0..1|1..2|2..3|3..4", ". +|+ -|- -|- .",
248 // . + - - -> 3 sections
249 3, "0..1|1..2|2..4", ".|+|-");
250
251 test_sectionalize<bg::model::polygon<P>, false>("first",
252 "polygon((2.0 1.3, 2.4 1.7, 2.8 1.8, 3.4 1.2, 3.7 1.6,3.4 2.0, 4.1 3.0, 5.3 2.6, 5.4 1.2, 4.9 0.8, 2.9 0.7,2.0 1.3))",
253 8, "0..2|2..3|3..4|4..5|5..6|6..8|8..10|10..11", "+ +|+ -|+ +|- +|+ +|+ -|- -|- +",
254 4, "0..4|4..5|5..8|8..11", "+|-|+|-");
255
256 test_sectionalize<bg::model::polygon<P, false>, true>("first_reverse",
257 "polygon((2.0 1.3, 2.4 1.7, 2.8 1.8, 3.4 1.2, 3.7 1.6,3.4 2.0, 4.1 3.0, 5.3 2.6, 5.4 1.2, 4.9 0.8, 2.9 0.7,2.0 1.3))",
258 8, "0..1|1..3|3..5|5..6|6..7|7..8|8..9|9..11", "+ -|+ +|- +|- -|+ -|- -|- +|- -",
259 4, "0..3|3..6|6..7|7..11", "+|-|+|-");
260
261 test_sectionalize<bg::model::polygon<P>, false>("second",
262 "POLYGON((3 1,2 2,1 3,2 4,3 5,4 4,5 3,4 2,3 1))",
263 4, "0..2|2..4|4..6|6..8", "- +|+ +|+ -|- -",
264 // - - - + + + + - - -> 3 sections
265 3, "0..2|2..6|6..8", "-|+|-");
266
267 // With holes
268 test_sectionalize<bg::model::polygon<P>, false>("with_holes",
269 "POLYGON((3 1,2 2,1 3,2 4,3 5,4 4,5 3,4 2,3 1), (3 2,2 2,3 4,3 2))",
270 7, "0..2|2..4|4..6|6..8|0..1|1..2|2..3", "- +|+ +|+ -|- -|- .|+ +|. -",
271 // - - - + + + + - - - + . -> 6 sections
272 6, "0..2|2..6|6..8|0..1|1..2|2..3", "-|+|-|-|+|.");
273
274 // With duplicates
275 test_sectionalize<bg::model::linestring<P>, false>("with_dups",
276 "LINESTRING(1 1,2 2,3 0,3 0,5 0,5 8)",
277 5, "0..1|1..2|2..3|3..4|4..5", "+ +|+ -|DUP DUP|+ .|. +",
278 4, "0..2|2..3|3..4|4..5", "+|DUP|+|.");
279 // With two subsequent duplicate segments
280 test_sectionalize<bg::model::linestring<P>, false>("with_subseq_dups",
281 "LINESTRING(1 1,2 2,3 0,3 0,3 0,5 0,5 0,5 0,5 0,5 8)",
282 6, "0..1|1..2|2..4|4..5|5..8|8..9", "+ +|+ -|DUP DUP|+ .|DUP DUP|. +",
283 5, "0..2|2..4|4..5|5..8|8..9", "+|DUP|+|DUP|.");
284
285
286 typedef bg::model::box<P> B;
287 test_sectionalize<B, false>("box2", "BOX(0 0,4 4)",
288 4, "0..1|1..2|2..3|3..4", ". +|+ .|. -|- .",
289 4, "0..1|1..2|2..3|3..4", ".|+|.|-");
290
291 std::string horizontal("POLYGON((0 10,1 8,2 10,3 8,4 10,5 8,6 10,7 8,8 10,9 8,10 10,11 8,12 10,12 5,9 5,9 4,8 4,8 5,7 5,7 4,6 4,6 5,5 5,5 4,4 4,4 5,3 5,3 4,2 4,2 5,1 5,1 4,0 4,0 10))");
292 test_sectionalize<bg::model::polygon<P>, false>("horizontal", horizontal,
293 33, "", "",
294 22, "", "", 100);
295 test_sectionalize<bg::model::polygon<P>, false>("horizontal4", horizontal,
296 33, "", "",
297 24, "", "", 4);
298
299 std::string vertical("POLYGON((4 0,6 1,4 2,6 3,4 4,6 5,4 6,6 7,4 8,6 9,4 10,10 10,10 9,9 9,9 8,10 8,10 7,9 7,9 6,10 6,10 5,9 5,9 4,10 4,10 3,9 3,9 2,10 2,10 1,9 1,9 0,5 0))");
300 test_sectionalize<bg::model::polygon<P>, false>("vertical", vertical,
301 31, "", "",
302 31, "", "", 100);
303
304 {
305 typedef boost::mpl::vector_c<std::size_t, 1> only_y_dim;
306 bg::model::polygon<P> pol;
307 bg::read_wkt(vertical, pol);
308 test_sectionalize<only_y_dim, false>("vertical_y", pol, 22, "", "", 100);
309 }
310
311 return;
312 // Buffer-case
313 test_sectionalize<bg::model::polygon<P>, false>("buffer",
314 "POLYGON((-1.1713 0.937043,2.8287 5.93704,2.90334 6.02339,2.98433 6.10382,2.98433 6.10382,3.07121 6.17786,3.16346 6.24507,3.16346 6.24507,3.16346 6.24507,3.26056 6.30508,3.36193 6.35752,3.36193 6.35752,3.46701 6.40211,3.57517 6.43858,3.57517 6.43858,3.57517 6.43858,3.57517 6.43858,3.68579 6.46672,3.79822 6.48637,3.79822 6.48637,3.91183 6.49741,4.02595 6.49978,4.02595 6.49978,4.02595 6.49978,4.13991 6.49346,4.25307 6.4785,4.25307 6.4785,4.36476 6.45497,4.47434 6.42302,4.47434 6.42302,4.47434 6.42302,4.47434 6.42302,7.47434 5.42302,6.84189 3.52566,4.39043 4.68765,0.390434 -0.312348,-1.1713 0.937043))",
315 8, "0..2|2..3|3..4|4..5|5..6|6..8|8..10|10..11", "+ +|+ -|+ +|- +|+ +|+ -|- -|- +",
316 4, "0..4|4..5|5..8|8..11", "+|-|+|-");
317 }
318
test_large_integers()319 void test_large_integers()
320 {
321 typedef bg::model::point<int, 2, bg::cs::cartesian> int_point_type;
322 typedef bg::model::point<double, 2, bg::cs::cartesian> double_point_type;
323
324 std::string const polygon_li = "POLYGON((1872000 528000,1872000 192000,1536119 192000,1536000 528000,1200000 528000,1200000 863880,1536000 863880,1872000 863880,1872000 528000))";
325 bg::model::polygon<int_point_type> int_poly;
326 bg::model::polygon<double_point_type> double_poly;
327 bg::read_wkt(polygon_li, int_poly);
328 bg::read_wkt(polygon_li, double_poly);
329
330 typedef boost::mpl::vector_c<std::size_t, 0> dimensions;
331 bg::sections<bg::model::box<int_point_type>, 1> int_sections;
332 bg::sections<bg::model::box<double_point_type>, 1> double_sections;
333
334
335 bg::sectionalize<false, dimensions>(int_poly, bg::detail::no_rescale_policy(), int_sections);
336 bg::sectionalize<false, dimensions>(double_poly, bg::detail::no_rescale_policy(), double_sections);
337
338 bool equally_sized = int_sections.size() == double_sections.size();
339 BOOST_CHECK(equally_sized);
340 if (! equally_sized)
341 {
342 return;
343 }
344
345 for (unsigned int i = 0; i < int_sections.size(); i++)
346 {
347 BOOST_CHECK(int_sections[i].begin_index == double_sections[i].begin_index);
348 BOOST_CHECK(int_sections[i].count == double_sections[i].count);
349 }
350
351 }
352
353
354
test_main(int,char * [])355 int test_main(int, char* [])
356 {
357 test_large_integers();
358
359 //test_all<bg::model::d2::point_xy<float> >();
360 test_all<bg::model::d2::point_xy<double> >();
361
362 return 0;
363 }
364