1 // Boost.Geometry (aka GGL, Generic Geometry Library) 2 // Unit Test 3 4 // Copyright (c) 2010-2012 Barend Gehrels, Amsterdam, the Netherlands. 5 6 // This file was modified by Oracle on 2016. 7 // Modifications copyright (c) 2016, Oracle and/or its affiliates. 8 // Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle 9 10 // Use, modification and distribution is subject to the Boost Software License, 11 // Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at 12 // http://www.boost.org/LICENSE_1_0.txt) 13 14 #ifndef BOOST_GEOMETRY_TEST_MULTI_OVERLAY_CASES_HPP 15 #define BOOST_GEOMETRY_TEST_MULTI_OVERLAY_CASES_HPP 16 17 18 #include <string> 19 20 // See powerpoint doc/other/test_cases/overlay_cases.ppt 21 // Note that there are some duplicates with single (80 and on) 22 23 static std::string case_multi_simplex[2] = 24 { 25 "MULTIPOLYGON(((0 1,2 5,5 3,0 1)),((1 1,5 2,5 0,1 1)))", 26 "MULTIPOLYGON(((3 0,0 3,4 5,3 0)))" 27 }; 28 29 // To mix multi/single 30 static std::string case_single_simplex = "POLYGON((3 0,0 3,4 5,3 0))"; 31 32 static std::string case_multi_no_ip[2] = 33 { 34 "MULTIPOLYGON(((4 1,0 7,7 9,4 1)),((8 1,6 3,10 4,8 1)),((12 6,10 7,13 8,12 6)))", 35 "MULTIPOLYGON(((14 4,8 8,15 10,14 4)),((15 3,18 9,20 2,15 3)),((3 4,1 7,5 7,3 4)))" 36 }; 37 38 static std::string case_multi_2[2] = 39 { 40 "MULTIPOLYGON(((4 3,2 7,10 9,4 3)),((8 1,6 3,10 4,8 1)),((12 6,10 7,13 8,12 6)))", 41 "MULTIPOLYGON(((14 4,8 8,15 10,14 4)),((15 3,18 9,20 2,15 3)),((5 5,4 7,7 7,5 5)))" 42 }; 43 44 // Case 58, same as case_58 IET (single) but here the second polygon is inverted 45 // To check behaviour of difference, but in an intersection operation 46 static std::string case_58_multi[8] = 47 { 48 /* a */ "MULTIPOLYGON(((3 3,3 4,4 4,4 3,3 3)))", 49 /* b */ "MULTIPOLYGON(((0 2,0 5,4 4,5 0,0 2),(4 4,1 4,1 3,4 4),(4 4,2 3,2 2,4 4),(4 4,3 2,4 2,4 4)))", 50 /* a inv */ "MULTIPOLYGON(((-1 -1,-1 6,6 6,6 -1,-1 -1),(3 3,4 3,4 4,3 4,3 3)))", 51 /* b inv */ "MULTIPOLYGON(((6 6,6 0,5 0,4 4,0 5,0 6,6 6)),((4 4,1 3,1 4,4 4)),((4 4,2 2,2 3,4 4)),((4 4,4 2,3 2,4 4)))", 52 53 // simpler versions of b 54 /* b */ "MULTIPOLYGON(((0 2,0 5,4 4,5 0,0 2),(4 4,1 4,1 3,4 4)))", 55 /* b */ "MULTIPOLYGON(((0 2,0 5,4 4,5 0,0 2),(4 4,3 2,4 2,4 4)))", 56 /* b */ "MULTIPOLYGON(((0 2,0 5,4 4,5 0,0 2),(4 4,2 3,2 2,4 4)))", 57 /* b */ "MULTIPOLYGON(((0 2,0 5,4 4,5 0,0 2),(4 4,2 3,2 2,4 4),(4 4,3 2,4 2,4 4)))", 58 }; 59 60 static std::string case_61_multi[2] = 61 { 62 // extracted from recursive boxes 63 "MULTIPOLYGON(((1 1,1 2,2 2,2 1,1 1)),((2 2,2 3,3 3,3 2,2 2)))", 64 "MULTIPOLYGON(((1 2,1 3,2 3,2 2,1 2)),((2 3,2 4,3 4,3 3,2 3)))" 65 }; 66 67 static std::string case_62_multi[2] = 68 { 69 // extracted from recursive boxes 70 "MULTIPOLYGON(((1 2,1 3,2 3,2 2,1 2)))", 71 "MULTIPOLYGON(((1 2,1 3,2 3,2 2,1 2)),((2 3,2 4,3 4,3 3,2 3)))" 72 }; 73 74 static std::string case_63_multi[2] = 75 { 76 // extracted from recursive boxes 77 "MULTIPOLYGON(((1 2,1 3,2 3,2 2,1 2)))", 78 "MULTIPOLYGON(((1 2,1 3,2 3,2 2,1 2)),((2 1,2 2,3 2,3 1,2 1)))" 79 }; 80 81 static std::string case_64_multi[3] = 82 { 83 // extracted from recursive boxes 84 "MULTIPOLYGON(((1 1,1 2,2 2,2 1,1 1)),((2 2,2 3,3 3,3 2,2 2)))", 85 "MULTIPOLYGON(((1 1,1 2,2 2,3 2,3 1,2 1,1 1)))" , 86 // same but omitting not-necessary form-points at x=2 (==simplified) 87 "MULTIPOLYGON(((1 1,1 2,3 2,3 1,1 1)))" 88 }; 89 90 static std::string case_65_multi[4] = 91 { 92 "MULTIPOLYGON(((2 2,2 3,3 3,3 2,2 2)))", 93 "MULTIPOLYGON(((1 1,1 2,2 2,2 1,1 1)),((2 2,2 3,3 3,3 2,2 2)),((3 1,3 2,5 2,5 1,3 1)))", 94 95 // Inverse versions 96 "MULTIPOLYGON(((0 0,0 4,6 4,6 0,0 0),(2 2,3 2,3 3,2 3,2 2)))", 97 "MULTIPOLYGON(((0 0,0 4,6 4,6 0,0 0),(1 1,2 1,2 2,1 2,1 1),(2 2,3 2,3 3,2 3,2 2),(3 1,5 1,5 2,3 2,3 1)))" 98 }; 99 100 static std::string case_66_multi[2] = 101 { 102 "MULTIPOLYGON(((3 5,2 5,2 6,3 6,4 6,4 5,3 5)),((1 6,0 6,0 7,1 7,2 7,2 6,1 6)))", 103 "MULTIPOLYGON(((1 4,1 5,2 5,2 4,1 4)),((1 7,2 7,2 6,1 6,1 7)),((0 8,0 9,1 9,1 8,1 7,0 7,0 8)))" 104 }; 105 106 static std::string case_67_multi[2] = 107 { 108 "MULTIPOLYGON(((1 2,1 3,2 3,2 2,1 2)),((2 1,2 2,3 2,3 1,2 1)))", 109 "MULTIPOLYGON(((1 1,1 2,3 2,3 1,1 1)))" 110 }; 111 112 static std::string case_68_multi[2] = 113 { 114 "MULTIPOLYGON(((2 1,2 2,4 2,4 1,2 1)),((4 2,4 3,5 3,5 2,4 2)))", 115 "MULTIPOLYGON(((1 2,1 3,2 3,2 2,1 2)),((2 1,2 2,3 2,3 1,2 1)),((3 2,3 3,5 3,5 2,3 2)))" 116 }; 117 118 static std::string case_69_multi[2] = 119 { 120 "MULTIPOLYGON(((1 1,1 2,2 2,2 1,1 1)),((3 2,3 3,4 3,4 2,3 2)))", 121 "MULTIPOLYGON(((2 0,2 1,3 1,3 0,2 0)),((1 1,1 3,2 3,2 1,1 1)),((2 3,2 4,3 4,3 3,2 3)))" 122 }; 123 124 static std::string case_71_multi[2] = 125 { 126 "MULTIPOLYGON(((0 0,0 3,1 3,1 1,3 1,3 2,4 2,4 0,0 0)),((2 2,2 3,3 3,3 2,2 2)))", 127 "MULTIPOLYGON(((0 2,0 3,3 3,3 2,0 2)))" 128 }; 129 130 static std::string case_72_multi[3] = 131 { 132 // cluster with ii, done by both traverse and assemble 133 "MULTIPOLYGON(((0 3,4 4,3 0,3 3,0 3)),((3 3,2 1,1 2,3 3)))", 134 "MULTIPOLYGON(((0 0,1 4,3 3,4 1,0 0)))", 135 136 // Inverse version of a 137 "MULTIPOLYGON(((-1 -1,-1 5,5 5,5 -1,-1 -1),(0 3,3 3,3 0,4 4,0 3),(3 3,1 2,2 1,3 3)))" 138 }; 139 140 static std::string case_73_multi[2] = 141 { 142 "MULTIPOLYGON(((2 2,2 3,3 3,3 2,2 2)),((1 1,1 2,2 2,2 1,1 1)))", 143 "MULTIPOLYGON(((1 1,1 2,2 2,2 3,3 3,3 1,1 1)))" 144 }; 145 146 static std::string case_74_multi[2] = 147 { 148 "MULTIPOLYGON(((3 0,2 0,2 1,3 1,3 3,1 3,1 2,2 2,2 1,0 1,0 5,4 5,4 0,3 0)))", 149 "MULTIPOLYGON(((0 2,0 3,1 3,1 1,2 1,2 0,0 0,0 2)),((2 3,1 3,1 4,2 4,2 3)))" 150 }; 151 152 static std::string case_75_multi[2] = 153 { 154 // cc/uu turns on all corners of second box 155 "MULTIPOLYGON(((1 1,1 2,2 2,2 1,1 1)),((1 3,1 4,2 4,2 3,1 3)),((2 2,2 3,3 3,3 2,2 2)),((3 1,3 2,4 2,4 1,3 1)),((3 3,3 4,4 4,4 3,3 3)))", 156 "MULTIPOLYGON(((2 2,2 3,3 3,3 2,2 2)))" 157 }; 158 159 static std::string case_76_multi[2] = 160 { 161 // cc/uu turns on all corners of second box, might generate TWO OVERLAPPING union polygons! 162 // therefore, don't follow uu. 163 "MULTIPOLYGON(((1 0,1 1,2 1,2 0,1 0)),((3 2,4 2,4 1,3 1,3 2)),((2 2,2 3,3 3,3 2,2 2)),((2 3,1 3,1 4,2 4,2 3)),((3 3,3 4,4 4,4 3,3 3)))", 164 "MULTIPOLYGON(((0 2,0 3,1 3,1 2,2 2,2 0,1 0,1 1,0 1,0 2)),((2 2,2 3,3 3,3 2,2 2)))" 165 }; 166 167 static std::string case_77_multi[2] = 168 { 169 // with a point on interior-ring-border of enclosing 170 // -> went wrong in the assemble phase for intersection (traversal is OK) 171 // -> fixed 172 "MULTIPOLYGON(((3 3,3 4,4 4,4 3,3 3)),((5 3,5 4,4 4,4 5,3 5,3 6,5 6,5 5,7 5,7 6,8 6,8 5,9 5,9 2,8 2,8 1,7 1,7 2,5 2,5 3),(6 3,8 3,8 4,6 4,6 3)))", 173 "MULTIPOLYGON(((6 3,6 4,7 4,7 3,6 3)),((2 3,1 3,1 4,3 4,3 5,4 5,4 6,5 6,5 7,9 7,9 4,7 4,7 5,8 5,8 6,7 6,7 5,6 5,6 4,4 4,4 3,3 3,3 2,2 2,2 3)),((5 2,4 2,4 3,6 3,6 2,5 2)),((7 2,7 3,8 3,8 2,8 1,7 1,7 2)))" 174 }; 175 176 static std::string case_78_multi[2] = 177 { 178 "MULTIPOLYGON(((0 0,0 5,5 5,5 0,0 0),(2 2,4 2,4 3,2 3,2 2)))", 179 "MULTIPOLYGON(((0 0,0 5,5 5,5 0,0 0),(3 2,4 2,4 3,3 3,3 2),(1 1,2 1,2 2,1 2,1 1)))" 180 181 }; 182 183 static std::string case_80_multi[2] = 184 { 185 // Many ux-clusters -> needs correct cluster-sorting 186 // Fixed now 187 "MULTIPOLYGON(((3 1,3 2,4 2,3 1)),((1 5,0 4,0 5,1 6,1 5)),((3 3,4 3,3 2,2 2,2 3,3 3)),((4 5,5 6,5 5,4 5)),((4 2,4 3,5 3,4 2)),((2.5 5.5,3 5,2 5,2 7,3 6,2.5 5.5)),((1 6,0 6,0 7,1 7,2 6,1 6)))", 188 "MULTIPOLYGON(((3 5,3 6,4 6,4 5,3 5)),((4 4,5 5,5 4,4 4)),((3 3,4 4,4 3,3 3)),((1 5,1 6,2 6,2 5,1 5)),((0 6,1 7,1 6,0 6)),((1 4,1 3,0 3,0 4,1 4)),((3 5,4 4,3 4,3 3,2 3,2 5,3 5)))" 189 }; 190 191 static std::string case_81_multi[2] = 192 { 193 "MULTIPOLYGON(((1 1,2 2,2 1,1 1)),((2 2,2 3,3 2,2 2)),((3 1,4 2,4 1,3 1)))", 194 "MULTIPOLYGON(((2 1,2 2,3 3,3 2,4 2,3 1,2 1)))" 195 }; 196 197 static std::string case_82_multi[2] = 198 { 199 "MULTIPOLYGON(((4 0,5 1,5 0,4 0)),((2 1,3 2,3 1,2 1)),((3 0,4 1,4 0,3 0)),((1 0,1 1,2 1,2 0,1 0)))", 200 "MULTIPOLYGON(((3 2,4 3,4 2,3 2)),((3 1,3 2,4 1,3 1)),((0 0,1 1,1 0,0 0)),((5 1,5 0,4 0,4 1,5 1)))" 201 }; 202 203 static std::string case_83_multi[2] = 204 { 205 // iu/iu 206 "MULTIPOLYGON(((1 0,1 1,2 1,1 0)),((0 1,0 4,1 4,1 1,0 1)),((2 1,2 2,3 2,3 1,2 1)),((2 3,3 4,3 3,2 3)))", 207 "MULTIPOLYGON(((1 0,2 1,2 0,1 0)),((0 3,1 4,1 3,0 3)),((2 3,2 4,3 3,2 3)),((1 3,2 3,2 2,0 2,1 3)))" 208 }; 209 210 static std::string case_84_multi[2] = 211 { 212 // iu/ux 213 "MULTIPOLYGON(((2 2,3 3,3 2,2 2)),((2 1,2 2,3 1,2 1)),((2 3,3 4,3 3,2 3)),((1 3,2 4,2 2,1 2,1 3)))", 214 "MULTIPOLYGON(((2 3,3 3,3 1,2 1,2 2,1 2,1 3,2 3)))" 215 }; 216 217 static std::string case_85_multi[2] = 218 { 219 // iu/ux (and ux/ux) 220 "MULTIPOLYGON(((0 1,0 2,1 2,0 1)),((1 1,1 2,2 1,1 1)),((0 3,1 3,0 2,0 3)))", 221 "MULTIPOLYGON(((1 3,2 3,2 1,1 1,1 2,0 2,1 3)))" 222 }; 223 224 static std::string case_86_multi[2] = 225 { 226 // iu/ux 227 "MULTIPOLYGON(((4 2,4 3,5 3,4 2)),((5 2,6 3,6 2,5 2)),((5 1,4 1,4 2,5 2,6 1,5 1)))", 228 "MULTIPOLYGON(((5 1,5 2,6 2,6 1,5 1)),((4 2,5 3,5 2,4 2)),((3 2,4 3,4 2,3 2)))" 229 }; 230 231 static std::string case_87_multi[2] = 232 { 233 // iu/ux where iu crosses, no touch 234 "MULTIPOLYGON(((5 0,5 1,6 0,5 0)),((6 2,7 3,7 2,6 2)),((5 1,5 3,6 3,6 1,5 1)))", 235 "MULTIPOLYGON(((5 1,5 2,7 2,7 1,6 1,6 0,5 0,5 1)),((4 3,5 3,5 2,3 2,4 3)))" 236 }; 237 238 239 static std::string case_88_multi[2] = 240 { 241 "MULTIPOLYGON(((0 0,0 1,1 0,0 0)),((1 1,1 2,2 1,1 1)),((0 2,0 3,1 3,2 3,2 2,1 2,0 1,0 2)))", 242 "MULTIPOLYGON(((0 0,0 1,1 0,0 0)),((0 1,1 2,1 1,0 1)),((0 2,0 3,1 3,1 2,0 2)))" 243 }; 244 245 static std::string case_89_multi[2] = 246 { 247 // Extract from rec.boxes_3 248 "MULTIPOLYGON(((8 1,7 1,8 2,8 3,9 4,9 2,8.5 1.5,9 1,8 0,8 1)),((9 1,9 2,10 2,10 1,9 0,9 1)))", 249 "MULTIPOLYGON(((8 3,9 4,9 3,8 3)),((7 0,7 1,8 1,8 0,7 0)),((9 2,9 1,8 1,8 3,8.5 2.5,9 3,9 2)))" 250 }; 251 252 static std::string case_90_multi[2] = 253 { 254 // iu/iu for Union; see ppt 255 "MULTIPOLYGON(((1 8,0 8,0 10,1 10,1 9,2 8,2 7,1 7,1 8)),((2 9,2 10,4 10,4 9,3 9,3 8,2 8,2 9)))", 256 "MULTIPOLYGON(((2 8,1 8,1 9,2 9,2 10,3 10,3 8,2 8)),((0 10,2 10,0 8,0 10)))" 257 }; 258 259 static std::string case_91_multi[2] = 260 { 261 // iu/xi for Intersection 262 "MULTIPOLYGON(((3 3,3 4,4 4,3 3)),((2 2,1 2,1 4,2 4,2 3,3 3,2 2)))", 263 "MULTIPOLYGON(((2 2,2 3,3 2,2 2)),((2 3,1 3,1 4,1.5 3.5,2 4,2.5 3.5,3 4,3 3,2 3)))" 264 }; 265 266 static std::string case_92_multi[2] = 267 { 268 // iu/iu all aligned (for union) 269 "MULTIPOLYGON(((7 2,7 3,8 2,7 2)),((8 4,9 5,9 4,8 4)),((8 2,8 3,9 2,8 2)),((7 3,7 4,8 4,8 3,7 3)),((9 3,9 4,10 4,10 3,9 3)))", 270 "MULTIPOLYGON(((9 2,8 2,8 3,9 3,10 2,9 2)),((7 5,8 5,9 6,9 4,8 4,7 3,6 3,6 4,6.5 3.5,7 4,6 4,7 5)))" 271 }; 272 273 static std::string case_93_multi[2] = 274 { 275 // iu/xi for intersection 276 "MULTIPOLYGON(((6 2,7 2,7 1,5 1,6 2)),((7 3,8 3,7.5 2.5,8 2,7 2,7 3)))", 277 "MULTIPOLYGON(((7 1,6 0,6 2,7 3,7 2,8 3,8 2,7 1)))" 278 }; 279 280 281 static std::string case_94_multi[2] = 282 { 283 // iu/iu for union 284 "MULTIPOLYGON(((9 2,9 3,10 3,10 2,9 2)),((7 3,8 4,9 3,8 3,9 2,7 2,7 3)),((8 6,9 5,9 4,8 4,8 6)))", 285 "MULTIPOLYGON(((6 2,6 3,7 3,8 2,6 2)),((9 3,10 3,9 2,9 1,8 0,7 0,8 1,8 3,8.5 2.5,9 3)),((7 4,7 5,8 5,9 6,9 4,8 4,8 3,7 3,7 4)))" 286 }; 287 288 static std::string case_95_multi[2] = 289 { 290 // iu/iu for union 291 "MULTIPOLYGON(((0 8,1 8,1 7,0 7,0 8)),((2 8,2 9,2.5 8.5,3 9,3 7,2 7,2 8)),((1 9,1 10,2 9,1 8,1 9)))", 292 "MULTIPOLYGON(((1 7,0 7,0 8,1 8,2 7,1 7)),((2 9,1 9,1 10,2 10,3 9,4 9,4 8,2 8,2 9)))" 293 }; 294 295 static std::string case_96_multi[2] = 296 { 297 // iu/iu all collinear, for intersection/union 298 "MULTIPOLYGON(((8 2,9 3,9 2,8 2)),((8 1,9 2,9 1,10 1,10 0,8 0,8 1)))", 299 "MULTIPOLYGON(((9 0,9 1,10 0,9 0)),((8 1,8 2,9 2,9 1,8 1)))" 300 }; 301 302 static std::string case_97_multi[2] = 303 { 304 // ux/ux for union 305 "MULTIPOLYGON(((4 4,4 5,4.5 4.5,5 5,6 5,5 4,5 3,4 3,4 4)))", 306 "MULTIPOLYGON(((5 3,5 4,6 3,5 3)),((6 5,7 5,6 4,5 4,6 5)))" 307 }; 308 309 310 static std::string case_98_multi[2] = 311 { 312 // ii/iu for intersection, solved by discarding iu (ordering not possible) 313 "MULTIPOLYGON(((2 0,3 1,3 0,2 0)),((2 2,2 3,1 3,1 4,2 4,3 3,3 4,5 2,4 2,4 1,3 1,3 2,2.5 1.5,3 1,2 1,2 2)))", 314 "MULTIPOLYGON(((4 2,4 3,5 2,4 2)),((1 0,0 0,0 2,4 2,4 1,2 1,2 0,1 0)),((3 3,4 4,4 3,3 2,3 3)))" 315 }; 316 317 static std::string case_99_multi[2] = 318 { 319 // iu/iu for intersection 320 "MULTIPOLYGON(((1 0,2 1,2 0,1 0)),((1 2,2 2,1.5 1.5,2 1,1 1,1 0,0 0,0 1,1 2)))", 321 "MULTIPOLYGON(((1 1,2 0,0 0,1 1)),((1 1,0 1,0 2,1 2,2 3,2 2,1 1)))" 322 }; 323 324 static std::string case_100_multi[2] = 325 { 326 // for intersection 327 "MULTIPOLYGON(((0 0,0 1,1 0,0 0)),((2 2,2 1,0 1,0 2,1 2,2 3,2 2)))", 328 "MULTIPOLYGON(((1 1,1 2,2 2,2 1,1 1)),((1 2,0 1,0 3,1 4,1 2)))" 329 }; 330 331 static std::string case_101_multi[4] = 332 { 333 // interior ring / union 334 "MULTIPOLYGON(((7 2,7 3,8 2,7 2)),((9 3,9 4,10 3,9 3)),((10 1,10 0,8 0,8 1,9 2,10 2,10 1)),((9 3,9 2,8 2,8 3,7 3,7 4,8 4,9 3)),((8 4,8 7,9 6,9 4,8 4)))", 335 "MULTIPOLYGON(((5 1,5 2,6 3,6 4,7 5,6 5,7 6,8 6,8 5,9 5,10 5,10 1,8 1,7 0,5 0,5 1),(9 5,8 4,9 4,9 5),(8 1,8 3,7 3,7 2,6 2,7 1,8 1),(5 1,5.5 0.5,6 1,5 1),(8.5 2.5,9 2,9 3,8.5 2.5)))", 336 337 // inverse versions 338 "MULTIPOLYGON(((4 -1,4 8,11 8,11 -1,4 -1),(7 2,8 2,7 3,7 2),(9 3,10 3,9 4,9 3),(10 1,10 2,9 2,8 1,8 0,10 0,10 1),(9 3,8 4,7 4,7 3,8 3,8 2,9 2,9 3),(8 4,9 4,9 6,8 7,8 4)))", 339 "MULTIPOLYGON(((4 -1,4 8,11 8,11 -1,4 -1),(5 1,5 0,7 0,8 1,10 1,10 5,9 5,8 5,8 6,7 6,6 5,7 5,6 4,6 3,5 2,5 1)),((9 5,9 4,8 4,9 5)),((8 1,7 1,6 2,7 2,7 3,8 3,8 1)),((5 1,6 1,5.5 0.5,5 1)),((8.5 2.5,9 3,9 2,8.5 2.5)))" 340 }; 341 342 static std::string case_102_multi[4] = 343 { 344 // interior ring 'fit' / union 345 "MULTIPOLYGON(((0 2,0 7,5 7,5 2,0 2),(4 3,4 6,1 6,2 5,1 5,1 4,3 4,4 3)),((3 4,3 5,4 5,3 4)),((2 5,3 6,3 5,2 4,2 5)))", 346 "MULTIPOLYGON(((0 2,0 7,5 7,5 2,0 2),(2 4,3 5,2 5,2 4),(4 4,3 4,3 3,4 4),(4 5,4 6,3 6,4 5)))", 347 348 // inverse versions (first was already having an interior, so outer ring is just removed 349 "MULTIPOLYGON(((4 3,3 4,1 4,1 5,2 5,1 6,4 6,4 3),(3 4,4 5,3 5,3 4),(2 5,2 4,3 5,3 6,2 5)))", 350 "MULTIPOLYGON(((-1 1,-1 8,6 8,6 1,-1 1),(0 2,5 2,5 7,0 7,0 2)),((2 4,2 5,3 5,2 4)),((4 4,3 3,3 4,4 4)),((4 5,3 6,4 6,4 5)))" 351 }; 352 353 static std::string case_103_multi[2] = 354 { 355 // interior ring 'fit' (ix) / union / assemble 356 "MULTIPOLYGON(((0 0,0 5,5 5,5 0,2 0,2 1,1 0,0 0),(2 1,3 1,3 2,2 2,2 1),(2 2,2 3,1 2,2 2)))", 357 "MULTIPOLYGON(((0 0,0 5,5 5,5 0,0 0),(2 1,2 2,1 1,2 1)))" 358 }; 359 360 static std::string case_104_multi[2] = 361 { 362 // interior ring 'fit' (ii) / union / assemble 363 "MULTIPOLYGON(((1 0,1 1,0 1,0 5,5 5,5 0,2 0,2 1,1 0),(2 2,3 3,2 3,2 2)))", 364 "MULTIPOLYGON(((0 0,0 5,5 5,5 0,0 0),(1 1,3 1,3 2,1 2,1 1)))" 365 }; 366 367 static std::string case_105_multi[2] = 368 { 369 // interior ring 'fit' () / union / assemble 370 "MULTIPOLYGON(((0 0,0 5,5 5,5 0,0 0),(2 2,3 2,3 3,1 3,2 2)))", 371 "MULTIPOLYGON(((0 0,0 5,5 5,5 0,0 0),(1 1,2 1,2 2,1 1),(2 1,3 1,3 2,2 1),(1 3,2 3,2 4,1 4,1 3),(2 3,3 3,3 4,2 3)))" 372 }; 373 374 static std::string case_106_multi[2] = 375 { 376 // interior ring 'fit' () / union / assemble 377 // [1] is reported as invalid by BG, but not by postgis 378 "MULTIPOLYGON(((0 0,0 3,0 5,5 5,5 0,0 0),(0 3,1 2,1 3,0 3),(1 3,2 3,3 4,1 4,1 3),(2 3,2 2,3 3,2 3),(2 2,2 1,3 2,2 2)))", 379 "MULTIPOLYGON(((0 0,0 5,1 5,1 4,2 4,2 5,3 5,3 3,4 4,5 4,5 0,2 0,3 1,2 1,1 1,0 0),(2 1,2 2,1.5 1.5,2 1),(2 2,2 3,1 3,2 2)),((2 0,1 0,2 1,2 0)))" 380 }; 381 382 static std::string case_107_multi[4] = 383 { 384 // For CCW polygon reports a iu/iu problem. 385 "MULTIPOLYGON(((6 8,7 9,7 7,8 7,7 6,6 6,6 8)),((6.5 9.5,7 10,7 9,6 9,6 10,6.5 9.5)))", 386 "MULTIPOLYGON(((5 7,6 8,6 10,7 9,8 10,8 8,7 8,6 7,6 6,5 7)))", 387 388 // inverse versions 389 "MULTIPOLYGON(((5 5,5 11,9 11,9 5,5 5),(6 8,6 6,7 6,8 7,7 7,7 9,6 8),(6.5 9.5,6 10,6 9,7 9,7 10,6.5 9.5)))", 390 "MULTIPOLYGON(((4 5,4 11,9 11,9 5,4 5),(5 7,6 6,6 7,7 8,8 8,8 10,7 9,6 10,6 8,5 7)))" 391 }; 392 393 static std::string case_108_multi[2] = 394 { 395 // Missing intersection point in [0] / [1], [0] / [2] is OK 396 "MULTIPOLYGON(((1 2,0 1,0 6,1 6,2 5,2 4,3 4,4 4,4 2,4 1,1 1,1 2),(1 2,2 2,3 3,1 3,1 2),(2 2,2.5 1.5,3 2,2 2),(2 4,1 4,1.5 3.5,2 4)))", 397 "MULTIPOLYGON(((1 2,2 3,2 4,1 3,1 4,1 5,2 6,3 6,3 5,5 5,5 0,4 0,4 1,1 1,1 2),(2 4,2.5 3.5,3 4,2 4),(3 4,4 3,4 4,3 4),(4 3,3 3,3 2,4 2,4 3)),((0 3,1 3,1 2,0 2,0 3)),((0 3,0 4,1 4,0 3)))" 398 }; 399 400 static std::string case_109_multi[2] = 401 { 402 "MULTIPOLYGON(((0 0,0 40,40 40,40 0,0 0),(10 10,30 10,30 30,10 30,10 10)))", 403 "MULTIPOLYGON(((10 10,10 20,20 10,10 10)),((20 10,30 20,30 10,20 10)),((10 20,10 30,20 20,10 20)),((20 20,30 30,30 20,20 20)))" 404 }; 405 406 static std::string case_110_multi[2] = 407 { 408 "MULTIPOLYGON(((0 0,0 40,40 40,40 0,0 0),(10 10,30 10,30 30,10 30,10 10)))", 409 "MULTIPOLYGON(((15 10,10 15,10 17,15 10)),((15 10,10 20,10 22,15 10)),((15 10,10 25,10 27,15 10)),((25 10,30 17,30 15,25 10)),((25 10,30 22,30 20,25 10)),((25 10,30 27,30 25,25 10)),((18 10,20 30,19 10,18 10)),((21 10,20 30,22 10,21 10)))" 410 }; 411 412 413 // Cases 111 to 122 are for testing uu-cases, validity, touch, interior rings 414 static std::string case_111_multi[2] = 415 { 416 "MULTIPOLYGON(((4 0,2 2,4 4,6 2,4 0)))", 417 "MULTIPOLYGON(((4 4,2 6,4 8,6 6,4 4)))" 418 }; 419 420 static std::string case_112_multi[2] = 421 { 422 "MULTIPOLYGON(((0 0,0 2,2 4,4 2,6 4,8 2,8 0,0 0)))", 423 "MULTIPOLYGON(((0 8,8 8,8 6,6 4,4 6,2 4,0 6,0 8)))" 424 }; 425 426 // Provided by Menelaos (1) 427 static std::string case_113_multi[2] = 428 { 429 "MULTIPOLYGON(((0 0,0 10,10 10,10 0,0 0)),((15 5,15 10,20 10,20 5,15 5)))", 430 "MULTIPOLYGON(((10 0,15 5,15 0,10 0)),((10 5,10 10,15 10,15 5,10 5)))" 431 }; 432 433 // Provided by Menelaos (2) 434 static std::string case_114_multi[2] = 435 { 436 "MULTIPOLYGON(((0 0,0 10,10 10,10 0,0 0)),((15 5,15 10,20 10,20 5,15 5)))", 437 "MULTIPOLYGON(((10 0,15 5,20 5,20 0,10 0)),((10 5,10 10,15 10,15 5,10 5)))" 438 }; 439 440 // Mailed by Barend 441 static std::string case_115_multi[2] = 442 { 443 "MULTIPOLYGON(((4 0,2 2,4 4,6 2,4 0)),((4 6,6 8,8 6,6 4,4 6)))", 444 "MULTIPOLYGON(((4 4,2 6,4 8,6 6,4 4)),((4 2,7 6,8 3,4 2)))" 445 }; 446 447 // Formerly referred to as a 448 // Should result in 1 polygon with 2 holes 449 // "POLYGON((4 9,4 10,6 10,6 12,8 12,8 11,10 11,10 9,11 9,11 2,3 2,3 9,4 9),(6 10,6 8,7 8,7 10,6 10),(6 8,5 8,5 3,9 3,9 7,8 7,8 6,6 6,6 8))" 450 static std::string case_116_multi[2] = 451 { 452 "MULTIPOLYGON(((4 8,4 10,6 10,6 8,4 8)),((7 7,7 11,10 11,10 7,7 7)))", 453 "MULTIPOLYGON(((6 6,6 8,8 8,8 6,6 6)),((6 10,6 12,8 12,8 10,6 10)),((9 9,11 9,11 2,3 2,3 9,5 9,5 3,9 3,9 9)))" 454 }; 455 456 // Formerly referred to as b 457 // Should result in 2 polygons 458 // "MULTIPOLYGON(((4 8,4 10,6 10,6 8,4 8)),((7 8,7 10,6 10,6 12,8 12,8 11,10 11,10 7,8 7,8 6,6 6,6 8,7 8)))" 459 static std::string case_117_multi[2] = 460 { 461 "MULTIPOLYGON(((4 8,4 10,6 10,6 8,4 8)),((7 7,7 11,10 11,10 7,7 7)))", 462 "MULTIPOLYGON(((6 6,6 8,8 8,8 6,6 6)),((6 10,6 12,8 12,8 10,6 10)))" 463 }; 464 465 // Formerly referred to as c 466 // Shoud result in 3 polygons: 467 // "MULTIPOLYGON(((4 8,4 10,6 10,6 8,4 8)),((8 8,8 10,10 10,10 8,8 8)),((7 12,7 13,13 13,13 5,7 5,7 6,6 6,6 8,8 8,8 7,11 7,11 11,8 11,8 10,6 10,6 12,7 12)))" 468 static std::string case_118_multi[2] = 469 { 470 "MULTIPOLYGON(((4 8,4 10,6 10,6 8,4 8)),((8 8,8 10,10 10,10 8,8 8)),((7 11,7 13,13 13,13 5,7 5,7 7,11 7,11 11,7 11)))", 471 "MULTIPOLYGON(((6 6,6 8,8 8,8 6,6 6)),((6 10,6 12,8 12,8 10,6 10)))" 472 }; 473 474 // Formerly referred to as d 475 // Should result in 2 polygons: 476 // "MULTIPOLYGON(((2 4,2 6,3 6,3 7,7 7,7 6,8 6,8 4,6 4,6 5,4 5,4 4,2 4)),((1 0,1 2,0 2,0 4,2 4,2 3,8 3,8 4,10 4,10 2,9 2,9 0,1 0)))" 477 static std::string case_119_multi[2] = 478 { 479 "MULTIPOLYGON(((2 4,2 6,4 6,4 4,2 4)),((6 4,6 6,8 6,8 4,6 4)),((1 0,1 3,9 3,9 0,1 0)))", 480 "MULTIPOLYGON(((0 2,0 4,2 4,2 2,0 2)),((8 2,8 4,10 4,10 2,8 2)),((3 5,3 7,7 7,7 5,3 5)))" 481 }; 482 483 // With a c/c turn 484 static std::string case_120_multi[2] = 485 { 486 "MULTIPOLYGON(((6 4,6 9,9 9,9 6,11 6,11 4,6 4)),((10 7,10 10,12 10,12 7,10 7)))", 487 "MULTIPOLYGON(((10 5,10 8,12 8,12 5,10 5)),((6 10,8 12,10 10,8 8,6 10)))" 488 }; 489 490 // With c/c turns in both involved polygons 491 static std::string case_121_multi[2] = 492 { 493 "MULTIPOLYGON(((7 4,7 8,9 8,9 6,11 6,11 4,7 4)),((10 7,10 10,12 10,12 7,10 7)))", 494 "MULTIPOLYGON(((10 5,10 8,12 8,12 5,10 5)),((7 7,7 10,10 10,9 9,9 7,7 7)))" 495 }; 496 497 // Same but here c/c not directly involved in the turns itself 498 // (This one breaks if continue is not checked in handle_touch) 499 static std::string case_122_multi[2] = 500 { 501 "MULTIPOLYGON(((10 8,10 10,12 10,12 8,10 8)),((10 4,10 7,12 7,12 4,10 4)),((7 5,7 8,9 8,9 5,7 5)))", 502 "MULTIPOLYGON(((7 3,7 6,9 6,9 5,11 5,11 3,7 3)),((10 6,10 9,12 9,12 6,10 6)),((7 7,7 10,10 10,9 9,9 7,7 7)))" 503 }; 504 505 static std::string case_123_multi[2] = 506 { 507 // Intersection: one cluster with 3 zones, intersection -> no holes 508 "MULTIPOLYGON(((1 0,1 1,1.5 0.5,2 0.5,2 0,1 0)),((0 1,1 2,2 2,2 1,0 1)))", 509 "MULTIPOLYGON(((1 0,1 2,2 2,2 0,1 0)),((0 1,0 2,1 1,0 1)))" 510 }; 511 512 static std::string case_124_multi[2] = 513 { 514 // Intersection: one cluster with 3 zones, intersection -> one hole 515 "MULTIPOLYGON(((1 0,1 1,0 1,1 2,2 2,2 0,1 0),(1.5 0.5,1.75 1,1 1,1.5 0.5)))", 516 "MULTIPOLYGON(((1 0,1 2,2 2,2 0,1 0)),((0 1,0 2,1 1,0 1)))" 517 }; 518 519 static std::string case_125_multi[2] = 520 { 521 // Intersection: one cluster with 3 zones, intersection -> one hole (filled with other polygon) 522 "MULTIPOLYGON(((1 0,1 1,0 1,1 2,2 2,2 0,1 0),(1.5 0.5,1.75 1,1 1,1.5 0.5)),((1 1,1.5 0.9,1.25 0.8,1 1)))", 523 "MULTIPOLYGON(((1 0,1 2,2 2,2 0,1 0)),((0 1,0 2,1 1,0 1)))" 524 }; 525 526 static std::string case_126_multi[2] = 527 { 528 // Intersection: should result in multi-polygon of 5 (needs self-intersections) 529 "MULTIPOLYGON(((5 5,5 10,10 10,10 5,5 5),(9 8,7 9,5 8,7 7,9 8)),((3 3,3 5,5 5,5 3,3 3)))", 530 "MULTIPOLYGON(((0 3,6 3,6 9,0 9,0 3),(2 6,4 7,6 6,4 5,2 6)),((6 9,6 11,8 11,8 9,6 9)))" 531 }; 532 533 static std::string case_127_multi[2] = 534 { 535 // Intersection/validity with ii at (4 4), and both have self intersections at (5 5) 536 "MULTIPOLYGON(((0 0,0 5,3 5,3 4,4 4,4 5,5 5,5 0,0 0)),((5 5,5 6,6 6,6 5,5 5)))", 537 "MULTIPOLYGON(((0 0,0 5,5 5,5 4,4 4,4 3,5 3,5 0,0 0)),((5 5,5 7,7 7,7 5,5 5)))" 538 }; 539 540 static std::string case_128_multi[2] = 541 { 542 // Contains isolated areas of two types 543 "MULTIPOLYGON(((0 0,0 10,10 10,10 0,0 0),(4 8,6 7,8 8,6 9,4 8),(1 2,2 0,3 2,2 4,1 2)))", 544 "MULTIPOLYGON(((0 0,0 10,11 10,11 0,0 0),(2 9,0 8,2 7,4 8,2 9),(5 5,5 0,10 5,5 5)))" 545 }; 546 547 static std::string case_129_multi[2] = 548 { 549 // Extract from rec.box #6 550 "MULTIPOLYGON(((0 0,0 5,5 5,5 4,4 4,4 2,5 1,5 0,0 0),(3 4,3 3,4 4,3 4),(2 1,3 2,3 3,2 2,2 1)))", 551 "MULTIPOLYGON(((0 0,0 5,5 5,5 0,0 0),(4 4,4 3,5 4,4 4),(2 1,3 1,3 3,2 2,2 1)))" 552 }; 553 554 static std::string case_130_multi[2] = 555 { 556 // For validity 557 "MULTIPOLYGON(((0 0,0 7,7 7,7 0,0 0),(1 4,2 3,3 4,2 5,1 4),(5 4,6 3,7 4,6 5,5 4),(3 6,4 5,5 6,4 7,3 6)))", 558 "MULTIPOLYGON(((0 0,0 7,7 7,7 0,0 0),(4 3,5 4,4 5,3 4,4 3),(1 2,2 1,3 2,2 3,1 2)))" 559 }; 560 561 static std::string case_131_multi[2] = 562 { 563 // For validity, interior ring connections 564 "MULTIPOLYGON(((1 2,1 3,2 3,2 2,1 2)),((2 1,2 2,3 2,3 1,2 1)))", 565 "MULTIPOLYGON(((0 0,0 4,4 4,4 0,0 0),(3 3,1 3,1 1,3 1,3 3)))" 566 }; 567 568 static std::string case_132_multi[2] = 569 { 570 // For validity, interior ring connections including cluster 571 "MULTIPOLYGON(((2 4,2 6,4 6,4 4,2 4)),((4 2,4 4,6 4,6 2,4 2)))", 572 "MULTIPOLYGON(((0 0,0 8,8 8,8 0,0 0),(6 6,2 6,2 2,6 2,6 6)),((2 2,2.5 3.5,4 4,3.5 2.5,2 2)),((4 4,4.5 5.5,6 6,5.5 4.5,4 4)))" 573 }; 574 575 static std::string case_133_multi[2] = 576 { 577 // Zoomed in version of case_recursive_boxes_49 with in both interiors an extra polygon (same for both) 578 "MULTIPOLYGON(((0 0,0 4,2 4,2 6,4 6,4 8,10 8,10 4,8 4,8 0,0 0),(4 4,4 6,6 6,6 4,4 4)),((5 4.5,4 6,5.5 5, 5 4.5)))", 579 "MULTIPOLYGON(((2 0,2 8,8 8,8 6,10 6,10 2,6 2,6 0,2 0),(6 6,6 4,4 4,4 6,6 6)),((5 4.5,4 6,5.5 5, 5 4.5)))" 580 }; 581 582 static std::string case_134_multi[2] = 583 { 584 // Zoomed in version of case_recursive_boxes_49 with two interior rings 585 "MULTIPOLYGON(((0 0,0 4,2 4,2 6,4 6,4 8,10 8,10 4,8 4,8 0,0 0),(3 4,4 6,4 4,3 4),(6 6,4 6,6 7,6 6)))", 586 "MULTIPOLYGON(((2 0,2 8,8 8,8 6,10 6,10 2,6 2,6 0,2 0),(3 4,4 6,4 4,3 4),(6 6,4 6,6 7,6 6)))" 587 }; 588 589 static std::string case_135_multi[2] = 590 { 591 // Contains two equal interior rings, both touching to their exterior rings 592 // Needs detection of isolated interior ring pattern 593 "MULTIPOLYGON(((5 8,4 8,4 7,3 7,3 6,2 6,2 7,1 7,1 10,3 10,3 9,5 9,5 8),(3 8,3 9,2 9,2 8,3 8)))", 594 "MULTIPOLYGON(((5 4,4 4,3 4,3 7,1 7,1 8,0 8,0 9,1 9,1 10,3 10,3 9,4 9,4 8,6 8,6 9,7 9,7 5,6 5,6 4,5 4),(5 5,5 6,6 6,6 7,4 7,4 5,5 5),(3 8,3 9,2 9,2 8,3 8)))" 595 }; 596 597 static std::string case_136_multi[2] = 598 { 599 // Variant of 135, but approaching cluster is non equal 600 "MULTIPOLYGON(((5 8,4 8,4 7,3 7,3 6,2 6,2 7,1 7,1 10,2 10,3 9,5 9,5 8),(3 8,3 9,2 9,2 8,3 8)))", 601 "MULTIPOLYGON(((5 4,4 4,3 4,3 7,1 7,1 8,0 8,0 9,1 9,1 10,3 10,3 9,4 9,4 8,6 8,6 9,7 9,7 5,6 5,6 4,5 4),(5 5,5 6,6 6,6 7,4 7,4 5,5 5),(3 8,3 9,2 9,2 8,3 8)))" 602 }; 603 604 static std::string case_137_multi[2] = 605 { 606 // Variant of 135, but leaving cluster is non equal 607 "MULTIPOLYGON(((5 8,4 8,4 7,3 7,3 6,2 6,2 7,1 7,1 10,3 10,3 9,5 9,5 8),(3 8,3 9,2 9,2 8,3 8)))", 608 "MULTIPOLYGON(((5 4,4 4,3 4,3 7,1 7,1 8,0 8,0 9,1 9,1 10,3 10,3 9,4 8,6 8,6 9,7 9,7 5,6 5,6 4,5 4),(5 5,5 6,6 6,6 7,4 7,4 5,5 5),(3 8,3 9,2 9,2 8,3 8)))" 609 }; 610 611 static std::string case_138_multi[2] = 612 { 613 // Zoomed in version of case_recursive_boxes_49 with in both interiors an extra polygon (different for both) 614 "MULTIPOLYGON(((0 0,0 4,2 4,2 6,4 6,4 8,10 8,10 4,8 4,8 0,0 0),(4 4,4 6,6 6,6 4,4 4)),((4.5 4.5,4 6,5.5 5.5,4.5 4.5)))", 615 "MULTIPOLYGON(((2 0,2 8,8 8,8 6,10 6,10 2,6 2,6 0,2 0),(6 6,6 4,4 4,4 6,6 6)),((5 4.5,4 6,5.5 5, 5 4.5)))" 616 }; 617 618 static std::string case_139_multi[2] = 619 { 620 // Another zoomed in version of case_recursive_boxes_49 with different interior polygons 621 "MULTIPOLYGON(((0 0,0 4,2 4,2 6,4 6,4 8,10 8,10 4,8 4,8 0,0 0),(4 4,4 6,6 6,6 4,4 4)),((4.5 4.5,4 6,5.5 5,4.5 4.5)))", 622 "MULTIPOLYGON(((2 0,2 8,8 8,8 6,10 6,10 2,6 2,6 0,2 0),(6 6,6 4,4 4,4 6,6 6)),((5 4.5,4 6,5.5 5, 5 4.5)))" 623 }; 624 625 static std::string case_140_multi[2] = 626 { 627 // Another zoomed in version of case_recursive_boxes_49 with different interior polygons 628 "MULTIPOLYGON(((0 0,0 4,2 4,2 6,4 6,4 8,10 8,10 4,8 4,8 0,0 0),(4 4,4 6,6 6,6 4,4 4)),((5 4.5,4 6,5.5 5.5,5 4.5)))", 629 "MULTIPOLYGON(((2 0,2 8,8 8,8 6,10 6,10 2,6 2,6 0,2 0),(6 6,6 4,4 4,4 6,6 6)),((5 4.5,4 6,5.5 5, 5 4.5)))" 630 }; 631 632 static std::string case_141_multi[2] = 633 { 634 // Version to test more isolation/validity cases 635 "MULTIPOLYGON(((0 0,0 10,10 10,10 0,0 0),(2 3,1 2,2 1,3 2,2 3),(2 7,3 8,2 9,1 8,2 7),(10 3,9 4,8 3,9 2,10 3),(7 10,6 9,7 8,8 9,7 10),(10 7,9 8,8 7,9 6,10 7)))", 636 "MULTIPOLYGON(((0 0,0 10,10 10,10 0,0 0),(0 5,2 3,4 5,2 7),(3 2,4 1,5 2,4 3,3 2),(3 8,4 7,5 8,4 9,3 8),(7 2,8 1,9 2,8 2,8 3,7 2),(8 7,7 8,6 7,7 6,8 7)))" 637 }; 638 639 static std::string case_recursive_boxes_1[2] = 640 { 641 "MULTIPOLYGON(((1 0,0 0,0 1,1 1,1 2,0 2,0 4,2 4,2 5,3 5,3 6,1 6,1 5,0 5,0 10,9 10,9 9,7 9,7 8,6 8,6 7,8 7,8 6,9 6,9 4,8 4,8 3,10 3,10 0,6 0,6 1,5 1,5 0,1 0),(8 4,8 5,7 5,7 6,6 6,6 5,5 5,5 4,4 4,4 3,5 3,5 2,7 2,7 3,6 3,6 4,8 4),(8 1,9 1,9 2,8 2,8 1),(4 7,4 9,3 9,3 7,4 7)),((9 9,10 9,10 7,10 6,9 6,9 7,8 7,8 8,9 8,9 9)))", 642 "MULTIPOLYGON(((5 6,5 7,3 7,3 9,2 9,2 8,1 8,1 10,4 10,4 9,6 9,6 10,10 10,10 9,9 9,9 8,10 8,10 6,9 6,9 5,10 5,10 3,7 3,7 4,6 4,6 6,5 6),(5 7,6 7,6 8,5 8,5 7),(7 7,7 6,8 6,8 7,7 7)),((1 0,0 0,0 7,2 7,2 6,5 6,5 5,4 5,4 4,5 4,5 3,7 3,7 2,6 2,6 0,1 0),(2 1,2 2,3 2,3 3,1 3,1 1,2 1)),((7 2,10 2,10 0,9 0,9 1,8 1,8 0,7 0,7 2)))" 643 }; 644 645 static std::string case_recursive_boxes_2[2] = 646 { 647 // Traversal problem; Many ii-cases -> formerly caused "Endless loop" 648 // So it appears that there might be more decisions than intersection points 649 "MULTIPOLYGON(((1 0,0 0,0 4,1 4,1 5,0 5,0 10,3 10,3 9,4 9,4 10,6 10,6 9,7 9,7 10,10 10,10 0,1 0),(6 9,5 9,5 8,6 8,6 9),(7 6,8 6,8 7,7 7,7 6),(8 7,9 7,9 8,8 8,8 7),(9 1,9 2,8 2,8 1,9 1)))", 650 "MULTIPOLYGON(((0 0,0 10,10 10,10 0,8 0,8 1,7 1,7 0,0 0),(7 3,6 3,6 2,7 2,7 3),(6 7,7 7,7 8,6 8,6 7)))" 651 }; 652 653 654 static std::string case_recursive_boxes_3[2] = 655 { 656 // Previously a iu/ux problem causing union to fail. 657 // For CCW polygon it also reports a iu/iu problem. 658 "MULTIPOLYGON(((8 3,9 4,9 3,8 3)),((5 9,5 10,6 10,5 9)),((2 0,2 1,3 0,2 0)),((2 5,2 6,3 6,3 5,2 5)),((2 2,1 2,1 3,2 3,3 2,3 1,2 1,2 2)),((6 8,7 9,7 7,8 7,7 6,6 6,6 8)),((4 6,5 7,5 6,4 6)),((4 8,4 9,5 9,5 8,4 8)),((0 3,1 4,1 3,0 3)),((8 7,9 8,9 7,8 7)),((9 6,9 7,10 7,9 6)),((7 0,8 1,8 0,7 0)),((0 4,0 5,1 5,1 4,0 4)),((4 2,5 3,5 2,4 1,4 2)),((4 10,4 9,2 9,3 10,4 10)),((5 2,6 3,7 3,7 2,6 2,6 1,5 0,5 2)),((5 3,4 3,4 4,2 4,4 6,4 5,4.5 4.5,6 6,6 5,7 4,5 4,5 3)),((10 2,9 1,9 3,10 2)),((8 4,7 4,8 5,7 5,7 6,9 6,9 5,10 5,10 4,8 4)),((1 7,0 7,0 8,1 8,1 7)),((1 10,2 10,1 9,0 9,0 10,1 10)),((6.5 9.5,7 10,7 9,6 9,6 10,6.5 9.5)),((8 8,8 9,10 9,9 8,8 8)))", 659 "MULTIPOLYGON(((7 3,7 4,8 5,8.5 4.5,9 5,9 4,10 3,8 3,7 3),(9 4,8 4,8.5 3.5,9 4)),((0 2,1 1,0 1,0 2)),((1 1,2 2,2 1,1 1)),((2 2,1 2,1 3,2 3,2 2)),((2 1,3 1,2 0,1 0,2 1)),((3 1,4 2,5 2,6 1,5 1,5 0,4 0,4 1,3 1)),((5 2,5 3,4 3,4 4,6 4,6 3,7 3,6 2,5 2)),((6 1,7 1,7 0,6 0,6 1)),((6 4,6 5,7 6,8 6,8 5,7 5,6 4)),((8 3,9 2,8 2,8 3)),((9 2,10 2,10 1,9 1,9 2)),((9 1,9 0,8 0,9 1)),((1 3,0 3,0 4,1 4,1 3)),((2 3,3 4,3 3,2 3)),((9 7,9 8,10 8,10 7,9 7)),((0 7,0 8,1 8,1 7,0 7)),((1 8,1 9,2 8,1 8)),((1 7,3 7,3 8,4 7,5 7,6 8,6 10,7 9,8 10,9 10,9 9,8 9,8 8,7 8,6 7,6 6,3 6,1 6,1 7)),((1 6,1 5,0 5,1 6)),((3 6,4 5,2 5,3 6)),((1 9,1 10,2 10,2 9,1 9)))" 660 }; 661 662 663 static std::string case_recursive_boxes_4[2] = 664 { 665 // Occurred after refactoring assemble 666 "MULTIPOLYGON(((0 1,0 3,1 4,0 4,0 5,1 6,0 6,0 8,1 9,0 9,0 10,6 10,7 10,7.5 9.5,8 10,8 9,9 9,9.5 8.5,10 9,10 8,9.5 7.5,10 7,10 5,9 5,9 3,10 2,10 1,9 1,10 0,4 0,4 1,3 1,3 0,1 0,1 1,0 0,0 1),(1 9,1 8,2 9,1 9),(2 9,2 8,3 9,2 9),(2 8,2 7,3 8,2 8),(2 7,1.5 6.5,2 6,2 7),(2 6,2.5 5.5,3 6,2 6),(3 6,3 5,4 6,3 6),(6 10,5.5 9.5,6 9,6 10),(8 9,7 9,7 8,8 8,8 9),(7 8,6 8,6.5 7.5,7 8),(9 5,8 5,8 4,9 5),(8 4,7 3,7 2,8 3,8 4),(9 1,8 1,8.5 0.5,9 1),(6 4,6.5 3.5,7 4,6 4),(4 2,4.5 1.5,5 2,5 3,4 3,4 2),(5 3,5 4,4.5 3.5,5 3),(5 7,5 9,4 9,4 8,5 7),(3 3,4 4,3 4,3 3),(3 4,2 4,2.5 3.5,3 4)),((9 3,10 4,10 3,9 3)),((10 9,9 9,10 10,10 9)))", 667 "MULTIPOLYGON(((1 0,0 0,0 3,1 3,1 4,0 4,0 8,1 7,1 9,0 9,0 10,7 10,6 9,6.5 8.5,7 9,8 9,9 8,8 8,9 7,9 6,10 7,10 5,10 0,7 0,8 1,7 1,6 0,3 0,3 1,2 1,1 1,1 0),(1 3,2 2,2 3,1 3),(1 4,2 4,2 5,1 4),(1 7,1 6,2 7,1 7),(10 5,9 5,9 4,10 5),(5 1,5.5 0.5,6 1,5 1),(6 1,6 2,5 2,6 1),(6 2,6.5 1.5,7 2,8 2,8 4,7 3,6 3,6 2),(6 5,7 6,7 7,6 7,6 5),(6 5,6.5 4.5,7 5,6 5),(4 4,5 4,5 5,4 4),(3 7,2 6,3 6,3 7),(3 7,4 6,4 7,3 7),(3.5 7.5,4 8,4 9,3 8,3.5 7.5)),((1 0,2 1,2 0,1 0)),((7 10,8 10,7 9,7 10)),((8 9,9 10,10 10,10 8,9 8,9 9,8 9)))" 668 }; 669 670 static std::string case_recursive_boxes_5[2] = 671 { 672 // Occurs after refactoring uu / handle_touch (not yet integrated) 673 "MULTIPOLYGON(((0 9,0 10,1 10,1 9,0 9)),((9 0,9 1,10 1,10 0,9 0)),((5 6,5 7,6 7,6 6,7 6,7 4,6 4,6 5,5 5,5 6)),((5 3,7 3,7 2,4 2,4 3,5 3)),((5 8,5 9,7 9,7 8,5 8)),((4 0,1 0,1 1,5 1,5 0,4 0)),((3 5,3 4,4 4,4 3,2 3,2 2,1 2,1 3,0 3,0 4,2 4,2 5,1 5,1 6,4 6,4 5,3 5)),((0 2,1 2,1 1,0 1,0 2)),((4 10,4 7,1 7,1 6,0 6,0 8,1 8,1 9,2 9,2 10,4 10)),((9 4,9 3,8 3,8 5,9 5,9 4)),((7 2,8 2,8 0,7 0,7 2)),((8 7,10 7,10 6,7 6,7 8,8 8,8 7)))", 674 "MULTIPOLYGON(((2 6,2 8,3 8,3 7,5 7,5 6,6 6,6 5,8 5,8 6,9 6,9 4,8 4,8 3,7 3,7 4,6 4,6 3,5 3,5 4,3 4,3 6,2 6),(5 6,4 6,4 5,5 5,5 6)),((1 1,2 1,2 0,1 0,1 1)),((2 1,2 2,3 2,3 1,2 1)),((2 2,1 2,1 3,2 3,2 2)),((1 3,0 3,0 5,1 5,1 4,1 3)),((1 5,1 6,2 6,2 5,1 5)),((2 8,0 8,0 10,3 10,4 10,4 9,2 9,2 8)),((8 6,7 6,7 7,8 7,8 6)),((8 7,8 10,9 10,9 9,10 9,10 8,9 8,9 7,8 7)),((9 7,10 7,10 6,9 6,9 7)),((9 4,10 4,10 3,10 1,9 1,9 2,8 2,8 3,9 3,9 4)),((8 2,8 1,7 1,7 2,8 2)),((8 1,9 1,9 0,8 0,8 1)),((7 1,7 0,5 0,3 0,3 1,4 1,4 2,6 2,6 1,7 1)),((6 2,6 3,7 3,7 2,6 2)),((3 4,3 3,2 3,2 4,3 4)),((6 8,6 9,7 9,7 8,6 8)))" 675 }; 676 677 static std::string case_recursive_boxes_6[2] = 678 { 679 // [1] is reported as invalid by BG, but not by postgis 680 // Fixed by replacing handle_tangencies 681 "MULTIPOLYGON(((0 3,1 3,1 4,2 4,2 5,5 5,5 0,2 0,0 0,0 3),(2 0,2 1,1 1,2 0),(2 1,2 2,1.5 1.5,2 1),(2 2,3 1,3 2,2 2),(3 2,3.5 1.5,4 2,3 2)),((0 3,0 5,1 5,2 5,1 4,0 3)))", 682 "MULTIPOLYGON(((1 2,2 3,1 3,1 4,0 4,0 5,5 5,5 2,4 2,3 2,3 1,2 1,2 2,1 2),(4 2,4 3,3 3,4 2)),((1 2,2 1,3 0,2 0,0 0,0 3,1 3,1 2)),((3 0,3 1,4 2,4 1,5 1,5 0,4 0,3 0)))" 683 }; 684 685 static std::string case_recursive_boxes_7[2] = 686 { 687 "MULTIPOLYGON(((3 1,3 2,4 2,4 1,3 1)),((2.5 2.5,3 3,3 2,2 2,2 3,2.5 2.5)),((2 1,3 0,1 0,1 2,2 2,2 1)))", 688 "MULTIPOLYGON(((0 0,1 1,1 0,0 0)),((0 1,0 2,1 2,0 1)),((3.5 2.5,4 3,4 2,3 2,3 3,3.5 2.5)),((3 2,4 1,1 1,1 2,3 2)))" 689 }; 690 691 static std::string case_recursive_boxes_8[2] = 692 { 693 // Having colocated IP halfway segment 694 "MULTIPOLYGON(((3 4,3 3,2 3,2 2,0 2,0 3,1 3,1 4,1.5 3.5,2 4,3 4)),((2 5,2 4,1 4,0 3,0 5,2 5)))", 695 "MULTIPOLYGON(((0 2,0 4,3 4,4 4,4 3,3 3,3 1,0 1,0 2),(0 2,1 2,1 3,0 2)))" 696 }; 697 698 static std::string case_recursive_boxes_9[2] = 699 { 700 // Needs ii turn skipping 701 "MULTIPOLYGON(((2 2,3 2,3 0,2 0,2 1,1 1,2 2)),((1 1,1 0,0 0,0 3,0.5 2.5,1 3,2 2,1 2,1 1)))", 702 "MULTIPOLYGON(((2 1,2 2,0 2,0 3,2 3,3 2,3 1,2 1)),((2.5 0.5,3 1,3 0,0 0,0 1,1 1,1 2,2.5 0.5)))" 703 }; 704 705 static std::string case_recursive_boxes_10[4] = 706 { 707 // Requires skipping ux for difference (a) and switching a->b 708 "MULTIPOLYGON(((2 2,2 3,3 2,2 2)),((2 2,3 1,1 1,1 2,2 2)))", 709 "MULTIPOLYGON(((3 2,2 1,2 3,3 3,3 2)))", 710 711 // Inverse versions 712 "MULTIPOLYGON(((0 0,0 4,4 4,4 0,0 0),(2 2,3 2,2 3,2 2),(2 2,1 2,1 1,3 1,2 2)))", 713 "MULTIPOLYGON(((1 0,1 4,4 4,4 0,1 0),(3 2,3 3,2 3,2 1,3 2)))" 714 }; 715 716 static std::string case_recursive_boxes_11[4] = 717 { 718 // Requires switching a->b 719 "MULTIPOLYGON(((3 2,5 2,5 1,4 1,4 0,3 0,3 1,2 1,3 2)))", 720 "MULTIPOLYGON(((5 2,4 1,4 3,5 2)),((3 1,3 2,4 2,3 1)),((4 1,5 1,5 0,4 0,4 1)),((3 2,2 1,3 1,2 0,1 1,2 2,2 3,3 3,3 2)))", 721 722 // Inverse versions 723 "MULTIPOLYGON(((0 -1,0 4,6 4,6 -1,0 -1),(3 2,2 1,3 1,3 0,4 0,4 1,5 1,5 2,3 2)))", 724 "MULTIPOLYGON(((0 -1,0 4,6 4,6 -1,0 -1),(5 2,4 3,4 1,5 2),(3 1,4 2,3 2,3 1),(4 1,4 0,5 0,5 1,4 1),(3 2,3 3,2 3,2 2,1 1,2 0,3 1,2 1,3 2)))" 725 }; 726 727 static std::string case_recursive_boxes_12[2] = 728 { 729 "MULTIPOLYGON(((0 3,1 3,0.5 2.5,1 2,0 2,0 3)),((1 2,2 2,2 1,1 1,1 2)),((2 1,3 2,3 1,2 1)),((2 2,2 3,3 3,2 2)),((0 0,0 1,1 0,0 0)))", 730 "MULTIPOLYGON(((0 1,0 2,1 2,0 1)),((0 1,1 1,1.5 0.5,2 1,2 0,0 0,0 1)),((1 3,1 4,2 3,1 2,1 3)))" 731 }; 732 733 static std::string case_recursive_boxes_13[2] = 734 { 735 "MULTIPOLYGON(((1 3,1 5,2 5,2 4,1.5 3.5,2 3,1 3)),((1 3,2 2,0 2,1 3)),((2 2,3 2,3 1,2 1,2 2)),((3 2,3 3,4 3,4 2,3 2)))", 736 "MULTIPOLYGON(((1 4,1 3,0 3,0 4,1 5,1 4)),((3 5,4 5,4 4,2 4,2 5,3 5)),((3 1,3 2,5 2,5 1,3 1)))" 737 }; 738 739 static std::string case_recursive_boxes_14[2] = 740 { 741 "MULTIPOLYGON(((2 2,2 3,3 2,2 2)),((2 3,3 4,3 3,2 3)),((2 3,1 3,1 4,2 4,2 3)))", 742 "MULTIPOLYGON(((3 3,4 4,4 3,3 3)),((1 2,2 3,2 2,1 2)),((2 1,2 2,3 1,2 1)),((1 4,1 5,2 5,2 4,1 4)))" 743 }; 744 745 static std::string case_recursive_boxes_12_invalid[2] = 746 { 747 // One of them is invalid requiring discarding turns colocated with uu in these clusters 748 "MULTIPOLYGON(((2 2,2 3,3 3,2 2)),((0 0,0 1,1 0,0 0)),((0 3,1 3,0.5 2.5,1 2,0 2,0 3)),((3 2,3 1,1 1,1 2,2 2,2 1,3 2)))", 749 "MULTIPOLYGON(((0 1,0 2,1 2,0 1)),((0 1,1 1,1.5 0.5,2 1,2 0,0 0,0 1)),((1 3,1 4,2 3,1 2,1 3)))" 750 }; 751 752 static std::string case_recursive_boxes_13_invalid[2] = 753 { 754 // Strictly invalid, requires checking seg_id while considering skipping to next turn 755 "MULTIPOLYGON(((2 1,2 2,3 2,3 1,2 1)),((3 2,3 3,4 3,4 2,3 2)),((2 4,1.5 3.5,2 3,1 3,2 2,0 2,1 3,1 5,2 5,2 4)))", 756 "MULTIPOLYGON(((1 4,1 3,0 3,0 4,1 5,1 4)),((3 5,4 5,4 4,2 4,2 5,3 5)),((3 1,3 2,5 2,5 1,3 1)))" 757 }; 758 759 static std::string case_recursive_boxes_14_invalid[2] = 760 { 761 // Strictly invalid, requires skipping assignment of discarded turns for clusters 762 "MULTIPOLYGON(((2 2,2 3,3 2,2 2)),((2 4,2 3,3 4,3 3,1 3,1 4,2 4)))", 763 "MULTIPOLYGON(((3 3,4 4,4 3,3 3)),((1 2,2 3,2 2,1 2)),((2 1,2 2,3 1,2 1)),((1 4,1 5,2 5,2 4,1 4)))" 764 }; 765 766 767 static std::string case_recursive_boxes_15[2] = 768 { 769 // Requires inspecting blocked operations in traversing cluster 770 "MULTIPOLYGON(((3 2,3 3,4 3,3 2)),((4 1,4 2,5 2,5 1,4 1)),((4 2,4 3,5 3,4 2)),((3 5,4 4,2 4,2 5,3 5)))", 771 "MULTIPOLYGON(((3 4,4 3,3 2,3 3,2 3,2 4,3 4)),((4 3,4 4,5 4,5 3,4 3)))" 772 }; 773 774 static std::string case_recursive_boxes_16[2] = 775 { 776 // Requires inspecting if traverse is possible in selecting continue operation 777 "MULTIPOLYGON(((2 4,1 3,0 3,0 5,3 5,3 4,2 4)),((3 4,4 4,4 5,5 5,5 4,4 3,2 3,3 4)),((2.5 1.5,3 1,2.5 0.5,3 0,0 0,0 2,3 2,2.5 1.5)),((3 1,3 2,4 2,4 1,5 2,5 0,3 0,3 1)))", 778 "MULTIPOLYGON(((0 1,1 1,1 0,0 0,0 1)),((0 1,0 5,1 5,1 3,2 3,2 2,1 1,1 2,0 1)),((2 2,3 1,2 1,2 2)),((3 1,3 2,4 1,5 1,5 0,3 0,3 1)),((4 1,4 2,3 2,3 4,2 4,2 5,3 5,5 5,5 4,4 4,4 3,5 3,5 2,4 1)))" 779 }; 780 781 static std::string case_recursive_boxes_17[2] = 782 { 783 // Requires including uu turns, at least in clusters 784 "MULTIPOLYGON(((0 4,0 5,1 5,0 4)),((1 5,1.5 4.5,2 5,2 4,1 3,1 5)),((2 4,3 4,3 3,2 2,1 2,1 3,2 3,2 4)),((1 2,1 1,2 1,3 0,0 0,0 2,1 2)),((2 1,2 2,2.5 1.5,4 3,5 3,5 1,4 1,4 0,3 0,3 1,2 1)),((4 0,5 1,5 0,4 0)),((3 4,3 5,4 5,5 5,5 4,3 4)))", 785 "MULTIPOLYGON(((2 5,3 5,2 4,2 5)),((3 1,4 2,4 0,3 0,3 1)),((2 0,0 0,0 1,1 2,0 2,1 3,2 2,2 3,3 2,3 1,2 0)),((1 4,0.5 3.5,1 3,0 3,0 4,1 4)),((4 3,3 3,3 5,4 5,4 4,5 4,5 2,4 2,4 3)))" 786 }; 787 788 static std::string case_recursive_boxes_18[2] = 789 { 790 // Simple case having two colocated uu turns 791 "MULTIPOLYGON(((2 1,3 0,2 0,2 1)),((2 1,1 1,1 2,2 1)))", 792 "MULTIPOLYGON(((2 2,2 3,3 3,3 2,2 1,2 2)))" 793 }; 794 795 static std::string case_recursive_boxes_19[2] = 796 { 797 // Simple case having two colocated uu and ux turns 798 "MULTIPOLYGON(((1 4,2 3,1 3,1 4)),((1 4,0 4,0 5,1 4)))", 799 "MULTIPOLYGON(((3 4,1 4,2 5,3 4)),((1 4,1 3,0 3,1 4)))" 800 }; 801 802 static std::string case_recursive_boxes_20[2] = 803 { 804 // Simple case having two colocated uu and (discarded) cc turns 805 "MULTIPOLYGON(((4 4,4 5,5 5,5 4,4 4)),((4 4,4 3,3 3,3 4,4 4)))", 806 "MULTIPOLYGON(((4 4,4 3,3 3,4 4)),((4 4,4 5,5 4,4 4)))" 807 }; 808 809 static std::string case_recursive_boxes_21[2] = 810 { 811 // Having colocated uu/ux/cc turns requiring traversing through arcs to 812 // find first open outgoing arc for union 813 "MULTIPOLYGON(((3 1,3 2,4 1,3 1)),((3 1,3 0,2 0,2 1,3 1)))", 814 "MULTIPOLYGON(((3 1,3 0,2 0,3 1)),((3 1,2 1,2 2,3 2,3 1)))" 815 }; 816 817 static std::string case_recursive_boxes_22[2] = 818 { 819 // Requires including ux turns for intersections to block paths 820 "MULTIPOLYGON(((2 2,3 2,2.5 1.5,3 1,2 1,2 2)),((2 2,2 3,3 3,2 2)))", 821 "MULTIPOLYGON(((1 2,0 2,0 3,1 2)),((1 2,2 3,2 1,1 1,1 2)))" 822 }; 823 824 static std::string case_recursive_boxes_23[2] = 825 { 826 // Requires discarding turns with uu for intersection/difference too 827 "MULTIPOLYGON(((4 3,4 4,4.5 3.5,5 4,5 3,4 3)),((4 3,5 2,4 2,4 3)))", 828 "MULTIPOLYGON(((4 3,5 4,5 3,4 3)),((3 3,3 4,4 3,3 3)))" 829 }; 830 831 static std::string case_recursive_boxes_24[2] = 832 { 833 // Requires including all combinations in clusters having uu 834 "MULTIPOLYGON(((0 2,0 3,1 2,0 2)),((2 3,1 3,1 4,2 4,2 3)),((2 3,4 3,3 2,2 2,2 3)))", 835 "MULTIPOLYGON(((3 2,4 1,2 1,3 2)),((3 2,2 2,2 3,3 2)),((2 2,2 1,1 1,1 2,2 2)))" 836 }; 837 838 static std::string case_recursive_boxes_25[2] = 839 { 840 // Requires startable flag per operation, assigned per cluster 841 "MULTIPOLYGON(((4 1,4 2,5 2,5 1,4 0,4 1)),((3 2,3 3,4 3,4 2,3 2)),((3 2,3 1,2 1,3 2)))", 842 "MULTIPOLYGON(((4 2,4 1,3 1,4 2)),((4 2,4 3,5 2,4 2)),((3 1,1 1,1 2,3 2,3 1)))" 843 }; 844 845 static std::string case_recursive_boxes_26[2] = 846 { 847 // Requires not including uu outside clusters (or travel through them) 848 "MULTIPOLYGON(((2 4,3 4,3 3,0 3,1 4,1 5,2 5,2 4)),((1 3,1 2,0 2,1 3)))", 849 "MULTIPOLYGON(((2 3,0 3,0 4,1 4,1 5,3 5,3 4,2 4,2 3)),((2 3,3 2,2 2,2 3)))" 850 }; 851 852 static std::string case_recursive_boxes_27[2] = 853 { 854 // Combination of lonely uu-turn (which is discarded) and a cluster containing it 855 "MULTIPOLYGON(((2 2,3 1,3 0,2 0,2 2)),((2 2,1 2,1 3,2 2)))", 856 "MULTIPOLYGON(((1 2,0 1,0 2,1 2)),((2 1,2 0,1 0,1 1,2 2,2 1)),((1 3,2 2,1 2,1 3)),((1 3,0 3,1 4,1 3)))" 857 }; 858 859 static std::string case_recursive_boxes_28[2] = 860 { 861 // Requires startable flag per operation, assigned per cluster (as #25 but in a different configuration) 862 "MULTIPOLYGON(((5 1,5 0,4 0,4 2,5 3,5 1)),((4 2,3 2,3 3,4 3,4 2)))", 863 "MULTIPOLYGON(((2 2,2 3,3 3,4 2,3 1,2 1,2 2)),((3 4,4 3,3 3,3 4)),((4 2,5 2,4 1,4 2)))" 864 }; 865 866 static std::string case_recursive_boxes_29[2] = 867 { 868 // Requires not discarding colocated cc turns 869 "MULTIPOLYGON(((2 3,2 4,1 4,2 5,4 5,4 4,3 4,3 3,2 3)),((3 3,4 3,4 1,5 1,5 0,3 0,3 2,2 2,3 3)),((1 2,0 2,0 3,1 3,1 2)),((1 1,0 1,1 2,2 2,2 1,1 1)),((2 1,2 0,1 0,2 1)))", 870 "MULTIPOLYGON(((0 4,0 5,1 4,0 4)),((2 3,2 4,4 4,4 3,2 3)),((2 2,1 2,1 3,2 3,2 2)),((1 2,0 2,0 3,1 3,0.5 2.5,1 2)),((1 0,0 0,1 1,4 1,4 0,1 0)),((4 0,5 1,5 0,4 0)))" 871 }; 872 873 static std::string case_recursive_boxes_30[2] = 874 { 875 // Requires not discarding turns colocated with uu/invalid polygons (now not necessary anymore because of startable) 876 "MULTIPOLYGON(((2 2,2 3,4 3,4 4,4.5 3.5,5 4,5 0,3 0,3 1,4 1,4 2,2 2)),((1 5,3 5,4 4,0 4,0 5,1 5)))", 877 "MULTIPOLYGON(((2 1,2 3,1 3,1 4,2 5,2 4,3 4,3 5,5 5,5 4,4 4,5 3,4.5 2.5,5 2,5 0,4 0,4 1,3 1,3 0,1 0,2 1),(4 4,3.5 3.5,4 3,4 4),(4 1,4 2,3 2,4 1),(3 2,3 3,2.5 2.5,3 2)))" 878 }; 879 880 static std::string case_recursive_boxes_31[2] = 881 { 882 // Requires allowing traverse through clusters having only uu/cc for intersection 883 "MULTIPOLYGON(((1 4,1 1,0 1,0 4,1 4)),((1 1,2 1,2 0,1 0,1 1)),((2 2,1 2,2 3,2 2)))", 884 "MULTIPOLYGON(((2 3,2 2,1 2,2 3)),((0 1,0 3,1 3,1 1,0 1)),((1 1,1 0,0 0,1 1)))" 885 }; 886 887 static std::string case_recursive_boxes_32[2] = 888 { 889 // Similar to #31 but here uu/ux/cc 890 "MULTIPOLYGON(((1 3,2 3,2 2,1 1,1 3)),((2 2,3 1,3 0,2 0,2 2)),((1 1,2 1,1 0,0 0,0 1,1 1)))", 891 "MULTIPOLYGON(((3 1,3 0,2 0,2 2,3 1)),((1 1,0 1,0 2,1 2,2 1,1 1)))" 892 }; 893 894 static std::string case_recursive_boxes_33[2] = 895 { 896 // Similar to #31 but here also a ui 897 "MULTIPOLYGON(((4 3,5 3,5 2,3 2,4 3)),((4 2,5 1,3 1,4 2)),((2 1,3 1,3 0,2 0,2 1)),((3 2,1 2,1 3,2 3,3 2)))", 898 "MULTIPOLYGON(((3 1,2 1,2 4,4 4,4 3,5 2,3 2,3 1)),((3 1,4 2,4 1,5 1,5 0,3 0,3 1)))" 899 }; 900 901 static std::string case_recursive_boxes_34[2] = 902 { 903 // Requires detecting finished arcs during cluster traversal 904 "MULTIPOLYGON(((2 0,0 0,0 5,2 5,2 4,3 5,5 5,5 0,2 0)))", 905 "MULTIPOLYGON(((1 0,0 0,0 5,1 4,1 5,4 5,5 4,5 1,4 1,4 3,3 3,2 3,2 2,3 2,3 1,2 0,1 0),(1 0,2 1,1 1,1 0),(4 5,3 4,3.5 3.5,4 4,4 5)),((4 1,3 0,3 1,4 1)))" 906 }; 907 908 static std::string case_recursive_boxes_35[2] = 909 { 910 // Requires detecting finished arcs during cluster traversal 911 "MULTIPOLYGON(((0 2,0 5,4 5,4 4,5 4,5 1,4 1,5 0,3 0,0 0,0 2),(0 2,1 2,1 3,0 2),(3 0,3 1,2 1,3 0),(2.5 1.5,3 2,2 2,2.5 1.5),(2 4,1 4,2 3,2 4)))", 912 "MULTIPOLYGON(((1 0,0 0,0 5,3 5,5 5,5 0,1 0),(1 0,2 1,1 1,1 0),(2 1,2 2,1.5 1.5,2 1),(3 5,2.5 4.5,3 4,3 5),(3 2,3 3,2.5 2.5,3 2),(2 3,2 4,1 4,1 3,2 3)))" 913 }; 914 915 static std::string case_recursive_boxes_36[2] = 916 { 917 // Requires increasing target rank while skipping finished arcs to avoid duplicate output 918 "MULTIPOLYGON(((5 3,4 3,4 4,5 3)),((5 2,4 2,5 3,5 2)),((5 2,5 1,4 1,5 2)))", 919 "MULTIPOLYGON(((4 2,4 3,5 3,5 2,4 2)),((4 2,4 1,3 1,3 2,4 2)))" 920 }; 921 922 static std::string case_recursive_boxes_37[2] = 923 { 924 // [1] is reported as invalid by BG, but not by postgis 925 // Requires skipping arc for union too, to avoid duplicate hole 926 "MULTIPOLYGON(((4 0,5 1,5 0,4 0)),((2 0,3 1,3 0,2 0)),((2 3,2 2,1 2,1 3,2 3)),((2 1,2 2,4 2,3 1,2 1)))", 927 "MULTIPOLYGON(((3 1,4 2,4 3,5 3,5 0,3 0,3 1),(3 1,3.5 0.5,4 1,3 1)),((3 1,2 0,2 1,3 1)),((2 3,1 2,1 3,2 3)))" 928 }; 929 930 static std::string case_recursive_boxes_38[2] = 931 { 932 // Smaller version of 29, removing generated lower interior in a union 933 "MULTIPOLYGON(((2 3,2 4,1 4,2 5,4 5,4 4,3 4,3 3,2 3)),((3 3,4 3,4 1,5 1,5 0,3 0,3 2,2 2,3 3)),((1 2,0 2,0 3,1 3,1 2)),((1 1,0 1,1 2,2 2,2 1,1 1)))", 934 "MULTIPOLYGON(((2 2,4 2,4 1,2 1,2 2)),((0 4,0 5,1 4,0 4)),((2 3,2 4,4 4,4 3,2 3)),((2 2,1 2,1 3,2 3,2 2)),((1 2,0 2,0 3,1 3,0.5 2.5,1 2)))" 935 }; 936 937 static std::string case_recursive_boxes_39[2] = 938 { 939 // Needs check for back at start during traversal 940 "MULTIPOLYGON(((3 8,2 8,2 9,3 9,3 8)),((4 8,4 9,5 9,5 8,4 8)),((6 9,6 10,7 10,7 9,6 9)),((5 6,4 6,4 7,6 7,6 5,5 5,5 6)),((4 7,3 7,3 8,4 8,4 7)),((7 8,8 8,8 7,6 7,6 8,7 8)))", 941 "MULTIPOLYGON(((3 7,3 6,2 6,2 7,3 7)),((4 8,4 7,3 7,3 8,4 8)),((6 10,7 10,7 9,5 9,5 10,6 10)),((5 8,4 8,4 9,5 9,5 8)),((5 8,6 8,6 7,5 7,5 8)))" 942 }; 943 944 static std::string case_recursive_boxes_40[2] = 945 { 946 "MULTIPOLYGON(((8 7,9 7,9 6,7 6,7 7,8 7)),((6 4,7 4,7 3,6 3,6 4)),((6 4,5 4,5 5,6 5,6 4)),((3 6,3 7,4 7,4 6,3 6)),((3 6,3 5,2 5,2 6,3 6)),((1 0,1 1,2 1,2 0,1 0)),((7 9,8 9,8 8,6 8,6 9,7 9)),((6 8,6 7,5 7,5 8,6 8)),((5 1,5 0,3 0,3 1,5 1)),((5 1,5 2,6 2,6 1,5 1)),((4 3,4 4,5 4,5 3,4 3)),((4 3,4 2,3 2,3 3,4 3)))", 947 "MULTIPOLYGON(((7 2,7 3,8 3,8 2,7 2)),((5 9,5 10,6 10,6 9,5 9)),((7 0,6 0,6 2,7 2,7 1,8 1,8 0,7 0)),((5 3,5 4,6 4,6 3,5 3)),((7 4,7 5,8 5,8 4,7 4)),((2 2,2 1,1 1,1 2,2 2)),((2 2,2 3,3 3,3 2,2 2)),((4 7,4 6,3 6,3 7,4 7)),((5 5,4 5,4 6,5 6,5 7,6 7,6 5,5 5)),((5 7,4 7,4 8,5 8,5 7)))" 948 }; 949 950 static std::string case_recursive_boxes_41[2] = 951 { 952 // Smaller version of 35 for validity checks 953 "MULTIPOLYGON(((0 2,0 5,5 5,5 1,5 0,3 0,0 0,0 2),(0 2,1 2,1 3,0 2),(2 4,1 4,2 3,2 4)))", 954 "MULTIPOLYGON(((0 0,0 5,5 5,5 0,0 0),(2 3,2 4,1 4,1 3,2 3)))" 955 }; 956 957 static std::string case_recursive_boxes_42[2] = 958 { 959 // Smaller version of 2 for validity checks 960 "MULTIPOLYGON(((0 0,0 10,6 10,6 9,7 9,7 10,10 10,10 0,0 0),(6 9,5 9,5 8,6 8,6 9),(7 6,8 6,8 7,7 7,7 6),(8 7,9 7,9 8,8 8,8 7)))", 961 "MULTIPOLYGON(((0 0,0 10,10 10,10 0,0 0),(6 7,7 7,7 8,6 8,6 7)))" 962 }; 963 964 static std::string case_recursive_boxes_43[2] = 965 { 966 // Smaller version of 35 for validity checks 967 "MULTIPOLYGON(((0 2,0 5,4 5,4 4,5 4,5 1,4 1,5 0,3 0,0 0,0 2),(3 0,3 1,2 1,3 0)))", 968 "MULTIPOLYGON(((1 0,0 0,0 5,3 5,5 5,5 0,1 0),(1 0,2 1,1 1,1 0)))" 969 }; 970 971 static std::string case_recursive_boxes_44[2] = 972 { 973 // Needs discarding uu turns in intersections, either globally or in aggregations 974 "MULTIPOLYGON(((4 1,5 1,5 0,4 0,4 1)),((4 1,2 1,2 2,4 2,4 1)),((2 2,1 2,1 1,2 1,2 0,0 0,0 3,2 3,2 2)))", 975 "MULTIPOLYGON(((2 1,2 2,3 2,3 1,2 1)),((1 0,0 0,0 1,2 1,2 0,1 0)))" 976 }; 977 978 static std::string case_recursive_boxes_45[2] = 979 { 980 // Needs discarding u/x turns in aggregations (for clusters for intersections) 981 // This case did go wrong, don't make it smaller, it also depends on the order of turns 982 "MULTIPOLYGON(((5 2,5 3,4 3,4 6,6 6,6 5,8 5,8 1,5 1,5 2)),((4 7,4 6,1 6,1 4,0 4,0 7,2 7,2 8,3 8,3 7,4 7)),((3 3,2 3,2 5,3 5,3 3)),((3 3,4 3,4 0,3 0,3 1,2 1,2 2,3 2,3 3)),((1 1,2 1,2 0,1 0,1 1)),((1 1,0 1,0 2,1 2,1 1)),((2 3,2 2,1 2,1 3,2 3)))", 983 "MULTIPOLYGON(((5 1,4 1,4 2,7 2,7 1,5 1)),((7 6,7 4,6 4,6 3,4 3,4 4,3 4,3 5,6 5,6 6,3 6,3 8,2 8,2 9,7 9,7 6)),((3 4,3 2,1 2,1 1,0 1,0 4,1 4,1 3,2 3,2 4,3 4)),((4 1,4 0,2 0,2 1,4 1)),((2 4,1 4,1 5,2 5,2 4)))" 984 }; 985 986 static std::string case_recursive_boxes_46[2] = 987 { 988 "MULTIPOLYGON(((8 9,8 10,9 10,9 9,8 9)),((5 5,5 4,3 4,3 5,5 5)),((5 5,5 6,6 6,6 5,5 5)),((5 9,6 9,6 10,7 10,7 8,9 8,9 5,10 5,10 4,9 4,6 4,6 5,7 5,7 6,6 6,6 8,3 8,3 9,4 9,4 10,5 10,5 9),(7 6,8 6,8 7,7 7,7 6)))", 989 "MULTIPOLYGON(((5 10,6 10,6 9,5 9,5 10)),((5 3,4 3,4 7,7 7,7 6,8 6,8 3,5 3),(5 5,5 4,7 4,7 6,6 6,6 5,5 5)),((9 7,9 6,8 6,8 7,9 7)),((9 7,9 9,8 9,8 10,10 10,10 7,9 7)),((8 9,8 8,7 8,7 9,8 9)))" 990 }; 991 992 static std::string case_recursive_boxes_47[2] = 993 { 994 // Needs open_count==0 in get_ring_turn_info to select_rings 995 "MULTIPOLYGON(((5 4,6 4,6 3,4 3,4 5,5 5,5 4)),((5 5,5 6,6 6,6 5,5 5)),((5 6,3 6,3 7,4 7,4 8,7 8,7 6,6 6,6 7,5 7,5 6)),((6 4,6 5,7 5,7 4,6 4)))", 996 "MULTIPOLYGON(((4 5,4 4,1 4,1 5,4 5)),((5 6,5 7,6 7,6 6,5 6)),((5 6,5 5,4 5,4 6,5 6)),((5 3,5 5,6 5,6 3,5 3)),((5 3,5 2,4 2,4 3,5 3)),((6 5,6 6,7 6,7 5,6 5)),((3 7,2 7,2 9,3 9,3 8,4 8,4 7,3 7)))" 997 }; 998 999 static std::string case_recursive_boxes_48[2] = 1000 { 1001 // Needs discarding self-ii turns not located within the other geometry 1002 "MULTIPOLYGON(((6 7,6 8,7 8,7 7,6 7)))", 1003 "MULTIPOLYGON(((9 9,10 9,10 7,9 7,9 5,8 5,8 6,7 6,7 7,6 7,6 8,7 8,7 9,8 9,8 10,9 10,9 9),(9 8,8 8,8 7,9 7,9 8)))" 1004 }; 1005 1006 static std::string case_recursive_boxes_49[2] = 1007 { 1008 // Needs specific handling for cc interior rings touching one exterior ring 1009 "MULTIPOLYGON(((5 2,5 3,4 3,4 4,5 4,5 5,6 5,6 2,7 2,7 1,0 1,0 3,1 3,1 2,5 2)),((5 7,5 8,6 8,6 9,7 9,7 10,10 10,10 8,9 8,9 6,10 6,10 4,9 4,9 3,8 3,8 4,7 4,7 6,5 6,5 7),(7 6,8 6,8 7,7 7,7 6),(8 9,7 9,7 8,8 8,8 9)),((2 6,4 6,4 5,3 5,3 4,1 4,1 5,2 5,2 6)),((3 10,4 10,4 7,2 7,2 10,3 10)))", 1010 "MULTIPOLYGON(((5 1,4 1,4 3,3 3,3 6,2 6,2 9,5 9,5 7,4 7,4 4,5 4,5 3,6 3,6 2,8 2,8 1,9 1,9 0,5 0,5 1),(4 7,4 8,3 8,3 7,4 7)),((8 2,8 3,9 3,9 2,8 2)),((9 5,9 6,10 6,10 5,9 5)),((9 5,9 4,8 4,8 5,9 5)),((7 5,7 4,6 4,6 5,7 5)),((7 10,9 10,9 9,10 9,10 7,8 7,8 6,6 6,6 10,7 10),(7 9,7 8,8 8,8 9,7 9)))" 1011 }; 1012 1013 static std::string case_recursive_boxes_50[2] = 1014 { 1015 // Same as 49 but needs the second variant 1016 "MULTIPOLYGON(((6 9,6 10,7 10,7 9,6 9)),((5 6,6 6,6 5,4 5,4 7,3 7,3 8,4 8,4 9,2 9,2 10,5 10,5 8,6 8,6 7,5 7,5 6)),((4 0,1 0,1 1,2 1,2 2,3 2,3 3,5 3,5 0,4 0)),((3 5,3 3,1 3,1 4,0 4,0 6,1 6,1 7,0 7,0 8,2 8,2 6,3 6,3 5),(2 5,1 5,1 4,2 4,2 5)),((1 1,0 1,0 2,1 2,1 1)),((6 5,7 5,7 4,6 4,6 5)),((10 5,8 5,8 6,9 6,9 7,10 7,10 5)),((6 0,6 1,8 1,8 2,10 2,10 0,6 0)),((9 7,7 7,7 8,8 8,8 9,9 9,9 7)),((8 2,6 2,6 3,8 3,8 2)),((9 9,9 10,10 10,10 9,9 9)))", 1017 "MULTIPOLYGON(((5 3,5 4,6 4,6 3,5 3)),((5 7,6 7,6 5,4 5,4 6,3 6,3 7,4 7,4 8,5 8,5 7)),((3 6,3 4,4 4,4 3,1 3,1 2,0 2,0 9,1 9,1 10,3 10,3 9,2 9,2 8,3 8,3 7,1 7,1 6,3 6),(1 5,1 4,2 4,2 5,1 5)),((4 0,0 0,0 1,1 1,1 2,3 2,3 1,5 1,5 0,4 0)),((7 6,7 7,8 7,8 8,9 8,9 6,8 6,8 5,7 5,7 6)),((9 0,7 0,7 1,9 1,9 2,10 2,10 0,9 0)),((7 9,5 9,5 10,7 10,7 9)),((7 9,8 9,8 8,7 8,7 9)),((8 3,8 2,7 2,7 3,8 3)),((8 3,8 4,9 4,9 3,8 3)),((8 9,8 10,9 10,9 9,8 9)),((9 8,9 9,10 9,10 8,9 8)))" 1018 }; 1019 1020 static std::string case_recursive_boxes_51[2] = 1021 { 1022 // Needs keeping colocated turns with a xx turn to properly generate interior rings. It also needs self-turns for validity 1023 "MULTIPOLYGON(((0 4,0 5,1 5,1 4,0 4)),((2 1,3 1,3 0,2 0,2 1)),((3 3,4 3,4 2,3 2,3 3)),((5 4,6 4,6 3,5 3,5 4)),((2 3,2 4,3 4,3 3,2 3)),((5 6,4 6,4 5,3 5,3 10,4 10,4 9,5 9,5 8,4 8,4 7,6 7,6 9,7 9,7 10,8 10,8 8,7 8,7 7,8 7,8 4,7 4,7 5,6 5,6 6,5 6)),((5 0,4 0,4 1,5 1,5 2,6 2,6 3,7 3,7 1,8 1,8 0,5 0)),((0 2,1 2,1 1,0 1,0 2)),((1 2,1 3,2 3,2 2,1 2)),((1 10,2 10,2 8,1 8,1 9,0 9,0 10,1 10)),((1 8,1 7,0 7,0 8,1 8)),((10 1,10 0,9 0,9 1,8 1,8 4,9 4,9 6,10 6,10 1)))", 1024 "MULTIPOLYGON(((3 1,4 1,4 0,2 0,2 1,3 1)),((1 9,0 9,0 10,1 10,1 9)),((8 2,9 2,9 1,10 1,10 0,8 0,8 2)),((5 8,4 8,4 9,5 9,5 10,7 10,7 8,8 8,8 7,7 7,7 6,8 6,8 7,10 7,10 6,9 6,9 3,8 3,8 2,6 2,6 1,5 1,5 3,7 3,7 4,4 4,4 5,5 5,5 6,6 6,6 8,5 8),(7 5,7 4,8 4,8 5,7 5)),((4 4,4 3,2 3,2 4,1 4,1 5,0 5,0 7,1 7,1 9,2 9,2 8,4 8,4 6,3 6,3 4,4 4),(1 5,2 5,2 6,1 6,1 5)),((0 3,1 3,1 1,0 1,0 3)),((4 9,3 9,3 10,4 10,4 9)),((9 10,10 10,10 9,9 9,9 8,8 8,8 10,9 10)))" 1025 }; 1026 1027 static std::string case_recursive_boxes_52[2] = 1028 { 1029 // Needs checking for isolated in handling of cc_ii clusters for intersection 1030 "MULTIPOLYGON(((0 0,0 1,1 1,1 0,0 0)),((5 1,2 1,2 3,1 3,1 4,0 4,0 8,1 8,1 9,2 9,2 8,5 8,5 5,6 5,6 7,7 7,7 9,9 9,9 10,10 10,10 7,9 7,9 6,10 6,10 5,9 5,9 1,8 1,8 2,7 2,7 3,6 3,6 4,5 4,5 2,6 2,6 0,5 0,5 1),(4 4,4 5,3 5,3 6,4 6,4 7,1 7,1 6,2 6,2 5,3 5,3 4,4 4),(7 5,7 4,8 4,8 6,7 6,7 5),(2 5,1 5,1 4,2 4,2 5)),((5 8,5 9,6 9,6 8,5 8)),((8 1,8 0,7 0,7 1,8 1)))", 1031 "MULTIPOLYGON(((1 1,2 1,2 0,1 0,1 1)),((9 10,10 10,10 9,9 9,9 10)),((3 9,3 10,4 10,4 9,3 9)),((1 10,2 10,2 9,0 9,0 10,1 10)),((5 4,4 4,4 3,3 3,3 2,1 2,1 1,0 1,0 3,2 3,2 4,1 4,1 5,5 5,5 7,6 7,6 6,7 6,7 8,9 8,9 7,8 7,8 6,9 6,9 4,8 4,8 3,10 3,10 2,8 2,8 1,7 1,7 0,6 0,6 2,7 2,7 3,6 3,6 4,5 4),(8 5,7 5,7 4,8 4,8 5)),((5 9,5 10,8 10,8 9,6 9,6 8,5 8,5 9)),((4 0,3 0,3 1,4 1,4 2,5 2,5 0,4 0)),((3 8,4 8,4 6,2 6,2 8,3 8)),((9 1,9 0,8 0,8 1,9 1)),((9 7,10 7,10 6,9 6,9 7)))" 1032 }; 1033 1034 static std::string case_recursive_boxes_53[2] = 1035 { 1036 // Needs checking for intersection patterns intersection_pattern_common_interior2 with ii 1037 "MULTIPOLYGON(((2 0,0 0,0 5,5 5,4 4,5 4,5 0,2 0),(2.5 4.5,3 4,3 5,2.5 4.5),(3 1,4 0,4 1,3 1),(3 3,4 2,4 3,3 3)))", 1038 "MULTIPOLYGON(((2 0,0 0,0 5,1 5,0.5 4.5,1 4,2 5,5 5,5 0,2 0),(2 3,2 4,1 4,2 3),(3 1,3 2,2 2,2 1,3 1),(1 3,0 2,1 2,1 3),(1 0,1 1,0.5 0.5,1 0),(5 3,4 3,4 2,5 3),(4 1,3.5 0.5,4 0,4 1)))" 1039 }; 1040 1041 static std::string case_recursive_boxes_54[2] = 1042 { 1043 // Needs including blocked from-ranks/operations in aggregations 1044 "MULTIPOLYGON(((2 2,2 3,1 3,1 5,2 4,2 5,5 5,5 4,4 3,5 3,5 2,4 2,4 1,5 0,2 0,2 1,1 1,1 2,2 2),(3 2,2.5 1.5,3 1,4 2,3 2),(3 2,3 3,2.5 2.5,3 2),(3 4,3 3,4 4,3 4)),((1 1,1 0,0 0,0 1,1 1)),((1 3,1 2,0 1,0 3,1 3)))", 1045 "MULTIPOLYGON(((2 2,3 3,2 3,2 5,5 5,5 3,4 3,3 2,5 2,5 1,4 1,3 0,1 0,1 1,0 1,0 2,2 2)),((0 4,0 5,1 5,1 4,0 3,0 4)))" 1046 }; 1047 1048 static std::string case_recursive_boxes_55[2] = 1049 { 1050 // Needs correct handling for union clusters with 3 open spaces 1051 "MULTIPOLYGON(((3 4,3 5,4 5,3 4)),((0 4,1 4,1 3,0 3,0 4)),((2 1,1.5 0.5,2 0,1 0,1 1,0 1,0 2,2 2,2 1)),((3 2,3 3,4 2,4 3,5 2,4 1,2 1,3 2)),((2 2,2 3,3 3,2 2)))", 1052 "MULTIPOLYGON(((2 1,2 0,1 0,2 1)),((2 1,2 2,3 2,3 1,2 1)),((1 3,1 4,2 5,2 2,1 2,0 1,0 4,1 3)),((5 4,4 3,3 3,4 4,3 4,3 5,5 5,5 4)),((1 0,0 0,1 1,1 0)),((0 4,0 5,1 5,0 4)))" 1053 }; 1054 1055 static std::string case_recursive_boxes_56[2] = 1056 { 1057 // Needs not discarding clustered self-turns if the cluster does not contain anything else 1058 "MULTIPOLYGON(((3 4,3 5,4 5,3 4)),((3 3,4 3,2 1,2 3,3 3)),((2 1,2 0,1 0,1 1,2 1)),((1 4,1 3,0 3,0 4,1 5,1 4)))", 1059 "MULTIPOLYGON(((2 4,2 5,3 4,2 4)),((1 5,1 4,0 4,0 5,1 5)),((1 2,0 2,0 3,1 2)),((2 2,1 2,2 3,2 2)),((2 2,2 1,1 1,1 2,1.5 1.5,2 2)))" 1060 }; 1061 1062 static std::string case_recursive_boxes_57[2] = 1063 { 1064 // Needs handling of 3 open spaces in union to form interior ring 1065 "MULTIPOLYGON(((2 0,0 0,0 1,0.5 0.5,1 1,1 2,2 1,4 1,4 4,5 3,5 0,2 0)),((2 5,2 4,1 4,1 5,2 5)),((1 2,0 2,0 3,1 2)),((1 2,1 3,2 3,2 2,1 2)),((0 1,0 2,1 1,0 1)),((4 3,3 3,3 4,4 3)),((3 4,3 5,5 5,5 4,3 4)))", 1066 "MULTIPOLYGON(((3 3,2 3,2 5,3 4,3 5,5 5,5 4,4 4,4 3,3 3)),((3 3,4 2,2 2,3 3)),((0 0,0 4,1 4,1 3,2 3,2 2,1 2,1 0,0 0)),((3 1,2 1,2 2,3 1)),((1 5,0 4,0 5,1 5)),((1 5,2 5,1 4,1 5)),((5 2,5 1,4 1,4 3,5 4,5 2)),((4 1,4 0,3 0,3 1,4 1)),((2 1,2 0,1 0,2 1)))", 1067 }; 1068 1069 static std::string case_recursive_boxes_58[2] = 1070 { 1071 // Needs correct handling for union clusters with 3 open spaces 1072 "MULTIPOLYGON(((0 0,1 1,2 1,1 0,0 0)),((1 1,1 2,2 2,1 1)),((3 1,4 2,4 1,3 1)),((3 2,3 3,4 3,3 2)))", 1073 "MULTIPOLYGON(((0 1,0 2,1 1,0 1)),((1 1,1 2,2 1,1 1)),((1 2,1 3,2 2,1 2)),((2 2,2 3,3 2,2 2)),((4 2,4 3,5 3,4 2)),((1 0,2 1,2 2,3 1,2 0,1 0)))", 1074 }; 1075 1076 static std::string case_recursive_boxes_59[2] = 1077 { 1078 // Needs correct handling for union clusters with 3 open spaces 1079 "MULTIPOLYGON(((2 3,2 2,3 2,3 1,2 1,1.5 0.5,2 0,0 0,0 1,1 1,1 4,2 4,3 5,5 5,5 4,3 4,3 3,2 3)),((3 2,3 3,4 3,4 2,3 2)),((2 0,3 1,5 1,5 0,2 0)),((0 3,0 5,1 5,1 4,0 3)),((0 3,1 3,0 2,0 3)))", 1080 "MULTIPOLYGON(((3 5,3 4,4 4,4 3,5 3,5 2,4 2,4 1,3.5 0.5,4 0,1 0,1 1,2 2,1 2,1 4,0 4,1 5,3 5),(2 3,2 4,1 3,2 3),(2 2,3 2,3 3,2 2)),((1 1,0 1,0 3,1 2,1 1)))", 1081 }; 1082 1083 static std::string case_recursive_boxes_60[2] = 1084 { 1085 // Needs checking left_count in union clusters 1086 "MULTIPOLYGON(((0 4,0 5,1 5,0 4)),((1 2,1 4,2 4,2 5,3 4,4 5,5 5,5 4,4 4,3.5 3.5,4 3,4 2,3 2,2 1,2 2,1 2)),((1 2,2 1,1 1,1 2)),((2 1,3 1,4 2,5 1,4 1,4 0,2 0,2 1)),((0 0,0 2,2 0,0 0)),((0 2,0 3,1 3,0 2)),((5 4,5 3,4 3,5 4)))", 1087 "MULTIPOLYGON(((2 3,1 2,1 4,0 4,0 5,3 5,3 3,2 3)),((1 2,3 2,3 3,4 4,5 4,5 3,4 3,3.5 2.5,4 2,4 0,0 0,0 1,1 1,1 2)),((4 2,5 3,5 2,4 2)))", 1088 }; 1089 1090 1091 static std::string case_recursive_boxes_61[2] = 1092 { 1093 // Needs pattern 4 for intersections 1094 "MULTIPOLYGON(((2 0,2 1,1 0,0 0,0 1,1 2,0 2,0 4,1 4,1 5,1.5 4.5,2 5,4 5,4.5 4.5,5 5,5 2,4.5 1.5,5 1,5 0,2 0),(3 1,3 2,2 2,2 1,3 1),(4 5,3.5 4.5,4 4,4 5)),((0 4,0 5,1 5,0 4)))", 1095 "MULTIPOLYGON(((3 5,5 5,5 0,2 0,2 1,1 1,1 0,0 0,0 2,1 2,1 3,0 3,0 5,3 5),(3 1,3 2,2 2,2 1,3 1)))", 1096 }; 1097 1098 static std::string case_recursive_boxes_62[2] = 1099 { 1100 // Needs discarding self-intersections within other geometry 1101 "MULTIPOLYGON(((2.5 3.5,3 4,3 3,4 3,4 2,5 2,5 0,1 0,1 1,2 1,3 2,2 2,2 3,1 3,2 4,2.5 3.5),(3 1,3 0,4 1,3 1)),((1 0,0 0,0 1,1 0)),((2 4,2 5,3 4,2 4)),((2 4,1 4,1 5,2 4)),((3 4,3 5,4 5,4 4,3 4)),((0 1,0 3,0.5 2.5,1 3,1 1,0 1)),((1 3,0 3,0 4,1 4,1 3)),((4 4,5 4,5 3,4 3,4 4)))", 1102 "MULTIPOLYGON(((2 0,1 0,1 1,2 2,2 1,4 1,3 0,2 0)),((2 2,1 2,1 1,0.5 0.5,1 0,0 0,0 5,4 5,4 4,3 3,4 3,4 2,2 2),(1 3,1 4,0 4,1 3)),((4 2,5 1,4 1,4 2)))", 1103 }; 1104 1105 static std::string case_recursive_boxes_63[2] = 1106 { 1107 // Derived from 62, needs not excluding startable points for checking rings for traversals 1108 "MULTIPOLYGON(((2 0,1 0,1 1,2 2,2 1,4 1,3 0,2 0)),((2 2,1 2,1 1,0.5 0.5,1 0,0 0,0 5,4 5,4 4,3 3,4 3,4 2,2 2),(1 3,1 4,0 4,1 3)),((4 2,5 1,4 1,4 2)))", 1109 "MULTIPOLYGON(((-1 -1, 6 -1, 6 6, -1 6, -1 -1), (0 0, 0 1, 0 3, 0 4, 1 4, 1 5, 2 4, 2 5, 3 4, 3 5, 4 5, 4 4, 5 4, 5 3, 4 3, 4 2, 5 2, 5 0, 3 0, 1 0, 0 0)),((2.5 3.5, 3 4, 2 4, 2.5 3.5)), ((3 3, 4 3, 4 4, 3 4, 3 3)), ((1 3, 2 4, 1 4, 1 3)), ((0.5 2.5, 1 3, 0 3, 0.5 2.5)), ((1 1, 2 1, 3 2, 2 2, 2 3, 1 3, 1 1)), ((3 0, 4 1, 3 1, 3 0)), ((1 0, 1 1, 0 1, 1 0)))", 1110 }; 1111 1112 static std::string case_recursive_boxes_64[2] = 1113 { 1114 // Needs considering remaining_distance in clusters 1115 "MULTIPOLYGON(((3 4,3 5,5 5,5 4,4 4,3 3,3.5 2.5,4 3,5 3,5 1,4 0,0 0,0 5,2 5,2 4,3 4),(2 2,3 2,3 3,2 2),(2 3,2 4,1 4,2 3),(2 0,2 1,1 1,2 0),(1 2,0 2,0.5 1.5,1 2)))", 1116 "MULTIPOLYGON(((3 5,5 5,5 0,0 0,1 1,0 1,0 3,1 3,1 4,1.5 3.5,2 4,2 5,3 5),(2 2,1 2,2 1,2 2),(2 2,2.5 1.5,3 2,2 2),(4 4,4.5 3.5,5 4,4 4),(4 1,3 1,4 0,4 1)),((2 5,0 3,0 5,2 5)))" 1117 }; 1118 1119 static std::string case_recursive_boxes_65[2] = 1120 { 1121 // Misses large hole in intersection 1122 "MULTIPOLYGON(((3 5,3.5 4.5,4 5,5 5,5 1,4 0,3 0,3 1,2 0,0 0,0 4,1 4,1 5,3 5),(2 4,2 3,3 4,2 4),(2 1,2 2,1.5 1.5,2 1),(3 3,4 2,4 3,3 3)))", 1123 "MULTIPOLYGON(((3 5,4 5,4 4,5 5,5 2,4 2,3.5 1.5,5 0,1 0,1 1,0 1,0 5,3 5),(2 2,3 2,4 3,1 3,1 2,2 2)),((1 0,0 0,0 1,1 0)),((4 1,4 2,5 1,4 1)))" 1124 }; 1125 1126 static std::string case_recursive_boxes_66[2] = 1127 { 1128 // Needs self-turns startable, at least not determined using count left/right for self-turns 1129 "MULTIPOLYGON(((1 0,0 0,1 1,0 1,0 4,1 4,1 5,3 5,3 4,4 5,5 5,5 0,1 0),(3 3,4 2,4 3,3 3),(3 1,4 1,4 2,3 2,3 1),(3 3,3 4,2 3,3 3),(3 4,3.5 3.5,4 4,3 4)))", 1130 "MULTIPOLYGON(((2 0,0 0,0 1,1 1,1 2,0 2,0 5,1 5,2 4,2 5,5 5,5 0,2 0),(3 1,3 2,2.5 1.5,3 1),(2 3,1 2,2 1,2 2,3 2,4 3,2 3),(0 3,0.5 2.5,1 3,1 4,0 3)))" 1131 }; 1132 1133 static std::string case_recursive_boxes_67[2] = 1134 { 1135 // Needs to avoid including any untraveled ring with blocked turns 1136 "MULTIPOLYGON(((2 2,3 3,3 2,2 2)),((2 2,1 2,1 3,2 3,2 2)),((1 1,2 1,2 0,0 0,0 1,1 1)),((2 4,1 4,0.5 3.5,1 3,0 3,0 5,1 5,2 4)),((4 2,4 3,5 2,4 2)),((4 2,4 1,3 1,4 2)),((3 3,3 4,4 4,4 3,3 3)),((4 4,4 5,5 5,5 4,4 4)))", 1137 "MULTIPOLYGON(((3 4,4 5,4 4,3 4)),((3 1,3 0,2 0,3 1)),((3 1,1 1,1 2,2 3,3 3,3 2,2 2,3 1)),((3 1,3 2,5 2,5 1,3 1)),((2 3,0 3,0 4,1 4,2 3)),((1 3,1 2,0 2,1 3)),((1 4,1 5,2 5,1 4)))" 1138 }; 1139 1140 static std::string case_recursive_boxes_68[2] = 1141 { 1142 // Needs checking blocked turns in colocated turns 1143 "MULTIPOLYGON(((3 3,3 4,4 4,4 5,5 5,4.5 4.5,5 4,5 3,4.5 2.5,5 2,2 2,2 4,3 3)),((2 5,3 5,3 4,2 4,1 3,1 2,0 2,0 4,1 4,1 5,2 5)),((2 2,4 0,1 0,2 1,1 1,1 2,2 2)),((1 0,0 0,0 1,1 1,1 0)),((4 0,5 1,5 0,4 0)),((5 1,4 1,4 2,5 1)))", 1144 "MULTIPOLYGON(((2 0,2 1,1 1,2 2,3 2,3 1,4 2,5 2,5 0,2 0)),((2 0,1 0,1 1,2 0)),((2 2,2 3,3 4,3 3,2 2)),((3 2,3 3,4 4,5 4,5 3,4 2,3 2)),((3 4,3 5,4 4,3 4)),((2 4,2 3,1 2,1 3,0 3,0 5,1 5,1 4,2 4)),((1 2,1 1,0 1,0 2,1 2)),((4 4,4 5,5 5,4 4)))" 1145 }; 1146 1147 static std::string case_recursive_boxes_69[2] = 1148 { 1149 // Needs checking left_count instead of is_closed for decision to block untraversed rings 1150 "MULTIPOLYGON(((3 4,3 5,4 5,3 4)),((3 4,3 2,2 2,3 1,1 1,1 2,0 2,1 3,0 3,1 4,3 4)),((3 1,4 1,4 0,3 0,3 1)),((1 1,2 0,0 0,0 1,1 1)))", 1151 "MULTIPOLYGON(((2 4,1 4,1 3,0 3,0 5,2 5,3 4,2 4)),((3 4,3 5,4 5,4 4,3 4)),((2 1,2 0,1 0,2 1)),((2 1,1 1,1 2,2 2,2 1)),((5 1,5 0,3 0,4 1,5 1)),((4 1,3 1,3 2,4 3,5 2,4 2,4 1)),((1 3,2 3,1 2,1 3)))" 1152 }; 1153 1154 static std::string case_recursive_boxes_70[2] = 1155 { 1156 // Needs checking left_count instead of is_closed for decision to block untraversed rings 1157 "MULTIPOLYGON(((2 0,0 0,0 4,1 3,3 3,3 5,5 5,5 3,4.5 2.5,5 2,5 0,2 0),(0 1,0.5 0.5,1 1,0 1),(5 2,4 2,4.5 1.5,5 2),(4 2,3 2,3 1,4 2)),((3 4,2 3,2 4,3 4)),((0 4,0 5,1 5,1.5 4.5,2 5,2 4,0 4)))", 1158 "MULTIPOLYGON(((2 0,0 0,0 5,5 5,5 2,4.5 1.5,5 1,5 0,2 0),(2 1,3 0,3 1,2 1),(4 4,3 3,4 3,4 4),(1 1,1 2,0 2,1 1),(4 3,4.5 2.5,5 3,4 3)))" 1159 }; 1160 1161 static std::string case_recursive_boxes_71[2] = 1162 { 1163 // Needs check for self-cluster within other geometry, in intersections 1164 "MULTIPOLYGON(((4 0,4 1,5 1,5 0,4 0)),((4 3,4 4,5 4,4 3)),((3 3,4 2,3 2,3 3)),((3 3,2 3,3 4,3 3)),((3 2,3 0,1 0,1 3,0 3,0 4,1 4,3 2),(3 2,2 2,2 1,3 2)),((1 4,1 5,2 5,2 4,1 4)))", 1165 "MULTIPOLYGON(((3 0,3 1,4 0,3 0)),((2 2,0 2,0 3,1 3,2 2)),((2 2,2 3,3 3,2 2)),((2 4,0 4,1 5,3 5,3 4,2 4)),((3 3,3 4,4 5,5 4,4 4,4 3,3 3)),((4 3,5 3,4 2,4 3)))" 1166 }; 1167 1168 static std::string case_recursive_boxes_72[2] = 1169 { 1170 // Needs selection of ranked point in union (to finish the ring) 1171 "MULTIPOLYGON(((3 1,4 1,4 0,3 0,3 1)),((1 0,1 1,2 1,2 0,1 0)),((3 3,3 5,5 5,5 2,4 2,4 3,3 3)),((3 3,2 2,2 3,3 3)),((1 3,0 2,0 3,1 3)),((1 4,2 4,2 3,1 2,1 4)),((1 4,1 5,2 5,1 4)),((2 5,3 5,2 4,2 5)),((1 5,0 4,0 5,1 5)))", 1172 "MULTIPOLYGON(((4 0,4 1,5 0,4 0)),((4 4,4 5,5 5,5 4,4 4)),((2 4,2 3,1 3,1 4,2 4)),((2 4,2 5,3 5,2 4)),((2 2,2 3,3 3,2 2)),((2 2,3 2,3 1,2 1,2 2)),((3 3,4 2,3 2,3 3)),((3 1,3 0,2 0,3 1)),((1 3,2 2,1 1,1 3)),((1 2,0 2,0 3,1 2)),((1 4,0 4,0 5,1 5,1 4)),((4 2,4 3,5 2,4 2)))" 1173 }; 1174 1175 static std::string case_recursive_boxes_73[2] = 1176 { 1177 // Needs handling connection points identical for clustered/non-clustered turns 1178 "MULTIPOLYGON(((3 5,5 5,5 4,4.5 3.5,5 3,5 2,3 2,3 1,4 0,0 0,0 5,1 4,2 4,2 5,3 5),(2 3,2 2,3 3,2 3),(1 2,0 2,1 1,1 2)),((1 4,1 5,2 5,1 4)),((4 0,4 1,5 1,5 0,4 0)))", 1179 "MULTIPOLYGON(((2 0,0 0,0 5,1 5,2 4,2 5,4 5,4.5 4.5,5 5,5 4,4 4,4 3,5 3,5 0,2 0),(0 2,0.5 1.5,1 2,0 2),(1 4,2 3,2 4,1 4)))" 1180 }; 1181 1182 static std::string case_recursive_boxes_74[2] = 1183 { 1184 // Needs another method to find isolated regions (previous attempted used parents, that is dropped now) 1185 "MULTIPOLYGON(((3 5,5 5,5 0,0 0,0 5,3 5),(2 3,1.5 2.5,2 2,3 3,2 3),(3 3,4 2,4 3,3 3),(2 0,3 1,2 1,2 0)))", 1186 "MULTIPOLYGON(((2 0,0 0,0 5,1 5,2 4,2 5,5 5,5 0,2 0),(2 1,2.5 0.5,3 1,2 1),(2 3,3 3,3 4,2 4,2 3),(3 1,4 1,5 2,3 2,3 1)))" 1187 }; 1188 1189 static std::string case_recursive_boxes_75[2] = 1190 { 1191 // Needs intersection pattern 6 (skip all isolated ranks in between) 1192 "MULTIPOLYGON(((3 1,2 1,1 0,0 0,0 5,5 5,5 3,4 2,5 2,5 0,3 0,3 1),(2 3,1 3,2 2,2 3),(3 4,3.5 3.5,4 4,3 4),(3 3,3 2,4 2,4 3,3 3)))", 1193 "MULTIPOLYGON(((3 5,4 5,4.5 4.5,5 5,5 0,4 0,4 1,2 1,2 2,1 2,1 3,0 2,0 5,1 5,0.5 4.5,1 4,2 5,3 5),(3 4,3 3,4 4,3 4),(3 3,4 2,4 3,3 3)),((2 1,2 0,1 0,1 1,2 1)),((0 2,1 2,0.5 1.5,1 1,0 1,0 2)),((1 0,0 0,0 1,1 0)))" 1194 }; 1195 1196 static std::string case_recursive_boxes_76[2] = 1197 { 1198 // Needs considering ix/ix turns (opposite in both directions) as the same region 1199 "MULTIPOLYGON(((3 5,3 4,4 5,4 4,5 4,5 0,0 0,0 4,1 4,1 5,3 5),(3 1,2 1,2.5 0.5,3 1),(1 2,0 2,0.5 1.5,1 2)))", 1200 "MULTIPOLYGON(((2 0,0 0,0 3,1 4,0 4,0 5,2 5,2 4,3 4,4 5,5 5,5 0,2 0),(3 1,4 0,4 1,3 1),(3 2,2 1,3 1,3 2),(3 3,3 4,2 3,3 3),(2 1,1 1,1.5 0.5,2 1),(4 3,4 4,3 4,4 3)))" 1201 }; 1202 1203 static std::string case_recursive_boxes_77[2] = 1204 { 1205 // Needs discarding self i/u turn traveling to itself (for intersection only) 1206 "MULTIPOLYGON(((1 2,2 3,2 2,1 1,1 2)),((1 4,1 5,2 5,2 4,1 4)),((1 4,0 3,0 4,1 4)),((4 2,4 1,3 1,3 3,4 2)),((3 1,3 0,1 0,2 1,2.5 0.5,3 1)),((3 3,3 5,4 5,4 3,3 3)))", 1207 "MULTIPOLYGON(((3 4,3 5,4 5,4 4,3 4)),((3 1,3 0,2 0,3 1)),((3 1,2 1,2 2,3 2,3 1)),((2 3,2 4,3 3,2 3)),((2 1,1 0,0 0,1 1,2 1)),((1 4,2 3,2 2,0 2,0 4,1 4),(2 3,1 3,1.5 2.5,2 3)),((1 4,1 5,2 5,2 4,1 4)),((4 1,5 0,4 0,4 1)),((4 1,4 2,5 1,4 1)),((4 2,5 3,5 2,4 2)))" 1208 }; 1209 1210 static std::string case_recursive_boxes_78[2] = 1211 { 1212 // Needs checking intersection/right_count in overlay, as was already done for union 1213 "MULTIPOLYGON(((3 2,1 2,1 4,3 2)),((3 2,3 4,4 4,3.5 3.5,4.5 2.5,5 3,5 1,4 1,3 0,3 2),(4 2,3.5 1.5,4 1,4 2)),((1 2,1 1,0 0,0 2,1 2)),((0 4,1 3,0 3,0 4)),((0 4,1 5,1.5 4.5,2 5,3 5,3 4,0 4)),((1 1,2 1,1 0,1 1)),((4 1,5 0,4 0,4 1)),((4 3,4 5,5 4,5 3,4 3)))", 1214 "MULTIPOLYGON(((2 4,1 4,1 5,3 5,2 4)),((2 4,4 4,4 3,5 3,5 2,4 1,4 2,3 2,3 3,2 2,2 4)),((2 2,2 1,0 1,0 4,1 3,1 4,2 3,1 2,2 2)),((1 4,0 4,0 5,1 4)),((0 1,1 0,0 0,0 1)),((4 1,3 1,3 2,4 1)))" 1215 }; 1216 1217 static std::string case_recursive_boxes_79[2] = 1218 { 1219 // Found by bug in discard_self_turns_which_loop, it needs only checking intersection and not union 1220 "MULTIPOLYGON(((2 3,2 2,1 2,1 4,4 4,4 3,2 3)),((2 0,0 0,0 2,1 2,1.5 1.5,2 2,2 1,1 1,2 0)),((2 0,2 1,3 2,4 2,3.5 1.5,4 1,4 0,2 0),(2 1,2.5 0.5,3 1,2 1)))", 1221 "MULTIPOLYGON(((2 0,1 0,1 1,0 1,0 3,1 4,4 4,4 0,2 0),(2 2,1 2,1 1,2 2),(4 3,3 3,3 2,4 3)))" 1222 }; 1223 1224 static std::string case_recursive_boxes_80[2] = 1225 { 1226 // Creates very small interior ring (~0) for union. This is a robustness 1227 // problem, it should not be generated. The intersection point is a tiny 1228 // distance away from real IP, and therefore it generates a correct 1229 // interior ring, and is considered as valid. But if you combine this 1230 // resulting union later with other polygons, with another rescaling model, 1231 // it most probably will be invalid. 1232 // These cases are found with recursive_polygons and size=4. 1233 // For size=5 the scaling is such that it does not occur (so often) 1234 // It needs removing the rescaling. 1235 "MULTIPOLYGON(((3.5 2.5,4 3,4 2,3 2,3 3,3.5 2.5)))", 1236 "MULTIPOLYGON(((1 1,1 2,2 1,1 1)),((3 2,3 3,4 3,3 2)))" 1237 }; 1238 1239 static std::string case_recursive_boxes_81[2] = 1240 { 1241 "MULTIPOLYGON(((3 4,2 4,2 5,3 4)),((3 3,2 3,2 4,3 3)),((3 3,3 4,4 5,5 4,5 3,3 3),(4 4,3.5 3.5,4 3,4 4)),((2 1,2 0,1 0,1 1,0 1,1 2,3 2,4 3,4 1,2 1)))", 1242 "MULTIPOLYGON(((2 4,2 2,1 2,0 1,0 3,1 3,1 4,2 4)),((2 4,2 5,3 4,2 4)),((3 4,5 4,5 3,3 3,3 4)),((1 4,0 4,0 5,1 5,1 4)),((2 1,2 0,0 0,0 1,2 1)),((4 2,5 2,4 1,3 1,4 2)),((4 1,5 1,4 0,4 1)))" 1243 }; 1244 1245 static std::string case_recursive_boxes_82[2] = 1246 { 1247 // Contains two outgoing arcs on same ring causing current aggregation implementation to fail. 1248 // Fixed by greatly simplifying the code, skipping aggregations and using sbs directly (which is now possible, now that isolation-information is much better) 1249 "MULTIPOLYGON(((4 0,5 1,5 0,4 0)),((3 3,3 1,4 1,3 0,0 0,0 5,1 5,1 4,1.5 3.5,2 4,2 3,3 3),(2 2,2 1,3 2,2 2)),((2 4,3 5,4 5,3.5 4.5,5 3,3 3,3 4,2 4)),((4 4,4 5,5 5,4.5 4.5,5 4,4 4)))", 1250 "MULTIPOLYGON(((2 4,2 5,4 5,4 4,2 4)),((2 4,2 3,5 3,5 2,4 2,4 1,1 1,1 2,0 2,0 5,1 5,1 4,2 4),(2 2,1 2,1.5 1.5,2 2),(3 2,3.5 1.5,4 2,3 2)),((4 4,5 5,5 4,4 4)))" 1251 }; 1252 1253 static std::string case_recursive_boxes_83[2] = 1254 { 1255 // Needs to select on operation in cluster 1256 "MULTIPOLYGON(((2 1,2 0,1 0,1 4,2 4,2 5,3 5,4 4,4 3,5 3,4 2,5 2,5 0,4 0,4 1,3 0,3 1,2 1),(2 3,1 3,2 2,2 3),(3 2,3 3,2 2,3 2)),((0 2,1 1,0 0,0 2)),((0 2,0 3,1 3,0 2)),((4 4,4 5,5 4,4 4)))", 1257 "MULTIPOLYGON(((2 0,1 0,1 2,2 2,2 5,3 4,3 5,4 5,4 4,5 5,5 3,4 3,4 1,5 1,5 0,2 0),(2 1,3 2,2 2,2 1)),((0 5,1 5,1 4,0 4,0 5)),((1 1,0 1,0 2,1 1)),((1 2,0 2,1 3,1 2)))" 1258 }; 1259 1260 static std::string case_recursive_boxes_84[2] = 1261 { 1262 // Need to set some ii-turns non-startable 1263 "MULTIPOLYGON(((2 4,1 4,1 5,3 5,2 4)),((3 5,4 5,4 4,3 4,3 5)),((3 3,4 3,4 4,5 4,4.5 3.5,5 3,5 2,4 1,3 1,3 2,2 2,2 3,3 3),(4 2,3.5 1.5,4 1,4 2)),((0 3,0 4,1 4,1 3,0 3)))", 1264 "MULTIPOLYGON(((4 4,4 5,5 5,5 4,4 4)),((0 5,1 5,1 4,0 4,0 5)),((2 0,1 0,1 1,2 1,2 2,3 2,3 0,2 0)),((2 4,2 3,1 3,2 4)),((2 4,2 5,3 5,2 4)),((2 3,2 2,1 2,2 3)),((1 3,1 1,0 1,0 3,1 3)),((5 1,5 0,4 0,4 1,5 1)))" 1265 }; 1266 1267 static std::string case_recursive_boxes_85[2] = 1268 { 1269 // Contains rescaling problem 1270 "MULTIPOLYGON(((5 2,5 3,6 3,6 2,5 2)),((6 5,6 6,7 6,7 5,6 5)),((3 6,1 6,2 7,3 7,3 6)),((3 6,3 5,2 5,2 6,2.5 5.5,3 6)))", 1271 "MULTIPOLYGON(((2 5,2 6,3 6,2 5)),((6 1,6 2,7 2,6 1)),((5 4,5 5,6 4,5 4)),((0 6,0 7,1 7,0 6)),((3 3,3 2,2 2,3 3)),((3 3,3 4,4 5,4 4,3 3)),((4 4,5 3,4 3,4 4)))" 1272 }; 1273 1274 static std::string case_recursive_boxes_86[2] = 1275 { 1276 // Positive ring and negative ring have same area. For difference, this 1277 // needs to be handled correctly in assign_parents, 1278 // skipping the optimization for union 1279 "MULTIPOLYGON(((3 4,4 4,4 3,2 3,3 4)))", 1280 "MULTIPOLYGON(((4 1,3 1,3 2,4 1)),((4 1,5 1,5 0,4 0,4 1)))" 1281 }; 1282 1283 static std::string case_recursive_boxes_87[2] = 1284 { 1285 // Needs to handle ii-turns for difference like done for intersection 1286 "MULTIPOLYGON(((5 2,5 3,6 3,5 2)),((3 4,3 3,2 3,3 4)),((3 4,2 4,3 5,3 4)),((2 4,2 3,1 3,2 4)))", 1287 "MULTIPOLYGON(((2 0,3 1,3 0,2 0)),((6 3,6 4,7 4,7 3,6 3)),((3 9,3 10,4 9,3 9)),((8 7,8 8,9 8,8 7)))" 1288 }; 1289 1290 static std::string case_recursive_boxes_88[2] = 1291 { 1292 "MULTIPOLYGON(((1 4,1 5,2 5,2 4,1 4)),((0 2,0 3,1 3,0 2)),((3 5,4 5,4 4,3 4,3 5)),((2 3,4 3,4 2,3 1,2 1,2 3),(3 3,2.5 2.5,3 2,3 3)),((4 1,3 0,3 1,4 1)),((4 2,5 2,5 0,4 0,4 2)))", 1293 "MULTIPOLYGON(((4 0,4 1,5 1,5 0,4 0)),((3 4,3 3,1 3,1 5,3 5,2.5 4.5,3 4)),((3 4,3 5,4 5,4 4,3 4)),((1 1,2 0,1 0,1 1)),((1 1,1 2,2 2,2 1,1 1)),((1 2,0 2,0 3,1 3,1 2)),((4 4,5 4,5 2,4 2,4 4)))" 1294 }; 1295 1296 static std::string pie_21_7_21_0_3[2] = 1297 { 1298 "MULTIPOLYGON(((2500 2500,2500 3875,2855 3828,3187 3690,3472 3472,3690 3187,3828 2855,3875 2500,3828 2144,3690 1812,3472 1527,3187 1309,2855 1171,2499 1125,2144 1171,1812 1309,1527 1527,1309 1812,1171 2144,1125 2499,1171 2855,1309 3187,2500 2500)))", 1299 "MULTIPOLYGON(((2500 2500,1704 3295,1937 3474,2208 3586,2499 3625,2791 3586,3062 3474,3295 3295,2500 2500)),((2500 2500,3586 2791,3625 2500,3586 2208,2500 2500)))" 1300 }; 1301 1302 static std::string pie_23_19_5_0_2[2] = 1303 { 1304 "MULTIPOLYGON(((2500 2500,2500 3875,2855 3828,3187 3690,3472 3472,3690 3187,3828 2855,3875 2500,3828 2144,3690 1812,3472 1527,3187 1309,2855 1171,2499 1125,2144 1171,1812 1309,1527 1527,1309 1812,1171 2144,1125 2499,1171 2855,1309 3187,1527 3472,1812 3690,2500 2500)))", 1305 "MULTIPOLYGON(((2500 2500,3586 2791,3625 2500,3586 2208,3474 1937,3295 1704,3062 1525,2791 1413,2499 1375,2208 1413,1937 1525,1704 1704,1525 1937,1413 2208,1375 2500,1413 2791,1525 3062,1704 3295,1937 3474,2208 3586,2500 2500)),((2500 2500,2791 3586,3062 3474,2500 2500)))" 1306 }; 1307 1308 static std::string pie_7_14_5_0_7[2] = 1309 { 1310 "MULTIPOLYGON(((2500 2500,2500 3875,2855 3828,3187 3690,3472 3472,3690 3187,3828 2855,3875 2500,2500 2500)))", 1311 "MULTIPOLYGON(((2500 2500,3586 2791,3625 2500,3586 2208,3474 1937,3295 1704,3062 1525,2791 1413,2499 1375,2208 1413,1937 1525,1704 1704,1525 1937,1413 2208,1375 2500,2500 2500)),((2500 2500,1525 3062,1704 3295,1937 3474,2208 3586,2499 3625,2791 3586,3062 3474,2500 2500)))" 1312 }; 1313 1314 static std::string pie_16_16_9_0_2[2] = 1315 { 1316 "MULTIPOLYGON(((2500 2500,2500 3875,2855 3828,3187 3690,3472 3472,3690 3187,3828 2855,3875 2500,3828 2144,3690 1812,3472 1527,3187 1309,2855 1171,2499 1125,2144 1171,1812 1309,1527 1527,2500 2500)))", 1317 "MULTIPOLYGON(((2500 2500,3295 1704,3062 1525,2791 1413,2499 1375,2208 1413,1937 1525,1704 1704,1525 1937,1413 2208,1375 2500,1413 2791,1525 3062,1704 3295,1937 3474,2208 3586,2499 3625,2500 2500)),((2500 2500,3062 3474,3295 3295,2500 2500)))" 1318 }; 1319 1320 static std::string pie_7_2_1_0_15[2] = 1321 { 1322 "MULTIPOLYGON(((2500 2500,2500 3875,2855 3828,3187 3690,3472 3472,3690 3187,3828 2855,3875 2500,2500 2500)))", 1323 "MULTIPOLYGON(((2500 2500,2791 3586,3062 3474,2500 2500)),((2500 2500,3474 3062,3586 2791,3625 2500,3586 2208,3474 1937,3295 1704,3062 1525,2791 1413,2499 1375,2208 1413,1937 1525,1704 1704,1525 1937,1413 2208,1375 2500,2500 2500)))" 1324 }; 1325 1326 static std::string case_precision_m1[2] = 1327 { 1328 "MULTIPOLYGON(((0 0,0 4,2 4,2 3,4 3,4 0,0 0)))", 1329 "MULTIPOLYGON(((-1 -1,-1 8,2 8,2 7,2 3,4.0000005 2.9999995,4 7,4 8,8 8,8 -1,-1 -1)))" 1330 }; 1331 1332 static std::string case_precision_m2[2] = 1333 { 1334 "MULTIPOLYGON(((0 0,0 4,2 4,2 3,4 3,4 0,0 0)),((3 6,3 7.5,4.5 7.5,4.5 6,3 6)))", 1335 "MULTIPOLYGON(((-1 -1,-1 8,8 8,8 -1,-1 -1),(2 7,2 3,4.0000005 2.9999995,4 7,2 7)))" 1336 }; 1337 1338 // Case, not literally on this list but derived, to mix polygon/multipolygon in call to difference 1339 static std::string ggl_list_20111025_vd[4] = 1340 { 1341 "POLYGON((0 0,0 4,4 0,0 0))", 1342 "POLYGON((10 0,10 5,15 0,10 0))", 1343 "MULTIPOLYGON(((0 0,0 4,4 0,0 0)))", 1344 "MULTIPOLYGON(((10 0,10 5,15 0,10 0)))" 1345 }; 1346 1347 // Same, mail with other case with text "Say the MP is the 2 squares below and P is the blue-ish rectangle." 1348 static std::string ggl_list_20111025_vd_2[2] = 1349 { 1350 "POLYGON((5 0,5 4,8 4,8 0,5 0))", 1351 "MULTIPOLYGON(((0 0,0 2,2 2,2 0,0 0)),((4 0,4 2,6 2,6 0,4 0)))" 1352 }; 1353 1354 // Mail of h2 indicating that reversed order (in second polygon) has ix/ix problems 1355 static std::string ggl_list_20120915_h2[3] = 1356 { 1357 "MULTIPOLYGON(((-2 5, -1 5, 0 5, 2 5, 2 -2, 1 -2, 1 -1, 0 -1,0 0, -1 0, -2 0, -2 5)))", 1358 "MULTIPOLYGON(((0 0, 1 0, 1 -1, 0 -1, 0 0)), ((-1 5, 0 5, 0 0, -1 0, -1 5)))", 1359 "MULTIPOLYGON(((-1 5, 0 5, 0 0, -1 0, -1 5)), ((0 0, 1 0, 1 -1, 0 -1, 0 0)))" 1360 }; 1361 1362 // Mail of volker, about another problem, but this specific example is causing two-point inner rings polygons which should be discarded 1363 // (condition of num_points in detail/overlay/convert_ring.hpp) 1364 static std::string ggl_list_20120221_volker[2] = 1365 { 1366 "MULTIPOLYGON(((1032 2130,1032 1764,2052 2712,1032 2130)),((3234 2580,2558 2690,3234 2532,3234 2580)),((2558 2690,2136 2790,2052 2712,2136 2760,2558 2690)))", 1367 "MULTIPOLYGON(((3232 2532.469945355191,2136 2790,1032 1764,1032 1458,1032 1212,2136 2328,3232 2220.196721311475,3232 1056,1031 1056,1031 2856,3232 2856,3232 2532.469945355191),(3232 2412.426229508197,2136 2646,3232 2412.426229508197)))" 1368 }; 1369 1370 static std::string ggl_list_20140212_sybren[2] = 1371 { 1372 "MULTIPOLYGON(((0.494062 0.659354,0.471383 0.64654,0.446639 0.616561,0.47291 0.61171,0.495396 0.625263,0.494964 0.679709,0.494062 0.659354)))", 1373 "MULTIPOLYGON(((0.4951091661995328 0.6614133543986973,0.495396 0.625263,0.50092 0.6492750000000001,0.494964 0.679709,0.477258 0.698703,0.4951091661995328 0.6614133543986973)),((0.452167 0.706562,0.433379 0.696888,0.442673 0.65792,0.464729 0.671387,0.452167 0.706562)))" 1374 }; 1375 1376 static std::string mail_2019_01_21_johan[4] = 1377 { 1378 // Contains a, b, both a and b (should have been merged), c (clip) 1379 "MULTIPOLYGON(((1.2036811113357544 0.7535473108291626,1.1699721813201904 0.7535473108291626,1.1699721813201904 0.7663263082504272,1.2033243179321289 0.7672826647758484,1.2036811113357544 0.7535473108291626)))", 1380 "MULTIPOLYGON(((1.2036811113357544 0.7535473108291626,1.2038091421127319 0.7486215233802795,1.1713759899139404 0.7495520114898682,1.1713759899139404 0.7535472512245178,1.2036811113357544 0.7535473108291626)))", 1381 "MULTIPOLYGON(((1.2036811113357544 0.7535473108291626,1.1699721813201904 0.7535473108291626,1.1699721813201904 0.7663263082504272,1.2033243179321289 0.7672826647758484,1.2036811113357544 0.7535473108291626))," 1382 "((1.2036811113357544 0.7535473108291626,1.2038091421127319 0.7486215233802795,1.1713759899139404 0.7495520114898682,1.1713759899139404 0.7535472512245178,1.2036811113357544 0.7535473108291626)))", 1383 "MULTIPOLYGON(((0 0,2 0,2 2,0 2,0 0)))" 1384 }; 1385 1386 static std::string ticket_9081[2] = 1387 { 1388 "MULTIPOLYGON(((0.5489109414010371 0.5774835110050927,0.4099611282054447 0.4644351568071598,0.4294011278595494 0.4843224236729239,0.4205359995313906 0.5115225580860201,0.4441572412013468 0.5184999851878852,0.5489109414010371 0.5774835110050927)),((0.562085028126843 0.5882018328808966,0.5644349663154944 0.591180348361206,0.568218114394707 0.5970364466647042,0.5838690879677763 0.6212632646137447,0.5873787029417971 0.6412877041753083,0.468699602592386 0.5866280231830688,0.4171010902425981 0.5220616039851281,0.4059124592966251 0.5563907478354578,0.3909547828925878 0.6022841397455458,0.520859401226844 0.9508041627246925,0.8595233008819849 0.8301950132755517,0.562085028126843 0.5882018328808966)))", 1389 "MULTIPOLYGON(((0.2099392122251989 0.492066865490789,0.1124301889095737 0.5124668111209448,0.3306914939102383 0.6126684490171914,0.2099392122251989 0.492066865490789)),((0.5885369465145437 0.6478961722242873,0.5342320718598281 0.6686303269145104,0.5619623880692838 0.7033299168703926,0.5945761233023867 0.6823532655194001,0.5885369465145437 0.6478961722242873)),((0.5570738195183501 0.6001870087680015,0.5429714753344335 0.6231021858940831,0.5880357506342242 0.6450365518134291,0.5838690879677763 0.6212632646137447,0.568218114394707 0.5970364466647042,0.5570738195183501 0.6001870087680015)),((0.5498478321815098 0.5029279381860542,0.608691671498764 0.5163121433149205,0.5636607291345047 0.5894838094559455,0.8595233008819849 0.8301950132755517,0.8285440738598029 0.8412277162756114,0.9591357158116398 0.9011810663167211,0.8572649311807611 0.3566393017365032,0.5965816668471951 0.4111770689940296,0.5498478321815098 0.5029279381860542)),((0.3984249865018206 0.4526335964808558,0.3621206996557855 0.4602288471829723,0.4183516736935784 0.4730187483833363,0.4099611282054451 0.4644351568071601,0.3984249865018206 0.4526335964808558)))" 1390 }; 1391 1392 // Integer, ccw, open, reported by Volker 1393 static std::string ticket_9942[2] = 1394 { 1395 "MULTIPOLYGON(((2058 1761,1996 1700,1660 1370,1324 1040,982 1148,881 981,2644 981,2338 1982)),((1996 1760,2338 2078,2674 1010,3010 1160,3254 2085,3352 2522,3427 2562,3688 2930,3688 2924,3688 2702,3439 2568,3352 2444,3218 1926,3010 998,2959 981,3773 981,3773 3702,732 3702,732 981,770 981,982 1310,1324 1148,1660 1442,1697 1472,1660 1436,1698 1473,1697 1472)))", 1396 "MULTIPOLYGON(((646 932,646 788,870 1136)),((3032 1096,3010 1040,2981 988,3010 998)),((3688 2702,3352 2522,3032 1096,3352 1916,3688 2018)),((2981 988,2674 884,2338 1982,1996 1712,1660 1442,1324 1148,982 1310,870 1136,982 1238,1324 1136,1660 1304,1996 1460,2338 1610,2674 434)))", 1397 }; 1398 1399 // Simplified version showing the generated 'spike' which actually has an area because of the necessary rounding 1400 static std::string ticket_9942a[2] = 1401 { 1402 "MULTIPOLYGON(((2058 1761,1996 1700,1660 1370,1324 1040,2644 981,2338 1982)))", 1403 "MULTIPOLYGON(((2674 884,2338 1982,1996 1712,1660 1442,1324 1148,1324 1136,1660 1304,1996 1460,2338 1610,2674 434)))", 1404 }; 1405 1406 // Integer, ccw, open 1407 static std::string ticket_10661[3] = 1408 { 1409 /* A */ "MULTIPOLYGON(((1701 985,3501 985,3501 2785,1701 2785,1701 985)))", 1410 /* B */ "MULTIPOLYGON(((1698 1860,1698 1122,2598 1392,3492 1842,3492 32706,2598 2340,1698 1860)))", 1411 /* C=A-B, */ 1412 /* D */ "MULTIPOLYGON(((1698 2772,1698 1860,2598 2340,3492 2412,3492 32743,1698 2772)))" 1413 // Reported problem was: validity of difference C-D 1414 }; 1415 1416 // Integer, ccw, open 1417 static std::string ticket_10803[2] = 1418 { 1419 "MULTIPOLYGON(((3174 1374,3174 2886,1374 2886,1374 2139,3174 1374)))", 1420 "MULTIPOLYGON(((1374 1092,1734 1092,3174 2526,3174 2886,1374 2886,1374 1092)))" 1421 }; 1422 1423 // Intersection was reported as invalid 1424 static std::string ticket_11018[2] = 1425 { 1426 "MULTIPOLYGON(((66.32861177 -32.36106001,66.32805654 -32.36294657,66.32805697 -32.36294666,66.2558847 -32.60687137,66.18259719 -32.85172659,66.18259756 -32.85172667,66.10923256 -33.09561483,66.10923294 -33.09561491,66.03574675 -33.34044236,65.96214887 -33.58529255,65.96214918 -33.58529261,65.94391227 -33.64484979,65.839119 -33.032507,66.32861177 -32.36106001)),((67.77272059 -31.62519092,67.77272315 -31.62518165,67.77272398 -31.62517863,67.84057793 -31.37975346,67.90737994 -31.13429944,67.92189506 -31.0817063,68.151987 -31.013051,69.236142 -30.678138,70.320296 -31.013051,71.411955 -31.338781,72.016906 -32.187175,72.633163 -33.032507,72.464921 -34.015608,72.292755 -34.998316,71.385165 -35.656005,70.46265 -36.306671,69.236142 -36.312964,68.009631 -36.306671,67.087119 -35.656005,66.69381557 -35.37099587,66.7156576 -35.29873723,66.78843343 -35.05443368,66.86117133 -34.80910208,66.86117388 -34.80909338,66.86117494 -34.8090898,66.93281945 -34.5647568,67.00441882 -34.31942369,67.00441834 -34.31942359,67.07592335 -34.07510168,67.14737287 -33.83073849,67.21777858 -33.58537517,67.28811831 -33.34001123,67.35838201 -33.09560549,67.42858934 -32.85025274,67.49773049 -32.6058299,67.56682212 -32.36043528,67.63585135 -32.11504002,67.63585413 -32.11503015,67.63585478 -32.1150278,67.70382724 -31.86961401,67.77272059 -31.62519092)))", 1427 "MULTIPOLYGON(((67.840578 -31.37975347,67.77272059 -31.62519092,66.61484414 -31.38427789,66.68556685 -31.13932219,67.840578 -31.37975347)))", 1428 }; 1429 1430 1431 // Integer, ccw, open 1432 static std::string ticket_11674[2] = 1433 { 1434 "MULTIPOLYGON(((529 3217,529 998,5337 998,5337 1834,5070 2000,5337 2072,5337 3475,529 3475,529 3312,1734 2054,2934 1670,3230 1690,2934 1400,1734 1784,529 3217),(4140 2582,5071 2001,4140 1754,3231 1691,4140 2582)))", 1435 "MULTIPOLYGON(((528 3218,528 2498,1734 1406,2556 1522,1734 1784,528 3218)),((4610 2288,5340 1178,5340 1832,4609 2289,4140 3002,2934 1574,2555 1521,2934 1400,4140 2582,4610 2288)))", 1436 }; 1437 1438 // Union was reported as invalid because of no generated interior rings, fixed 1439 static std::string ticket_11984[2] = 1440 { 1441 "MULTIPOLYGON(((-104.025 72.5541,-95 67,-94 64,-95 60,-81.5804 61.9881,-75 52,-73.1862 50.0729,-75 48,-69.2 42.6,-96 56,-102 51,-119 49,-128 41,-126 33,-99 29,-61.9276 35.8291,-46 21,-30 10,-45 8,-104 6,-119 -8,-89 -18,-29 -10,-20 -9,-16 -11,-15 -13,-27 -29,-9 -13,-7 -14,-13.4737 -33.4211,-21 -34,-25 -36,-30 -40,-40 -49,-35 -50,-30 -51,-27 -53,-21 -52,-20.037 -52.642,-31.5314 -70.8413,-37.9815 -75.2274,-52.1689 -78.5148,-55 -78,-55 -79,-55 -79.1707,-112.692 -92.5385,-120 -94,-90.9143 -94.9695,-91 -95,-90 -99.5,-90 -103,-95 -114,-93 -116,-92 -117,-90 -119,-87.28 -119.68,-87 -120,-86.4444 -119.889,-82 -121,-80.821 -119.728,-77.6667 -119,-73 -119,-55 -114,-54 -114,-47 -114,-40 -121,-39.9327 -120.951,-39.3478 -121.609,-39 -123,-35.2182 -118.927,-24.536 -110.248,-22.875 -109.292,-22 -109,-22 -109,-16 -107,-9 -105,-7.83333 -104.833,-1.33333 -104.333,0.962934 -105.481,11.9682 -122.413,13 -129,20.1579 -120.053,22 -119,29.5 -115.25,30.2903 -114.968,39 -114,48 -112,47.156 -108.962,61 -117,54.9172 -103.176,65 -107,51.482 -95.3683,50.2426 -92.5515,53 -92,51.806 -91.0448,52 -91,49.1363 -88.9091,25.1429 -69.7143,22.733 -56.1314,24.9744 -49.3053,26.9174 -45.1157,27 -45,27.1481 -44.6543,33.4226 -34.0476,35.5919 -31.272,39 -29,39.4424 -26.3458,44.296 -20.136,46 -19,53 -14,53.3759 -13.4361,58.9297 -10.7874,115 13,110.286 13,114 14,112.414 14.7207,247.196 184.001,250 189,239.971 201.765,239 216,237.627 218.027,237.317 223.454,243 229)))", 1442 "MULTIPOLYGON(((-31 6,-51 220,-84 241,-120 249,-146 224,-67 56,-74 52,-95 60,-38 10,-38 9)))", 1443 }; 1444 1445 static std::string ticket_12118[2] = 1446 { 1447 "MULTIPOLYGON(((13.08940410614013671875 -70.98416137695312500000,12.81384754180908203125 -67.55441284179687500000,12.60483169555664062500 -63.57923889160156250000,13.56438255310058593750 -54.91608428955078125000,13.80568027496337890625 -43.62073516845703125000,13.00057315826416015625 -33.85240554809570312500,9.29664993286132812500 -33.23409271240234375000,19.66869926452636718750 -14.42036247253417968750,-5.96064376831054687500 -17.19871711730957031250,-14.87041568756103515625 -6.99879980087280273438,-22.50806808471679687500 -27.92480468750000000000,-22.16161727905273437500 -45.15484619140625000000,-22.42436790466308593750 -54.01613616943359375000,-23.13828659057617187500 -59.28628540039062500000,-23.18314933776855468750 -68.01937866210937500000,-22.86939430236816406250 -72.78530883789062500000,-23.02970123291015625000 -72.76760864257812500000,-22.81921195983886718750 -73.54760742187500000000,-18.65677833557128906250 -73.25045776367187500000,3.16641521453857421875 -75.66014099121093750000,12.75282478332519531250 -76.71865844726562500000,13.08940410614013671875 -70.98416137695312500000)))", 1448 "MULTIPOLYGON(((3.16641521453857421875 -75.66014099121093750000,12.75282478332519531250 -76.71865844726562500000,12.95001888275146484375 -74.61856842041015625000,3.16641521453857421875 -75.66014099121093750000)),((-22.84768676757812500000 -78.42963409423828125000,-20.92837524414062500000 -78.22530364990234375000,3.16641521453857421875 -75.66014099121093750000,-23.02970123291015625000 -72.76760864257812500000,-22.84768676757812500000 -78.42963409423828125000)))", 1449 }; 1450 1451 static std::string ticket_12125[2] = 1452 { 1453 "MULTIPOLYGON(((-5.96064376831054687500 -17.19871711730957031250,7.83307075500488281250 -32.98977279663085937500,8.81292819976806640625 -34.11151504516601562500,19.66869926452636718750 -14.42036247253417968750,-5.96064376831054687500 -17.19871711730957031250)),((-14.87041568756103515625 -6.99879980087280273438,-16.12161636352539062500 -18.30021858215332031250,-5.96064376831054687500 -17.19871711730957031250,-14.87041568756103515625 -6.99879980087280273438)))", 1454 "MULTIPOLYGON(((7.83307075500488281250 -32.98977279663085937500,8.81292819976806640625 -34.11151504516601562500,13.00057315826416015625 -33.85240554809570312500,7.83307075500488281250 -32.98977279663085937500)),((-22.50806808471679687500 -27.92480468750000000000,7.83307075500488281250 -32.98977279663085937500,-14.87041568756103515625 -6.99879980087280273438,-22.50806808471679687500 -27.92480468750000000000)))", 1455 }; 1456 1457 static std::string ticket_12751[4] = 1458 { 1459 /* a */ "MULTIPOLYGON(((1920 1462,3720 1462,3720 3262,1920 3262,1920 1462)))", 1460 /* b */ "MULTIPOLYGON(((1918 1957,1918 1657,2218 2189,1918 1957)),((3718 1957,3360 2233,3718 1561,3718 1957)),((3360 2233,2818 3253,2218 2189,2818 2653,3360 2233)))", 1461 /* c=a-b */ "MULTIPOLYGON(((1920 1660,1920 1462,3720 1462,3720 3262,1920 3262,1920 1959,2218 2189,1920 1660),(3718 1561,3360 2233,3718 1957,3718 1561),(2818 2653,2218 2189,2818 3253,3360 2233,2818 2653)))", 1462 /* d */ "MULTIPOLYGON(((1918 2155,1918 1957,2818 2653,3718 1957,3718 2154,2818 3055,1918 2155)))", 1463 }; 1464 1465 static std::string ticket_12752[2] = 1466 { 1467 "MULTIPOLYGON(((3232 2413,2136 2646,3232 2412,3232 2413)),((3232 2532,3232 2856,1031 2856,1031 1056,3232 1056,3232 2221,2136 2328,1032 1212,1032 1458,1032 1764,2136 2790,3232 2532)))", 1468 "MULTIPOLYGON(((1032 2130,1032 1764,2052 2712,1032 2130)),((3234 2580,2558 2690,3234 2532,3234 2580)),((2558 2690,2136 2790,2052 2712,2136 2760,2558 2690)))" 1469 }; 1470 1471 1472 // Ticket for validity, input is CCW 1473 static std::string ticket_12503[2] = 1474 { 1475 "MULTIPOLYGON (((15 17, 12 23, 15 20, 15 17)), ((35 23, 34 23, 34 24, 35 25, 36 25, 35 23)), ((8 6, 7 24, 10 25, 12 25, 12 23, 11 23, 10 13, 15 15, 8 6)), ((12 27, 8 31, 6 32, 6 38, 13 34, 13 31, 11 31, 12 30, 11 30, 12 29, 12 27)), ((7 24, 7 26, 6 31, 9 26, 7 24)), ((18 44, 15 45, 15 48, 18 44)), ((26 34, 18 44, 38 39, 26 34)), ((15 33, 13 34, 15 45, 15 33)), ((15 32, 15 33, 17 32, 15 32)), ((19 30, 17 32, 18 32, 16 38, 21 31, 19 30)), ((15 29, 13 30, 13 31, 15 32, 15 29)), ((15 28, 15 29, 17 29, 15 28)), ((14 27, 12 29, 13 30, 15 28, 14 27)), ((30 24, 25 24, 24 26, 25 27, 24 27, 23 28, 19 28, 19 29, 17 29, 18 30, 19 30, 22 29, 21 31, 26 34, 31 27, 28 30, 26 27, 30 24)), ((15 26, 15 28, 17 26, 15 26)), ((27 27, 31 27, 34 27, 32 26, 27 27)), ((19 25, 17 26, 19 26, 19 25)), ((41 15, 33 18, 35 23, 41 15)), ((23 24, 20 25, 19 26, 24 27, 24 26, 23 24)), ((33 15, 46 5, 48 4, 49 1, 32 13, 33 15)), ((32 23, 31 24, 32 25, 32 26, 33 25, 32 23)), ((35 23, 43 23, 44 23, 44 22, 43 22, 42 15, 35 23)), ((43 23, 36 25, 38 31, 35 25, 33 25, 34 27, 39 34, 40 39, 38 39, 44 42, 43 23)), ((48 22, 44 23, 48 46, 48 22)), ((18 11, 23 2, 15 3, 18 11)), ((29 17, 26 20, 22 23, 23 24, 25 24, 27 21, 28 20, 30 19, 29 17)), ((22 19, 21 20, 21 21, 24 19, 22 19)), ((31 23, 34 23, 31 19, 30 19, 31 22, 27 21, 30 24, 31 24, 31 23)), ((21 18, 20 21, 21 20, 21 18)), ((14 27, 15 26, 16 25, 19 25, 20 24, 22 23, 21 21, 20 21, 17 17, 15 20, 15 25, 12 25, 12 26, 14 26, 14 27), (20 21, 20 22, 17 24, 20 21)), ((22 17, 22 19, 23 18, 22 17)), ((30 15, 32 13, 31 10, 28 13, 30 15)), ((16 16, 17 17, 18 17, 16 16)), ((15 15, 15 17, 16 16, 15 15)), ((30 15, 29 16, 29 17, 30 17, 30 15)), ((33 15, 30 17, 31 19, 33 18, 33 15)), ((43 14, 44 22, 48 22, 48 4, 47 7, 42 13, 43 14)), ((43 14, 42 14, 41 15, 42 15, 43 14)), ((27 10, 25 6, 23 13, 27 11, 49 1, 24 2, 27 10)), ((28 13, 23 18, 24 19, 29 16, 28 13)), ((15 11, 15 15, 16 15, 17 13, 15 11)), ((18 11, 17 13, 19 15, 18 17, 21 18, 21 17, 20 15, 22 17, 23 13, 20 14, 18 11)), ((8 6, 8 5, 15 11, 15 3, 5 3, 8 6)))", 1476 "MULTIPOLYGON(((13 18,18 18,18 23,13 23,13 18)))" 1477 }; 1478 1479 static std::string issue_630_a[2] = 1480 { 1481 "MULTIPOLYGON(((-0.3 -0.1475,-0.3 +0.1475,+0.3 +0.1475,+0.3 -0.1475,-0.3 -0.1475)))", 1482 "MULTIPOLYGON(((-0.605 +0.1575,+0.254777333596 +1.0172773336,+1.53436796127 -0.262313294074,+0.674590627671 -1.12209062767,-0.605 +0.1575)))" 1483 }; 1484 1485 static std::string issue_630_b[2] = 1486 { 1487 "MULTIPOLYGON(((-0.3 -0.1475,-0.3 +0.1475,+0.3 +0.1475,+0.3 -0.1475,-0.3 -0.1475)))", 1488 "MULTIPOLYGON(((-1.215 +0.7675000000000001,-0.4962799075873666 +1.486220092412633,+0.665763075292561 +0.324177109532706,-0.05295701712007228 -0.3945429828799273,-1.215 +0.7675000000000001)))" 1489 }; 1490 1491 static std::string issue_630_c[2] = 1492 { 1493 "MULTIPOLYGON(((-0.3 -0.1475,-0.3 +0.1475,+0.3 +0.1475,+0.3 -0.1475,-0.3 -0.1475)))", 1494 "MULTIPOLYGON(((-0.9099999999999999 +0.4625,-0.1912799075873667 +1.181220092412633,+0.9707630752925609 +0.01917710953270602,+0.2520429828799277 -0.6995429828799273,-0.9099999999999999 +0.4625)))" 1495 }; 1496 1497 static std::string issue_643[2] = 1498 { 1499 "MULTIPOLYGON(((-0.420825839394717959862646239344 0.168094877926996288941552393226,5.29161113734201116187705338234 5.76881481261494233336861725547,12.2925110557019436896553088445 -1.37173140830596795858298264648,6.58007407896521545609402892296 -6.97245134299391278176472042105,-0.420825839394717959862646239344 0.168094877926996288941552393226)))", 1500 "MULTIPOLYGON(((4.75985680877701196159479187986e-16 -0.26112514220036736611874061964,0 0,0.72337592336357892097709054724 0.600648602980154100450249643472,1.223386680467822174023240222 1.19163154396839887638748223253,1.72339743757206620422550713556 2.1342216197599452875977021904,1.72339742847305732453833115869 -2.01889900623749607433410346857,4.75985680877701196159479187986e-16 -0.26112514220036736611874061964)))" 1501 }; 1502 1503 static std::string bug_21155501[2] = 1504 { 1505 "MULTIPOLYGON(((-8.3935546875 27.449790329784214,4.9658203125 18.729501999072138,11.8212890625 23.563987128451217,9.7119140625 25.48295117535531,9.8876953125 31.728167146023935,8.3056640625 32.99023555965106,8.5693359375 37.16031654673677,-1.8896484375 35.60371874069731,-0.5712890625 32.02670629333614,-8.9208984375 29.458731185355344,-8.3935546875 27.449790329784214)))", 1506 "MULTIPOLYGON(((4.9658203125 18.729501999072138,-3.4868710311820115 24.246968623627644,8.3589904332912 33.833614418115445,8.3056640625 32.99023555965106,9.8876953125 31.728167146023935,9.7119140625 25.48295117535531,11.8212890625 23.563987128451217,4.9658203125 18.729501999072138)),((-3.88714525609152 24.508246314579743,-8.3935546875 27.449790329784214,-8.9208984375 29.458731185355344,-0.5712890625 32.02670629333614,-1.8896484375 35.60371874069731,8.5693359375 37.16031654673677,8.362166569827938 33.883846345901595,-3.88714525609152 24.508246314579743)))", 1507 }; 1508 1509 static std::string mysql_21965285_b[2] = 1510 { 1511 "MULTIPOLYGON(((3 0, -19 -19, -7 3, -2 10, 15 0, 3 0)))", 1512 "MULTIPOLYGON(((1 1, 3 0, 19 -8, -4 -3, 1 1)),((3 0, -2 7, -3 16, 1 19, 8 12, 3 0)))" 1513 }; 1514 1515 // formerly mysql_1 1516 static std::string mysql_23023665_7[2] = 1517 { 1518 "MULTIPOLYGON(((4 5,12 11,-12 -3,4 5)))", 1519 "MULTIPOLYGON(((5 4,-14 0,1 0,5 4)),((1 6,13 0,10 12,1 6)))" 1520 }; 1521 1522 static std::string mysql_23023665_8[2] = 1523 { 1524 "MULTIPOLYGON(((0 0,0 40,40 40,40 0,0 0),(10 10,30 10,30 30,10 30,10 10)))", 1525 "MULTIPOLYGON(((10 10,10 20,20 10,10 10)),((20 10,30 20,30 10,20 10)),((10 20,10 30,20 20,10 20)),((20 20,30 30,30 20,20 20)))" 1526 }; 1527 1528 static std::string mysql_23023665_9[2] = 1529 { 1530 "MULTIPOLYGON(((0 0, 0 40, 40 40, 40 0, 0 0),(10 10, 30 10, 30 30, 10 30, 10 10)))", 1531 "MULTIPOLYGON(((15 10, 10 15, 10 17, 15 10)),((15 10, 10 20, 10 22, 15 10))," 1532 "((15 10, 10 25, 10 27, 15 10)),((25 10, 30 17, 30 15, 25 10))," 1533 "((25 10, 30 22, 30 20, 25 10)),((25 10, 30 27, 30 25, 25 10))," 1534 "((18 10, 20 30, 19 10, 18 10)),((21 10, 20 30, 22 10, 21 10)))" 1535 }; 1536 1537 static std::string mysql_23023665_12[2] = 1538 { 1539 "MULTIPOLYGON(((6 7,18 14,-8 1,0 0,18 -8,6 7),(6 0,-4 3,5 3,6 0)))", 1540 "MULTIPOLYGON(((2 3,-3 5,-10 -1,2 3)))" 1541 }; 1542 1543 static std::string mysql_regression_1_65_2017_08_31[2] = 1544 { 1545 "MULTIPOLYGON(((23.695652173913043 4.3478260869565215,23.333333333333336 4.166666666666667,25 0,23.695652173913043 4.3478260869565215)),((10 15,0 15,8.870967741935484 9.67741935483871,10.777777750841748 14.44444437710437,10 15)))", 1546 "MULTIPOLYGON(((10 15,20 15,15 25,10 15)),((10 15,0 15,7 10,5 0,15 5,15.90909090909091 4.545454545454546,17 10,10 15)),((23.695652173913043 4.3478260869565215,20 2.5,25 0,23.695652173913043 4.3478260869565215)))", 1547 }; 1548 1549 #endif // BOOST_GEOMETRY_TEST_MULTI_OVERLAY_CASES_HPP 1550