1 // Boost.Geometry (aka GGL, Generic Geometry Library)
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.
8 // Parts of Boost.Geometry are redesigned from Geodan's Geographic Library
9 // (geolib/GGL), copyright (c) 1995-2010 Geodan, Amsterdam, the Netherlands.
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)
18 #include <geometry_test_common.hpp>
20 #define BOOST_GEOMETRY_DEBUG_SEGMENT_IDENTIFIER
23 #include <boost/geometry/strategies/strategies.hpp>
25 #include <boost/geometry/algorithms/correct.hpp>
26 #include <boost/geometry/algorithms/detail/overlay/get_turns.hpp>
27 #include <boost/geometry/policies/robustness/get_rescale_policy.hpp>
29 #include <boost/geometry/algorithms/detail/overlay/debug_turn_info.hpp>
31 #include <boost/geometry/geometries/geometries.hpp>
33 #include <boost/geometry/io/wkt/read.hpp>
34 #include <boost/geometry/io/wkt/write.hpp>
36 #if defined(TEST_WITH_SVG)
37 # include <boost/geometry/io/svg/svg_mapper.hpp>
40 #include <algorithms/overlay/overlay_cases.hpp>
45 // To test that "get_turns" can be called using additional information
46 template <typename Point
, typename SegmentRatio
>
47 struct my_turn_op
: public bg::detail::overlay::turn_operation
<Point
, SegmentRatio
>
56 template<typename G1
, typename G2
>
57 static void apply(std::string
const& id
,
58 std::size_t expected_count
,
59 G1
const& g1
, G2
const& g2
, double /*precision*/)
61 typedef typename
bg::point_type
<G2
>::type point_type
;
62 typedef typename
bg::rescale_policy_type
<point_type
>::type
65 rescale_policy_type rescale_policy
66 = bg::get_rescale_policy
<rescale_policy_type
>(g1
, g2
);
68 typedef bg::detail::overlay::turn_info
71 typename
bg::segment_ratio_type
<point_type
, rescale_policy_type
>::type
73 std::vector
<turn_info
> turns
;
76 bg::detail::get_turns::no_interrupt_policy policy
;
77 bg::get_turns
<false, false, bg::detail::overlay::assign_null_policy
>(g1
, g2
, rescale_policy
, turns
, policy
);
80 expected_count
== boost::size(turns
),
82 << " #turns expected: " << expected_count
83 << " detected: " << boost::size(turns
)
84 << " type: " << string_from_type
85 <typename
bg::coordinate_type
<G1
>::type
>::name()
88 #if defined(TEST_WITH_SVG)
90 typedef typename
bg::coordinate_type
<G1
>::type coordinate_type
;
91 std::map
<std::pair
<coordinate_type
, coordinate_type
>, int> offsets
;
92 std::ostringstream filename
;
93 filename
<< "get_turns_" << id
94 << "_" << string_from_type
<typename
bg::coordinate_type
<G1
>::type
>::name()
97 std::ofstream
svg(filename
.str().c_str());
99 bg::svg_mapper
<typename
bg::point_type
<G2
>::type
> mapper(svg
, 500, 500);
103 // Input shapes in green/blue
104 mapper
.map(g1
, "fill-opacity:0.5;fill:rgb(153,204,0);"
105 "stroke:rgb(153,204,0);stroke-width:3");
106 mapper
.map(g2
, "fill-opacity:0.3;fill:rgb(51,51,153);"
107 "stroke:rgb(51,51,153);stroke-width:3");
110 BOOST_FOREACH(turn_info
const& turn
, turns
)
112 mapper
.map(turn
.point
, "fill:rgb(255,128,0);stroke:rgb(0,0,100);stroke-width:1");
114 // Map characteristics
115 std::pair
<coordinate_type
, coordinate_type
> p
116 = std::make_pair(bg::get
<0>(turn
.point
), bg::get
<1>(turn
.point
));
119 std::ostringstream out
;
121 << ": " << bg::operation_char(turn
.operations
[0].operation
)
122 << " " << bg::operation_char(turn
.operations
[1].operation
)
123 << " (" << bg::method_char(turn
.method
) << ")"
124 << (turn
.discarded
? " (discarded) " : turn
.blocked() ? " (blocked)" : "")
128 int offset
= offsets
[p
];
129 mapper
.text(turn
.point
, out
.str(),
130 "fill:rgb(0,0,0);font-family:Arial;font-size:8px",
143 template<typename G1
, typename G2
>
144 struct test_get_turns
146 inline static void apply(std::string
const& id
, std::size_t expected_count
,
147 std::string
const& wkt1
, std::string
const& wkt2
,
148 double precision
= 0.001)
150 if (wkt1
.empty() || wkt2
.empty())
156 bg::read_wkt(wkt1
, g1
);
159 bg::read_wkt(wkt2
, g2
);
164 // Try the overlay-function in both ways
165 std::string caseid
= id
;
166 //goto case_reversed;
168 #ifdef BOOST_GEOMETRY_DEBUG_INTERSECTION
169 std::cout
<< std::endl
<< std::endl
<< "# " << caseid
<< std::endl
;
171 detail::test_get_turns::apply(caseid
, expected_count
, g1
, g2
, precision
);
173 #ifdef BOOST_GEOMETRY_DEBUG_INTERSECTION
178 #if ! defined(BOOST_GEOMETRY_TEST_OVERLAY_NOT_EXCHANGED)
179 caseid
= id
+ "_rev";
180 #ifdef BOOST_GEOMETRY_DEBUG_INTERSECTION
181 std::cout
<< std::endl
<< std::endl
<< "# " << caseid
<< std::endl
;
184 detail::test_get_turns::apply(caseid
, expected_count
, g2
, g1
, precision
);
189 #if ! defined(GEOMETRY_TEST_MULTI)
190 template <typename T
>
193 typedef bg::model::point
<T
, 2, bg::cs::cartesian
> P
;
194 typedef bg::model::polygon
<P
> polygon
;
195 typedef bg::model::linestring
<P
> linestring
;
196 typedef bg::model::box
<P
> box
;
198 #ifdef BOOST_GEOMETRY_DEBUG_INTERSECTION
199 std::cout
<< string_from_type
<T
>::name() << std::endl
;
205 test_get_turns<polygon, polygon>::apply("snl_2",
208 //"POLYGON((182467 605842,182480 605954,182557 605958,182571 605958,182585 605958,182579 605843,182559 605838,182467 605842))",
209 //"POLYGON((182499 605955,182511 605960,182536 605974,182536 605981,182536 606006,182563 606006,182610 605985,182613 605976,182620 605948,182628 605937,182631 605924,182639 605889,182634 605885,182603 605848,182579 605843,182585 605958,182571 605958,182557 605958,182499 605955))");
211 //"POLYGON((120812 525783,120845 525792,120821 525842,120789 525826,120818 525849,120831 525854,120875 525875,120887 525881,120887 525881,120920 525834,120920 525834,120811 525772,120789 525826,120812 525783))",
212 //"POLYGON((120789 525826,120812 525783,120845 525792,120821 525842,120789 525826,120818 525849,120831 525854,120875 525875,120923 525836,120811 525772,120789 525826))"
214 "POLYGON((184913.4512400339881423860788345336914 606985.779408219968900084495544433594,184912.8999999999941792339086532592773 606987.145999999949708580970764160156,184904.4135310589917935431003570556641 606987.651360383024439215660095214844,184901.847619076987029984593391418457 607014.593436188995838165283203125,184916.3977574919990729540586471557617 607021.060164373018778860569000244141,184927.7147701499925460666418075561523 607008.126435620011761784553527832031,184926.0980706939881201833486557006836 606998.426238880958408117294311523438,184913.4512400339881423860788345336914 606985.779408219968900084495544433594),(184907.5560000000114087015390396118164 607013.300999999977648258209228515625,184905.7820000000065192580223083496094 607009.971999999950639903545379638672,184906.0039999999862629920244216918945 607005.978000000002793967723846435547,184908.4439999999885912984609603881836 606998.876999999978579580783843994141,184912.2149999999965075403451919555664 606994.217999999993480741977691650391,184919.3140000000130385160446166992188 606993.996000000042840838432312011719,184922.4200000000128056854009628295898 606995.770999999949708580970764160156,184925.7470000000030267983675003051758 606998.876999999978579580783843994141,184926.4130000000004656612873077392578 607002.871999999973922967910766601563,184925.7470000000030267983675003051758 607007.753000000026077032089233398438,184922.4200000000128056854009628295898 607012.190999999991618096828460693359,184917.0959999999904539436101913452148 607015.297999999951571226119995117188,184911.7710000000079162418842315673828 607015.297999999951571226119995117188,184907.5560000000114087015390396118164 607013.300999999977648258209228515625))",
215 "POLYGON((184861.1180000010062940418720245361328 606901.158000000054016709327697753906,184893.7870000000111758708953857421875 606898.482999998959712684154510498047,184925.0430000009946525096893310546875 606913.399999998975545167922973632813,184927.1739999990095384418964385986328 606951.758999999961815774440765380859,184912.8999999990046489983797073364258 606987.146000002045184373855590820313,184877.8700000010139774531126022338867 606989.232000001007691025733947753906,184885.1030000000027939677238464355469 607023.773999999975785613059997558594,184899.0579999980109278112649917602539 607022.743000000948086380958557128906,184906.0080000009911600500345230102539 607044.947999999043531715869903564453,184966.4649999999965075403451919555664 607025.020000000018626451492309570313,184968.4420000019890721887350082397461 606961.300000000977888703346252441406,185024.7679999989923089742660522460938 606947.401999998954124748706817626953,185024.5439999999944120645523071289063 606941.354999999981373548507690429688,185027.0069999989937059581279754638672 606937.322999999043531715869903564453,185030.3660000000090803951025009155273 606934.186999998986721038818359375,185035.5159999990137293934822082519531 606933.962999999988824129104614257813,185040.4420000019890721887350082397461 606935.530999999027699232101440429688,185042.905000000988366082310676574707 606939.114999998011626303195953369141,185088.3640000000013969838619232177734 606931.385000001988373696804046630859,185089.1389999990060459822416305541992 607015.508999999961815774440765380859,185095.1999999989930074661970138549805 607011.300000000977888703346252441406,185118.8269999999902211129665374755859 606995.545000002020969986915588378906,185126.813000001013278961181640625 606991.9950000010430812835693359375,185177.7270000019925646483898162841797 606973.798999998951330780982971191406,185181.4820000010076910257339477539063 606966.67599999904632568359375,185193.5709999990067444741725921630859 606977.795000002020969986915588378906,185193.710999998991610482335090637207 606960.300000000977888703346252441406,185189.3520000019925646483898162841797 606779.020000000018626451492309570313,185167.5150000010035000741481781005859 606783.844000000972300767898559570313,185086.9600000010104849934577941894531 606801.241000000038184225559234619141,185011.7069999990053474903106689453125 606817.809000000008381903171539306641,185000 606819.304000001051463186740875244141,184994.0340000019932631403207778930664 606819.793999999994412064552307128906,184976.3979999980074353516101837158203 606819.572000000975094735622406005859,184956.6539999989909119904041290283203 606817.1310000009834766387939453125,184934.9129999990109354257583618164063 606813.136999998008832335472106933594,184893.0969999989902134984731674194336 606804.927000000956468284130096435547,184884.4450000000069849193096160888672 606831.555000000051222741603851318359,184866.9189999999944120645523071289063 606883.480999998981133103370666503906,184861.1180000010062940418720245361328 606901.158000000054016709327697753906),(184907.5560000019904691725969314575195 607013.30099999904632568359375,184905.7820000019855797290802001953125 607009.971999999019317328929901123047,184906.0040000010048970580101013183594 607005.978000000002793967723846435547,184908.4439999980095308274030685424805 606998.876999999978579580783843994141,184912.2149999999965075403451919555664 606994.217999998014420270919799804688,184919.3139999989944044500589370727539 606993.995999998995102941989898681641,184922.420000001991866156458854675293 606995.771000002045184373855590820313,184925.7470000009925570338964462280273 606998.876999999978579580783843994141,184926.4129999990109354257583618164063 607002.872000001021660864353179931641,184925.7470000009925570338964462280273 607007.752999998978339135646820068359,184922.420000001991866156458854675293 607012.190999999991618096828460693359,184917.0960000010090880095958709716797 607015.297999999951571226119995117188,184911.7710000019869767129421234130859 607015.297999999951571226119995117188,184907.5560000019904691725969314575195 607013.30099999904632568359375))"
223 test_get_turns
<polygon
, polygon
>::apply("1", 6, case_1
[0], case_1
[1]);
224 test_get_turns
<polygon
, polygon
>::apply("2", 8, case_2
[0], case_2
[1]);
225 test_get_turns
<polygon
, polygon
>::apply("3", 4, case_3
[0], case_3
[1]);
226 test_get_turns
<polygon
, polygon
>::apply("4", 12, case_4
[0], case_4
[1]);
227 test_get_turns
<polygon
, polygon
>::apply("5", 17, case_5
[0], case_5
[1]);
228 test_get_turns
<polygon
, polygon
>::apply("6", 3, case_6
[0], case_6
[1]);
231 test_get_turns
<polygon
, polygon
>::apply("7", 2, case_7
[0], case_7
[1]);
232 test_get_turns
<polygon
, polygon
>::apply("8", 2, case_8
[0], case_8
[1]);
233 test_get_turns
<polygon
, polygon
>::apply("9", 1, case_9
[0], case_9
[1]);
234 test_get_turns
<polygon
, polygon
>::apply("10", 3, case_10
[0], case_10
[1]);
235 test_get_turns
<polygon
, polygon
>::apply("11", 1, case_11
[0], case_11
[1]);
236 test_get_turns
<polygon
, polygon
>::apply("12", 8, case_12
[0], case_12
[1]);
239 test_get_turns
<polygon
, polygon
>::apply("13", 2, case_13
[0], case_13
[1]);
240 test_get_turns
<polygon
, polygon
>::apply("14", 2, case_14
[0], case_14
[1]);
241 test_get_turns
<polygon
, polygon
>::apply("15", 2, case_15
[0], case_15
[1]);
242 test_get_turns
<polygon
, polygon
>::apply("16", 4, case_16
[0], case_16
[1]);
243 test_get_turns
<polygon
, polygon
>::apply("17", 2, case_17
[0], case_17
[1]);
244 ///test_get_turns<polygon, polygon>::apply("18", 4, case_18[0], case_18[1]);
247 test_get_turns
<polygon
, polygon
>::apply("19", 2, case_19
[0], case_19
[1]);
248 test_get_turns
<polygon
, polygon
>::apply("20", 3, case_20
[0], case_20
[1]);
249 test_get_turns
<polygon
, polygon
>::apply("21", 3, case_21
[0], case_21
[1]);
250 test_get_turns
<polygon
, polygon
>::apply("22", 1, case_22
[0], case_22
[1]);
251 test_get_turns
<polygon
, polygon
>::apply("23", 2, case_23
[0], case_23
[1]);
252 test_get_turns
<polygon
, polygon
>::apply("24", 1, case_24
[0], case_24
[1]);
255 test_get_turns
<polygon
, polygon
>::apply("25", 1, case_25
[0], case_25
[1]);
256 test_get_turns
<polygon
, polygon
>::apply("26", 1, case_26
[0], case_26
[1]);
257 test_get_turns
<polygon
, polygon
>::apply("27", 2, case_27
[0], case_27
[1]);
258 test_get_turns
<polygon
, polygon
>::apply("28", 2, case_28
[0], case_28
[1]);
259 test_get_turns
<polygon
, polygon
>::apply("29", 2, case_29
[0], case_29
[1]);
260 test_get_turns
<polygon
, polygon
>::apply("30", 2, case_30
[0], case_30
[1]);
263 test_get_turns
<polygon
, polygon
>::apply("31", 1, case_31
[0], case_31
[1]);
264 test_get_turns
<polygon
, polygon
>::apply("32", 1, case_32
[0], case_32
[1]);
265 test_get_turns
<polygon
, polygon
>::apply("33", 1, case_33
[0], case_33
[1]);
266 test_get_turns
<polygon
, polygon
>::apply("34", 2, case_34
[0], case_34
[1]);
267 test_get_turns
<polygon
, polygon
>::apply("35", 1, case_35
[0], case_35
[1]);
268 test_get_turns
<polygon
, polygon
>::apply("36", 3, case_36
[0], case_36
[1]);
271 test_get_turns
<polygon
, polygon
>::apply("37", 3, case_37
[0], case_37
[1]);
272 test_get_turns
<polygon
, polygon
>::apply("38", 3, case_38
[0], case_38
[1]);
273 test_get_turns
<polygon
, polygon
>::apply("39", 4, case_39
[0], case_39
[1]);
274 test_get_turns
<polygon
, polygon
>::apply("40", 3, case_40
[0], case_40
[1]);
275 test_get_turns
<polygon
, polygon
>::apply("41", 5, case_41
[0], case_41
[1]);
276 test_get_turns
<polygon
, polygon
>::apply("42", 5, case_42
[0], case_42
[1]);
279 test_get_turns
<polygon
, polygon
>::apply("43", 4, case_43
[0], case_43
[1]);
280 test_get_turns
<polygon
, polygon
>::apply("44", 4, case_44
[0], case_44
[1]);
281 test_get_turns
<polygon
, polygon
>::apply("45", 4, case_45
[0], case_45
[1]);
282 test_get_turns
<polygon
, polygon
>::apply("46", 4, case_46
[0], case_46
[1]);
283 test_get_turns
<polygon
, polygon
>::apply("47", 5, case_47
[0], case_47
[1]);
286 test_get_turns
<polygon
, polygon
>::apply("50", 4, case_50
[0], case_50
[1]);
287 test_get_turns
<polygon
, polygon
>::apply("51", 3, case_51
[0], case_51
[1]);
288 test_get_turns
<polygon
, polygon
>::apply("52", 8, case_52
[0], case_52
[1]);
289 // A touching point interior/ring exterior/ring can be represented in two ways:
290 test_get_turns
<polygon
, polygon
>::apply("53a", 4, case_53
[0], case_53
[1]);
291 test_get_turns
<polygon
, polygon
>::apply("53b", 4, case_53
[0], case_53
[2]);
292 test_get_turns
<polygon
, polygon
>::apply("54aa", 13, case_54
[0], case_54
[2]);
293 test_get_turns
<polygon
, polygon
>::apply("54ab", 13, case_54
[0], case_54
[3]);
294 test_get_turns
<polygon
, polygon
>::apply("54ba", 13, case_54
[1], case_54
[2]);
295 test_get_turns
<polygon
, polygon
>::apply("54bb", 13, case_54
[1], case_54
[3]);
297 test_get_turns
<polygon
, polygon
>::apply("55", 12, case_55
[0], case_55
[1]);
298 test_get_turns
<polygon
, polygon
>::apply("56", 9, case_56
[0], case_56
[1]);
302 test_get_turns
<polygon
, polygon
>::apply("many_situations", 31, case_many_situations
[0], case_many_situations
[1]);
306 test_get_turns
<polygon
, box
>::apply("ticket_17", 6, ticket_17
[0], ticket_17
[1]);
309 test_get_turns
<polygon
, polygon
>::apply("ggl_list_20110306_javier",
311 ggl_list_20110306_javier
[0], ggl_list_20110306_javier
[1]);
313 #ifdef _MSC_VER // gcc returns 14 for float
314 // test_get_turns<polygon, polygon>::apply("ggl_list_20110716_enrico",
316 // ggl_list_20110716_enrico[0], ggl_list_20110716_enrico[1]);
321 test_get_turns
<polygon
, polygon
>::apply("pie_23_16_16", 3, pie_23_16_16
[0], pie_23_16_16
[1]);
322 test_get_turns
<polygon
, polygon
>::apply("pie_16_4_12", 2, pie_16_4_12
[0], pie_16_4_12
[1]);
323 test_get_turns
<polygon
, polygon
>::apply("pie_4_13_15", 3, pie_4_13_15
[0], pie_4_13_15
[1]);
324 test_get_turns
<polygon
, polygon
>::apply("pie_16_2_15_0", 2, pie_16_2_15_0
[0], pie_16_2_15_0
[1]);
325 test_get_turns
<polygon
, polygon
>::apply("pie_20_20_7_100", 3, pie_20_20_7_100
[0], pie_20_20_7_100
[1]);
326 test_get_turns
<polygon
, polygon
>::apply("pie_23_23_3_2000", 5, pie_23_23_3_2000
[0], pie_23_23_3_2000
[1]);
330 test_get_turns
<linestring
, linestring
>::apply("lineline1", 3, line_line1
[0], line_line1
[1]);
333 test_get_turns
<linestring
, polygon
>::apply("line_poly1", 4, line_line1
[0], case_1
[1]);
334 test_get_turns
<linestring
, polygon
>::apply("line_poly2", 4, line_line1
[1], case_1
[0]);
335 test_get_turns
<polygon
, linestring
>::apply("poly_line", 4, case_1
[1], line_line1
[0]);
339 template <typename T
>
342 typedef bg::model::point
<T
, 2, bg::cs::cartesian
> P
;
343 typedef bg::model::polygon
<P
, false, true> polygon
;
345 test_get_turns
<polygon
, polygon
>::apply("ccw_1",
347 ccw_case_1
[0], ccw_case_1
[1]);
349 test_get_turns
<polygon
, polygon
>::apply("ccw_9",
351 case_9
[0], case_9
[1]);
355 template <typename T
>
358 typedef bg::model::point
<T
, 2, bg::cs::cartesian
> P
;
359 typedef bg::model::polygon
<P
, true, false> polygon
;
361 test_get_turns
<polygon
, polygon
>::apply("open_1",
363 open_case_1
[0], open_case_1
[1]);
365 test_get_turns
<polygon
, polygon
>::apply("open_9",
367 open_case_9
[0], open_case_9
[1]);
372 int test_main(int, char* [])
379 #if ! defined(_MSC_VER)
380 test_all
<long double>();
383 #if defined(HAVE_TTMATH)
384 test_all
<ttmath_big
>();