1 // Boost.Geometry (aka GGL, Generic Geometry Library)
2 // Unit Test
3
4 // Copyright (c) 2016 Barend Gehrels, Amsterdam, the Netherlands.
5 // Copyright (c) 2017 Adam Wulkiewicz, Lodz, Poland.
6
7 // This file was modified by Oracle on 2017, 2019.
8 // Modifications copyright (c) 2017, 2019, Oracle and/or its affiliates.
9 // Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle
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 <geometry_test_common.hpp>
16
17 #include <boost/geometry.hpp>
18 #include <boost/geometry/algorithms/detail/overlay/debug_turn_info.hpp>
19 #include <boost/geometry/geometries/geometries.hpp>
20 #include <boost/assign/list_of.hpp>
21 #include <boost/foreach.hpp>
22
23 #include "multi_overlay_cases.hpp"
24
25
26 namespace
27 {
28
29 template <typename T>
as_string(std::vector<T> const & v)30 std::string as_string(std::vector<T> const& v)
31 {
32 std::stringstream out;
33 bool first = true;
34 BOOST_FOREACH(T const& value, v)
35 {
36 out << (first ? "[" : " , ") << value;
37 first = false;
38 }
39 out << (first ? "" : "]");
40 return out.str();
41 }
42
43 }
44
45 // Adapted copy of handle_colocations::gather_cluster_properties
46 template
47 <
48 bool Reverse1, bool Reverse2,
49 bg::overlay_type OverlayType,
50 typename Clusters,
51 typename Turns,
52 typename Geometry1,
53 typename Geometry2,
54 typename SideStrategy
55 >
gather_cluster_properties(Clusters & clusters,Turns & turns,bg::detail::overlay::operation_type for_operation,Geometry1 const & geometry1,Geometry2 const & geometry2,SideStrategy const & strategy)56 std::vector<std::size_t> gather_cluster_properties(
57 Clusters& clusters, Turns& turns,
58 bg::detail::overlay::operation_type for_operation,
59 Geometry1 const& geometry1, Geometry2 const& geometry2,
60 SideStrategy const& strategy)
61 {
62 using namespace boost::geometry;
63 using namespace boost::geometry::detail::overlay;
64
65 std::vector<std::size_t> result;
66
67 typedef typename boost::range_value<Turns>::type turn_type;
68 typedef typename turn_type::point_type point_type;
69 typedef typename turn_type::turn_operation_type turn_operation_type;
70
71 // Define sorter, sorting counter-clockwise such that polygons are on the
72 // right side
73 typedef sort_by_side::side_sorter
74 <
75 Reverse1, Reverse2, OverlayType, point_type, SideStrategy, std::less<int>
76 > sbs_type;
77
78 for (typename Clusters::iterator mit = clusters.begin();
79 mit != clusters.end(); ++mit)
80 {
81 cluster_info& cinfo = mit->second;
82 std::set<signed_size_type> const& ids = cinfo.turn_indices;
83 if (ids.empty())
84 {
85 return result;
86 }
87
88 sbs_type sbs(strategy);
89 point_type turn_point; // should be all the same for all turns in cluster
90
91 bool first = true;
92 for (typename std::set<signed_size_type>::const_iterator sit = ids.begin();
93 sit != ids.end(); ++sit)
94 {
95 signed_size_type turn_index = *sit;
96 turn_type const& turn = turns[turn_index];
97 if (first)
98 {
99 turn_point = turn.point;
100 }
101 for (int i = 0; i < 2; i++)
102 {
103 turn_operation_type const& op = turn.operations[i];
104 sbs.add(op, turn_index, i, geometry1, geometry2, first);
105 first = false;
106 }
107 }
108 sbs.apply(turn_point);
109
110 sbs.find_open();
111 sbs.assign_zones(for_operation);
112
113 cinfo.open_count = sbs.open_count(for_operation);
114 result.push_back(cinfo.open_count);
115 }
116 return result;
117 }
118
119
120 // Adapted copy of overlay::apply
121 template
122 <
123 bg::overlay_type OverlayType,
124 bool Reverse1, bool Reverse2, bool ReverseOut,
125 typename GeometryOut,
126 typename Geometry1, typename Geometry2,
127 typename RobustPolicy, typename Strategy
128 >
apply_overlay(Geometry1 const & geometry1,Geometry2 const & geometry2,RobustPolicy const & robust_policy,Strategy const & strategy)129 std::vector<std::size_t> apply_overlay(
130 Geometry1 const& geometry1, Geometry2 const& geometry2,
131 RobustPolicy const& robust_policy,
132 Strategy const& strategy)
133 {
134 using namespace boost::geometry;
135
136 typedef typename bg::point_type<GeometryOut>::type point_type;
137 typedef bg::detail::overlay::traversal_turn_info
138 <
139 point_type,
140 typename bg::detail::segment_ratio_type<point_type, RobustPolicy>::type
141 > turn_info;
142 typedef std::deque<turn_info> turn_container_type;
143
144 // Define the clusters, mapping cluster_id -> turns
145 typedef std::map
146 <
147 signed_size_type,
148 bg::detail::overlay::cluster_info
149 > cluster_type;
150
151 turn_container_type turns;
152
153 detail::get_turns::no_interrupt_policy policy;
154 bg::get_turns
155 <
156 Reverse1, Reverse2,
157 detail::overlay::assign_null_policy
158 >(geometry1, geometry2, strategy, robust_policy, turns, policy);
159
160 cluster_type clusters;
161
162 bg::enrich_intersection_points<Reverse1, Reverse2, OverlayType>(turns,
163 clusters, geometry1, geometry2, robust_policy, strategy);
164
165 // Gather cluster properties, with test option
166 return ::gather_cluster_properties<Reverse1, Reverse2, OverlayType>(
167 clusters, turns, bg::detail::overlay::operation_from_overlay<OverlayType>::value,
168 geometry1, geometry2, strategy.get_side_strategy());
169 }
170
171
172 template <typename Geometry, bg::overlay_type OverlayType>
test_sort_by_side(std::string const & case_id,std::string const & wkt1,std::string const & wkt2,std::vector<std::size_t> const & expected_open_count)173 void test_sort_by_side(std::string const& case_id,
174 std::string const& wkt1, std::string const& wkt2,
175 std::vector<std::size_t> const& expected_open_count)
176 {
177 // std::cout << case_id << std::endl;
178
179 Geometry g1;
180 bg::read_wkt(wkt1, g1);
181
182 Geometry g2;
183 bg::read_wkt(wkt2, g2);
184
185 // Reverse if necessary
186 bg::correct(g1);
187 bg::correct(g2);
188
189 typedef typename boost::range_value<Geometry>::type geometry_out;
190
191 typedef typename bg::rescale_overlay_policy_type
192 <
193 Geometry,
194 Geometry
195 >::type rescale_policy_type;
196
197 rescale_policy_type robust_policy
198 = bg::get_rescale_policy<rescale_policy_type>(g1, g2);
199
200 typedef typename bg::strategy::intersection::services::default_strategy
201 <
202 typename bg::cs_tag<Geometry>::type
203 >::type strategy_type;
204
205 strategy_type strategy;
206
207 std::vector<std::size_t> result = ::apply_overlay
208 <
209 OverlayType, false, false, false, geometry_out
210 >(g1, g2, robust_policy, strategy);
211
212 BOOST_CHECK_MESSAGE(result == expected_open_count,
213 " caseid=" << case_id
214 << " open count: expected=" << as_string(expected_open_count)
215 << " detected=" << as_string(result));
216 }
217
218
219 // Define two small macro's to avoid repetitions of testcases/names etc
220 #define TEST_INT(caseid, exp) { (test_sort_by_side<multi_polygon, bg::overlay_intersection>) \
221 ( #caseid "_int", caseid[0], caseid[1], exp); }
222
223 #define TEST_UNION(caseid, exp) { (test_sort_by_side<multi_polygon, bg::overlay_union>) \
224 ( #caseid "_union", caseid[0], caseid[1], exp); }
225
226 using boost::assign::list_of;
227
228 template <typename T>
test_all()229 void test_all()
230 {
231 typedef bg::model::point<T, 2, bg::cs::cartesian> point_type;
232 typedef bg::model::polygon<point_type> polygon;
233 typedef bg::model::multi_polygon<polygon> multi_polygon;
234
235 // Selection of test cases having only one cluster
236
237 TEST_INT(case_64_multi, list_of(1));
238 TEST_INT(case_72_multi, list_of(3));
239 TEST_INT(case_107_multi, list_of(2));
240 TEST_INT(case_123_multi, list_of(3));
241 TEST_INT(case_124_multi, list_of(3));
242 TEST_INT(case_recursive_boxes_10, list_of(2));
243 TEST_INT(case_recursive_boxes_20, list_of(2));
244 TEST_INT(case_recursive_boxes_21, list_of(1));
245 TEST_INT(case_recursive_boxes_22, list_of(0));
246
247 TEST_UNION(case_recursive_boxes_46, list_of(2)(1)(2)(1)(1)(2)(1));
248
249 TEST_UNION(case_62_multi, list_of(2));
250 TEST_UNION(case_63_multi, list_of(2));
251 TEST_UNION(case_64_multi, list_of(1));
252 TEST_UNION(case_107_multi, list_of(1));
253 TEST_UNION(case_123_multi, list_of(1));
254 TEST_UNION(case_124_multi, list_of(1));
255 TEST_UNION(case_recursive_boxes_10, list_of(1));
256 TEST_UNION(case_recursive_boxes_18, list_of(3));
257 TEST_UNION(case_recursive_boxes_19, list_of(3));
258 TEST_UNION(case_recursive_boxes_20, list_of(2));
259 TEST_UNION(case_recursive_boxes_21, list_of(1));
260 TEST_UNION(case_recursive_boxes_22, list_of(1));
261 TEST_UNION(case_recursive_boxes_23, list_of(3));
262 }
263
test_main(int,char * [])264 int test_main(int, char* [])
265 {
266 test_all<double>();
267 return 0;
268 }
269