1// Boost.Geometry (aka GGL, Generic Geometry Library)
2// Unit Test
3
4// Copyright (c) 2007-2012 Barend Gehrels, Amsterdam, the Netherlands.
5// Use, modification and distribution is subject to the Boost Software License,
6// Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
7// http://www.boost.org/LICENSE_1_0.txt)
8
9#ifndef BOOST_GEOMETRY_TEST_OVERLAY_HPP
10#define BOOST_GEOMETRY_TEST_OVERLAY_HPP
11
12#include <string>
13
14// 1. (Example) testcases
15static std::string example_box = "box(1.5 1.5, 4.5 2.5)";
16
17static std::string example_polygon =
18 "POLYGON((2 1.3,2.4 1.7,2.8 1.8,3.4 1.2,3.7 1.6,3.4 2,4.1 3,5.3 2.6,5.4 1.2,4.9 0.8,2.9 0.7,2 1.3)"
19 "(4.0 2.0, 4.2 1.4, 4.8 1.9, 4.4 2.2, 4.0 2.0))";
20
21static std::string example_ring =
22 "POLYGON((2 1.3,2.4 1.7,2.8 1.8,3.4 1.2,3.7 1.6,3.4 2,4.1 3,5.3 2.6,5.4 1.2,4.9 0.8,2.9 0.7,2 1.3))";
23
24static std::string example_star =
25 "POLYGON((4.0 -0.5 , 3.5 1.0 , 2.0 1.5 , 3.5 2.0 , 4.0 3.5 , 4.5 2.0 , 6.0 1.5 , 4.5 1.0 , 4.0 -0.5))";
26
27static std::string polygon_empty = "POLYGON EMPTY";
28
29// 2. Alphabetically ordered testcase pairs
30
31static std::string crossed[2] =
32 {"POLYGON((0 0,0 5,5 5,5 0,0 0),(4 1,3 4,1 2,4 1))",
33 "POLYGON((2 1,1 4,4 3,2 1))"};
34
35static std::string disjoint[2] =
36 {"POLYGON((3 0,3 1,4 1,4 0,3 0))",
37 "POLYGON((3 4,3 5,4 5,4 4,3 4))"};
38
39static std::string distance_zero[2] =
40 {"POLYGON((1 1,1 4,4 4,4 1,1 1))",
41 "POLYGON((1.9 0.9,2.0 4.000001,2.1 1.0,1.9 0.9))"};
42
43// e-45 gives 'convenient' IEEE-single-FP-error,
44static std::string epsilon[2] =
45 {"POLYGON((0.0 0.0"
46 ",3.0e-45 4.0e-45"
47 ",4.0e-45 1.0e-45"
48 ",0.0 0.0))",
49 "POLYGON((2.0e-45 2.0e-45"
50 ",6.0e-45 4.0e-45"
51 ",4.0e-45 -1.0e-45"
52 ",2.0e-45 2.0e-45))"};
53
54static std::string epsilon_multi_ip[2] =
55 {
56 "POLYGON("
57 "(0.0e-44 2.0e-44,0.5e-44 2.5e-44,1.2e-44 2.0e-44,1.7e-44 2.5e-44,2.5e-44 2.0e-44,2.0e-44 1.5e-44"
58 ",2.5e-44 1.0e-44,2.0e-44 0.5e-44,1.7e-44 0.0e-44,1.5e-44 0.5e-44,1.2e-44 0.0e-44,1.0e-44 0.5e-44"
59 ",0.7e-44 0.0e-44,0.5e-44 1.7e-44,0.12e-44 1.5e-44,0.5e-44 1.2e-44,0.0e-44 1.0e-44,0.0e-44 2.0e-44))",
60 "POLYGON("
61 "(0.2e-44 0.2e-44,0.2e-44 2.2e-44,2.2e-44 2.2e-44,2.2e-44 0.2e-44,0.2e-44 0.2e-44))"
62 };
63
64static std::string equal_holes_disjoint[2] =
65 {"POLYGON((0 0,0 9,9 9,9 0,0 0),(1 1,4 1,4 8,1 8,1 1),(5 1,8 1,8 4,5 4,5 1))",
66 "POLYGON((0 0,0 9,9 9,9 0,0 0),(1 1,4 1,4 8,1 8,1 1),(5 5,8 5,8 8,5 8,5 5))"};
67
68static std::string first_within_second[2] =
69 {"POLYGON((2 2,2 3,3 3,3 2,2 2))",
70 "POLYGON((0 0, 0 5, 5 5, 5 0, 0 0))"};
71
72static std::string first_within_hole_of_second[2] =
73 {"POLYGON((2 2,2 3,3 3,3 2,2 2))",
74 "POLYGON((0 0, 0 5, 5 5, 5 0, 0 0),(1 1,4 1,4 4,1 4,1 1))"};
75
76// == case 52
77static std::string fitting[2] =
78 {"POLYGON((0 0,0 5,5 5,5 0,0 0),(4 1,3 4,1 2,4 1))",
79 "POLYGON((1 2,3 4,4 1,1 2))"};
80
81static std::string identical[2] =
82 {"POLYGON((0 0,0 1,1 1,1 0,0 0))",
83 "POLYGON((1 1,1 0,0 0,0 1,1 1))"};
84
85// case 2102 from "algorithms/detail/overlay/robustness/assemble.hpp"
86static std::string intersect_exterior_and_interiors_winded[2] =
87 {"POLYGON((2 0.5,0.5 2,0.5 8,2 9.5,6 9.5,8.5 8,8.5 2,7 0.5,2 0.5),(2 2,7 2,7 8,2 8,2 2))",
88 "POLYGON((1 1,1 9,8 9,8 1,1 1),(4 4,5 4,5 5,4 5,4 4))"};
89
90static std::string intersect_holes_disjoint[2] =
91 {"POLYGON((0 0,0 7,5 7,5 0,0 0),(2 2,3 2,3 3,2 3,2 2))",
92 "POLYGON((1 1,1 6,6 6,6 1,1 1),(2 4,3 4,3 5,2 5,2 4))"};
93
94static std::string intersect_holes_intersect[2] =
95 {"POLYGON((0 0,0 7,5 7,5 0,0 0),(2 2,3 2,3 3,2 3,2 2))",
96 "POLYGON((1 1,1 6,6 6,6 1,1 1),(2.5 2.5,3.5 2.5,3.5 3.5,2.5 3.5,2.5 2.5))"};
97
98static std::string intersect_holes_intersect_and_disjoint[2] =
99 {"POLYGON((0 0,0 7,5 7,5 0,0 0),(2 2,3 2,3 3,2 3,2 2),(2 4,3 4,3 5,2 5,2 4))",
100 "POLYGON((1 1,1 6,6 6,6 1,1 1),(2.5 2.5,3.5 2.5,3.5 3.5,2.5 3.5,2.5 2.5))"};
101
102static std::string intersect_holes_intersect_and_touch[2] =
103 {"POLYGON((0 0,0 7,5 7,5 0,0 0),(2 2,3 2,3 3,2 3,2 2),(2.5 4,3 4.5,2.5 5,2 4.5,2.5 4))",
104 "POLYGON((1 1,1 6,6 6,6 1,1 1),(2.5 2.5,3.5 2.5,3.5 3.5,2.5 3.5,2.5 2.5),(3.5 4,4 4.5,3.5 5,3 4.5,3.5 4))"};
105
106static std::string intersect_holes_new_ring[2] =
107 {"POLYGON((4 4,4 16,16 16,16 4,4 4),(7 6,14 10,7 14,11 10,7 6))",
108 "POLYGON((2 2,2 18,18 18,18 2,2 2),(13 6,9 10,13 14,6 10,13 6))"};
109
110static std::string isovist1[2] =
111 {
112 "POLYGON((37.29449462890625 1.7902572154998779, 46.296027072709599 -2.4984308554828116, 45.389434814453125 -4.5143837928771973, 47.585065917176543 -6.1314922196594779, 46.523914387974358 -8.5152102535033496, 42.699958801269531 -4.4278755187988281, 42.577877044677734 -4.4900407791137695, 42.577911376953125 -4.4901103973388672, 40.758884429931641 -5.418975830078125, 40.6978759765625 -5.4500408172607422, 41.590042114257813 -7.2021245956420898, 57.297810222148939 -37.546793343968417, 50.974888957147442 -30.277285722290763, 37.140213012695313 1.3446992635726929, 37.000419616699219 1.664225697517395, 37.29449462890625 1.7902572154998779))",
113 "POLYGON((43.644271850585938 0.96149998903274536,43.764598846435547 0.93951499462127686,49.071769542946825 0.61489892713413252,48.43512638981781 -0.81299959072453376,47.830955505371094 -0.69758313894271851,47.263670054709685 -1.784876824891044,46.695858001708984 -1.6093428134918213,45.389434814453125 -4.5143837928771973,47.604561877161387 -6.087697464505224,46.559533858616469 -8.435196445683264,42.699958801269531 -4.4278755187988281,42.577877044677734 -4.4900407791137695,42.577911376953125 -4.4901103973388672,40.758884429931641 -5.418975830078125,40.6978759765625 -5.4500408172607422,41.590042114257813 -7.2021245956420898,57.524304765518266 -37.807195733984784,41.988733475572282 -19.945838749437218,41.821544647216797 -19.211688995361328,40.800632476806641 -17.208097457885742,39.966808319091797 -17.625011444091797,38.823680877685547 -16.296066284179688,37.326129913330078 -17.190576553344727,35.963497161865234 -15.476018905639648,35.656356811523438 -15.66030216217041,34.931102752685547 -16.223842620849609,34.634240447128811 -15.85007183479255,34.886280059814453 -14.120697975158691,34.658355712890625 -13.81736946105957,34.328716278076172 -13.992490768432617,33.598796844482422 -14.546377182006836,33.164891643669634 -14.000060288415174,33.566280364990234 -12.450697898864746,33.339523315429688 -12.147735595703125,32.998821258544922 -12.323249816894531,32.274600982666016 -12.879127502441406,31.682494778186321 -12.133624901803865,32.226280212402344 -10.790698051452637,32.000633239746094 -10.488097190856934,31.669155120849609 -10.653837203979492,30.947774887084961 -11.208560943603516,30.207040612748258 -10.275926149505661,30.896280288696289 -9.1206979751586914,30.670633316040039 -8.8180980682373047,30.339155197143555 -8.9838371276855469,29.619997024536133 -9.5368013381958008,29.135100397190627 -8.9262827849488211,32.718830108642578 -4.3281683921813965,32.708168029785156 -2.3611698150634766,32.708126068115234 -2.3611700534820557,32.708126068115234 -2.3611266613006592,30.501169204711914 -2.3718316555023193,27.069889344709196 -4.2926591211028242,26.472516656201325 -3.5380830513658776,36.954700469970703 1.2597870826721191,37.140213012695313 1.3446992635726929,37.000419616699219 1.664225697517395,37.29449462890625 1.7902572154998779,37.43402099609375 1.470055103302002,51.370888500897557 7.4163459734570729,51.20102152843122 7.1738039562841562,42.721500396728516 3.6584999561309814,42.721500396728516 2.2342472076416016,42.399410247802734 1.4956772327423096,43.644271850585938 0.96149998903274536))"
114 };
115
116static std::string new_hole[2] =
117 {"POLYGON((2 2,2 5,5 5,5 2,2 2))",
118 "POLYGON((0 0,0 6,3 6,3 4,1 4,1 3,3 3,3 0,0 0))"};
119
120static std::string only_hole_intersections[3] =
121 {"POLYGON((0 0,0 10,20 10,20 0,0 0),(1 1,7 5,5 7,1 1),(11 1,17 5,15 7,11 1))",
122 "POLYGON((0 0,0 10,20 10,20 0,0 0),(1 1,7 6,6 7,1 1),(11 1,17 6,16 7,11 1))",
123 "POLYGON((0.5 0.5,0.5 9.5,19.5 9.5,19.5 0.5,0.5 0.5),(1 1,7 6,6 7,1 1),(11 1,17 6,16 7,11 1))"};
124
125static std::string side_side[2] =
126 {"POLYGON((0 0,0 1,1 1,1 0,0 0))",
127 "POLYGON((1 0,1 1,2 1,2 0,1 0))"};
128
129static std::string simplex_normal[2] =
130 {"POLYGON((0 1,2 5,5 3,0 1))",
131 "POLYGON((3 0,0 3,4 5,3 0))"};
132
133static std::string simplex_reversed[2] =
134 {"POLYGON((0 1,5 3,2 5,0 1))",
135 "POLYGON((3 0,4 5,0 3,3 0))"};
136
137static std::string star_comb_15[2] =
138 {"POLYGON((25 52.5,27.1694 29.5048,46.5004 42.146,29.8746 26.1126,51.8105 18.8807,28.9092 21.8826,36.9318 0.223356,25 20,13.0682 0.223356,21.0908 21.8826,-1.81052 18.8807,20.1254 26.1126,3.49963 42.146,22.8306 29.5048,25 52.5))",
139 "POLYGON((25 0,0 25,25 50,50 25,49.0741 24.0741,25 48.1481,24.0741 47.2222,48.1481 23.1481,47.2222 22.2222,23.1481 46.2963,22.2222 45.3704,46.2963 21.2963,45.3704 20.3704,21.2963 44.4444,20.3704 43.5185,44.4444 19.4444,43.5185 18.5185,19.4444 42.5926,18.5185 41.6667,42.5926 17.5926,41.6667 16.6667,17.5926 40.7407,16.6667 39.8148,40.7407 15.7407,39.8148 14.8148,15.7407 38.8889,14.8148 37.963,38.8889 13.8889,37.963 12.963,13.8889 37.037,12.963 36.1111,37.037 12.037,36.1111 11.1111,12.037 35.1852,11.1111 34.2593,35.1852 10.1852,34.2593 9.25926,10.1852 33.3333,9.25926 32.4074,33.3333 8.33333,32.4074 7.40741,8.33333 31.4815,7.40741 30.5556,31.4815 6.48148,30.5556 5.55556,6.48148 29.6296,5.55556 28.7037,29.6296 4.62963,28.7037 3.7037,4.62963 27.7778,3.7037 26.8519,27.7778 2.77778,26.8519 1.85185,2.77778 25.9259,1.85185 25,25.9259 0.925926,25 0))"};
140
141static std::string two_bends[2] =
142 {"POLYGON((0 4,4 8,7 7,8 4,5 3,4 0,0 4))",
143 "POLYGON((0 4,4 8,5 5,8 4,7 1,4 0,0 4))"};
144
145// within each other, having no intersections but many holes within each other
146static std::string winded[2] =
147 {"POLYGON((0 0,0 11,11 11,11 0,0 0),(3 3,4 3,4 4,3 4,3 3),(5 3,6 3,6 4,5 4,5 3),(2 6,7 6,7 9,2 9,2 6),(9 2,10 2,10 5,9 5,9 2))",
148 "POLYGON((1 1,1 10,10 10,10 6,8 6,8 1,1 1),(2 2,7 2,7 5,2 5,2 2),(3 7,4 7,4 8,3 8,3 7),(5 7,6 7,6 8,5 8,5 7),(8 7,9 7,9 8,8 8,8 7))"};
149
150static std::string within_holes_disjoint[2] =
151 {"POLYGON((0 0,0 7,7 7,7 0,0 0),(2 2,3 2,3 3,2 3,2 2))",
152 "POLYGON((1 1,1 6,6 6,6 1,1 1),(2 4,3 4,3 5,2 5,2 4))"};
153
154// == case 53
155static std::string wrapped[3] = {
156 "POLYGON((2 2,2 3,3 3,3 2,2 2))",
157 /*a:*/ "POLYGON((0 2,0 5,5 5,5 0,2 0,2 2,3 2,3 1,4 1,4 4,1 4,1 3,2 3,2 2,0 2))", // NOT st_isvalid
158 /*b:*/ "POLYGON((0 2,0 5,5 5,5 0,2 0,2 2,0 2),(1 3,2 3,2 2,3 2,3 1,4 1,4 4,1 4,1 3))" // st_isvalid
159 };
160
161#endif
162

source code of boost/libs/geometry/test/algorithms/test_overlay.hpp