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-2021.
8// Modifications copyright (c) 2017-2021, 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/algorithms/correct.hpp>
18#include <boost/geometry/algorithms/detail/overlay/debug_turn_info.hpp>
19#include <boost/geometry/algorithms/detail/overlay/overlay.hpp>
20#include <boost/geometry/geometries/geometries.hpp>
21#include <boost/geometry/io/wkt/read.hpp>
22
23#include "multi_overlay_cases.hpp"
24
25
26namespace
27{
28
29template <typename T>
30std::string as_string(std::vector<T> const& v)
31{
32 std::stringstream out;
33 bool first = true;
34 for (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
46template
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 Strategy
55>
56std::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 Strategy 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, Strategy, 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(turn, 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(x: cinfo.open_count);
115 }
116 return result;
117}
118
119
120// Adapted copy of overlay::apply
121template
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>
129std::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);
169}
170
171
172template <typename Geometry, bg::overlay_type OverlayType>
173void 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::strategies::relate::services::default_strategy
201 <
202 Geometry, Geometry
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_INTER(caseid, ...) { (test_sort_by_side<multi_polygon, bg::overlay_intersection>) \
221 ( #caseid "_inter", caseid[0], caseid[1], __VA_ARGS__); }
222
223#define TEST_UNION(caseid, ...) { (test_sort_by_side<multi_polygon, bg::overlay_union>) \
224 ( #caseid "_union", caseid[0], caseid[1], __VA_ARGS__); }
225
226template <typename T>
227void test_all()
228{
229 typedef bg::model::point<T, 2, bg::cs::cartesian> point_type;
230 typedef bg::model::polygon<point_type> polygon;
231 typedef bg::model::multi_polygon<polygon> multi_polygon;
232
233 // Selection of test cases having only one cluster
234
235 TEST_INTER(case_64_multi, {1});
236 TEST_INTER(case_72_multi, {3});
237 TEST_INTER(case_107_multi, {2});
238 TEST_INTER(case_123_multi, {3});
239 TEST_INTER(case_124_multi, {3});
240 TEST_INTER(case_recursive_boxes_10, {2});
241 TEST_INTER(case_recursive_boxes_20, {2});
242 TEST_INTER(case_recursive_boxes_21, {1});
243 TEST_INTER(case_recursive_boxes_22, {0});
244
245 TEST_UNION(case_recursive_boxes_46, {2, 1, 2, 1, 1, 2, 1});
246
247 TEST_UNION(case_62_multi, {2});
248 TEST_UNION(case_63_multi, {2});
249 TEST_UNION(case_64_multi, {1});
250 TEST_UNION(case_107_multi, {1});
251 TEST_UNION(case_123_multi, {1});
252 TEST_UNION(case_124_multi, {1});
253 TEST_UNION(case_recursive_boxes_10, {1});
254 TEST_UNION(case_recursive_boxes_18, {3});
255 TEST_UNION(case_recursive_boxes_19, {3});
256 TEST_UNION(case_recursive_boxes_20, {2});
257 TEST_UNION(case_recursive_boxes_21, {1});
258 TEST_UNION(case_recursive_boxes_22, {1});
259 TEST_UNION(case_recursive_boxes_23, {3});
260}
261
262int test_main(int, char* [])
263{
264 test_all<double>();
265 return 0;
266}
267

source code of boost/libs/geometry/test/algorithms/overlay/sort_by_side.cpp