1 // Boost.Geometry
2 // Unit Test
3
4 // Copyright (c) 2017-2018, Oracle and/or its affiliates.
5
6 // Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle
7
8 // Licensed under the Boost Software License version 1.0.
9 // http://www.boost.org/users/license.html
10
11
12 #include <geometry_test_common.hpp>
13
14 #include <boost/geometry/geometries/geometries.hpp>
15
16 #include <boost/geometry/algorithms/densify.hpp>
17 #include <boost/geometry/algorithms/length.hpp>
18 #include <boost/geometry/algorithms/num_points.hpp>
19 #include <boost/geometry/algorithms/perimeter.hpp>
20
21 #include <boost/geometry/iterators/segment_iterator.hpp>
22
23 #include <boost/geometry/strategies/cartesian/densify.hpp>
24 #include <boost/geometry/strategies/cartesian/distance_pythagoras.hpp>
25 #include <boost/geometry/strategies/geographic/densify.hpp>
26 #include <boost/geometry/strategies/geographic/distance.hpp>
27 #include <boost/geometry/strategies/spherical/densify.hpp>
28 #include <boost/geometry/strategies/spherical/distance_haversine.hpp>
29
30 #include <boost/geometry/io/wkt/wkt.hpp>
31
32
33 struct check_lengths
34 {
35 template <typename G, typename S>
operator ()check_lengths36 void operator()(G const& g, G const& o, S const& s) const
37 {
38 double d1 = bg::length(g, s);
39 double d2 = bg::length(o, s);
40
41 BOOST_CHECK_CLOSE(d1, d2, 0.0001);
42 }
43 };
44
45 struct check_perimeters
46 {
47 template <typename G, typename S>
operator ()check_perimeters48 void operator()(G const& g, G const& o, S const& s) const
49 {
50 double d1 = bg::perimeter(g, s);
51 double d2 = bg::perimeter(o, s);
52
53 BOOST_CHECK_CLOSE(d1, d2, 0.0001);
54 }
55 };
56
57 template <typename G, typename DistS>
shortest_length(G const & g,DistS const & dist_s)58 double inline shortest_length(G const& g, DistS const& dist_s)
59 {
60 double min_len = (std::numeric_limits<double>::max)();
61 for (bg::segment_iterator<G const> it = bg::segments_begin(g);
62 it != bg::segments_end(g); ++it)
63 {
64 double len = bg::length(*it, dist_s);
65 min_len = (std::min)(min_len, len);
66 }
67 return min_len;
68 }
69
70 template <typename G, typename DistS>
greatest_length(G const & o,DistS const & dist_s)71 double inline greatest_length(G const& o, DistS const& dist_s)
72 {
73 double max_len = 0.0;
74 for (bg::segment_iterator<G const> it = bg::segments_begin(o);
75 it != bg::segments_end(o); ++it)
76 {
77 double len = bg::length(*it, dist_s);
78 max_len = (std::max)(max_len, len);
79 }
80 return max_len;
81 }
82
83 template <typename G, typename CSTag = typename bg::cs_tag<G>::type>
84 struct cs_data
85 {};
86
87 template <typename G>
88 struct cs_data<G, bg::cartesian_tag>
89 {
90 bg::strategy::densify::cartesian<> compl_s;
91 bg::strategy::distance::pythagoras<> dist_s;
92 };
93
94 template <typename G>
95 struct cs_data<G, bg::spherical_equatorial_tag>
96 {
cs_datacs_data97 cs_data()
98 : model(6378137.0)
99 , compl_s(model)
100 , dist_s(6378137.0)
101 {}
102
103 bg::srs::sphere<double> model;
104 bg::strategy::densify::spherical<> compl_s;
105 bg::strategy::distance::haversine<double> dist_s;
106 };
107
108 template <typename G>
109 struct cs_data<G, bg::geographic_tag>
110 {
cs_datacs_data111 cs_data()
112 : model(6378137.0, 6356752.3142451793)
113 , compl_s(model)
114 , dist_s(model)
115 {}
116
117 bg::srs::spheroid<double> model;
118 bg::strategy::densify::geographic<> compl_s;
119 bg::strategy::distance::geographic<> dist_s;
120 };
121
122 template <typename G, typename DistS, typename Check>
check_result(G const & g,G const & o,double max_distance,DistS const & dist_s,Check const & check)123 inline void check_result(G const& g, G const& o, double max_distance,
124 DistS const& dist_s, Check const& check)
125 {
126 // geometry was indeed densified
127 std::size_t g_count = bg::num_points(g);
128 std::size_t o_count = bg::num_points(o);
129 BOOST_CHECK(g_count < o_count);
130
131 // all segments have lengths smaller or equal to max_distance
132 double gr_len = greatest_length(o, dist_s);
133 // NOTE: Currently geographic strategies can generate segments that have
134 // lengths slightly greater than max_distance. In order to change
135 // this the generation of new points should e.g. be recursive with
136 // stop condition comparing the current distance calculated by
137 // inverse strategy.
138 // NOTE: Closeness value tweaked for Andoyer
139 bool is_close = (gr_len - max_distance) / (std::max)(gr_len, max_distance) < 0.0001;
140 BOOST_CHECK(gr_len <= max_distance || is_close);
141
142 // the overall length or perimeter didn't change
143 check(g, o, dist_s);
144 }
145
146 template <typename G, typename Check>
test_geometry(std::string const & wkt,Check const & check)147 inline void test_geometry(std::string const& wkt, Check const& check)
148 {
149 cs_data<G> d;
150
151 G g;
152 bg::read_wkt(wkt, g);
153
154 {
155 bg::default_strategy def_s;
156 double max_distance = shortest_length(g, def_s) / 3.0;
157
158 G o;
159 bg::densify(g, o, max_distance);
160
161 check_result(g, o, max_distance, def_s, check);
162 }
163
164 {
165 double max_distance = shortest_length(g, d.dist_s) / 3.0;
166
167 G o;
168 bg::densify(g, o, max_distance, d.compl_s);
169
170 check_result(g, o, max_distance, d.dist_s, check);
171 }
172 }
173
174 template <typename G>
test_linear(std::string const & wkt)175 inline void test_linear(std::string const& wkt)
176 {
177 test_geometry<G>(wkt, check_lengths());
178 }
179
180 template <typename G>
test_areal(std::string const & wkt)181 inline void test_areal(std::string const& wkt)
182 {
183 test_geometry<G>(wkt, check_perimeters());
184 }
185
186 template <typename P>
test_all()187 void test_all()
188 {
189 typedef bg::model::linestring<P> ls_t;
190 typedef bg::model::multi_linestring<ls_t> mls_t;
191
192 typedef bg::model::ring<P> ring_t;
193 typedef bg::model::polygon<P> poly_t;
194 typedef bg::model::multi_polygon<poly_t> mpoly_t;
195
196 typedef bg::model::ring<P, true, false> oring_t;
197 typedef bg::model::polygon<P, true, false> opoly_t;
198 typedef bg::model::multi_polygon<opoly_t> ompoly_t;
199
200 test_linear<ls_t>("LINESTRING(4 -4, 4 -1)");
201 test_linear<ls_t>("LINESTRING(4 4, 4 1)");
202 test_linear<ls_t>("LINESTRING(0 0, 180 0)");
203 test_linear<ls_t>("LINESTRING(1 1, -179 -1)");
204
205 test_linear<ls_t>("LINESTRING(1 1, 2 2, 4 2)");
206 test_linear<mls_t>("MULTILINESTRING((1 1, 2 2),(2 2, 4 2))");
207
208 test_areal<ring_t>("POLYGON((1 1, 1 2, 2 2, 1 1))");
209 test_areal<poly_t>("POLYGON((1 1, 1 4, 4 4, 4 1, 1 1),(1 1, 2 2, 2 3, 1 1))");
210 test_areal<mpoly_t>("MULTIPOLYGON(((1 1, 1 4, 4 4, 4 1, 1 1),(1 1, 2 2, 2 3, 1 1)),((4 4, 5 5, 5 4, 4 4)))");
211
212 test_areal<oring_t>("POLYGON((1 1, 1 2, 2 2))");
213 test_areal<opoly_t>("POLYGON((1 1, 1 4, 4 4, 4 1),(1 1, 2 2, 2 3))");
214 test_areal<ompoly_t>("MULTIPOLYGON(((1 1, 1 4, 4 4, 4 1),(1 1, 2 2, 2 3)),((4 4, 5 5, 5 4)))");
215
216 test_areal<ring_t>("POLYGON((0 0,0 40,40 40,40 0,0 0))");
217 test_areal<oring_t>("POLYGON((0 0,0 40,40 40,40 0))");
218 }
219
test_main(int,char * [])220 int test_main(int, char* [])
221 {
222 test_all< bg::model::point<double, 2, bg::cs::cartesian> >();
223 test_all< bg::model::point<double, 2, bg::cs::spherical_equatorial<bg::degree> > >();
224 test_all< bg::model::point<double, 2, bg::cs::geographic<bg::degree> > >();
225
226 return 0;
227 }
228