ceph/src/boost/libs/geometry/test/algorithms/overlay/multi_overlay_cases.hpp

   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 pie_21_7_21_0_3[2] =
1240 {
1241     "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)))",
1242     "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)))"
1243 };
1244
1245 static std::string pie_23_19_5_0_2[2] =
1246 {
1247     "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)))",
1248     "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)))"
1249 };
1250
1251 static std::string pie_7_14_5_0_7[2] =
1252 {
1253     "MULTIPOLYGON(((2500 2500,2500 3875,2855 3828,3187 3690,3472 3472,3690 3187,3828 2855,3875 2500,2500 2500)))",
1254     "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)))"
1255 };
1256
1257 static std::string pie_16_16_9_0_2[2] =
1258 {
1259     "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)))",
1260     "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)))"
1261 };
1262
1263 static std::string pie_7_2_1_0_15[2] =
1264 {
1265     "MULTIPOLYGON(((2500 2500,2500 3875,2855 3828,3187 3690,3472 3472,3690 3187,3828 2855,3875 2500,2500 2500)))",
1266     "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)))"
1267 };
1268
1269 // Case, not literally on this list but derived, to mix polygon/multipolygon in call to difference
1270 static std::string ggl_list_20111025_vd[4] =
1271     {
1272     "POLYGON((0 0,0 4,4 0,0 0))",
1273     "POLYGON((10 0,10 5,15 0,10 0))",
1274     "MULTIPOLYGON(((0 0,0 4,4 0,0 0)))",
1275     "MULTIPOLYGON(((10 0,10 5,15 0,10 0)))"
1276     };
1277
1278 // Same, mail with other case with text "Say the MP is the 2 squares below and P is the blue-ish rectangle."
1279 static std::string ggl_list_20111025_vd_2[2] =
1280     {
1281     "POLYGON((5 0,5 4,8 4,8 0,5 0))",
1282     "MULTIPOLYGON(((0 0,0 2,2 2,2 0,0 0)),((4 0,4 2,6 2,6 0,4 0)))"
1283     };
1284
1285 // Mail of h2 indicating that reversed order (in second polygon) has ix/ix problems
1286 static std::string ggl_list_20120915_h2[3] =
1287     {
1288         "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)))",
1289         "MULTIPOLYGON(((0 0, 1 0, 1 -1, 0 -1, 0 0)), ((-1 5, 0 5, 0 0, -1 0, -1 5)))",
1290         "MULTIPOLYGON(((-1 5, 0 5, 0 0, -1 0, -1 5)), ((0 0, 1 0, 1 -1, 0 -1, 0 0)))"
1291     };
1292
1293 // Mail of volker, about another problem, but this specific example is causing two-point inner rings polygons which should be discarded
1294 // (condition of num_points in detail/overlay/convert_ring.hpp)
1295 static std::string ggl_list_20120221_volker[2] =
1296     {
1297         "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)))",
1298         "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)))"
1299     };
1300
1301 static std::string ggl_list_20140212_sybren[2] =
1302     {
1303         "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)))",
1304         "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)))"
1305     };
1306
1307 static std::string ticket_9081[2] =
1308     {
1309         "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)))",
1310         "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)))"
1311     };
1312
1313 // Integer, ccw, open, reported by Volker
1314 static std::string ticket_9942[2] =
1315     {
1316         "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)))",
1317         "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)))",
1318     };
1319
1320 // Simplified version showing the generated 'spike' which actually has an area because of the necessary rounding
1321 static std::string ticket_9942a[2] =
1322     {
1323         "MULTIPOLYGON(((2058 1761,1996 1700,1660 1370,1324 1040,2644 981,2338 1982)))",
1324         "MULTIPOLYGON(((2674 884,2338 1982,1996 1712,1660 1442,1324 1148,1324 1136,1660 1304,1996 1460,2338 1610,2674 434)))",
1325     };
1326
1327 // Integer, ccw, open
1328 static std::string ticket_10661[3] =
1329     {
1330         /* A */ "MULTIPOLYGON(((1701 985,3501 985,3501 2785,1701 2785,1701 985)))",
1331         /* B */ "MULTIPOLYGON(((1698 1860,1698 1122,2598 1392,3492 1842,3492 32706,2598 2340,1698 1860)))",
1332         /* C=A-B, */
1333         /* D */ "MULTIPOLYGON(((1698 2772,1698 1860,2598 2340,3492 2412,3492 32743,1698 2772)))"
1334         // Reported problem was: validity of difference C-D
1335     };
1336
1337 // Integer, ccw, open
1338 static std::string ticket_10803[2] =
1339     {
1340         "MULTIPOLYGON(((3174 1374,3174 2886,1374 2886,1374 2139,3174 1374)))",
1341         "MULTIPOLYGON(((1374 1092,1734 1092,3174 2526,3174 2886,1374 2886,1374 1092)))"
1342     };
1343
1344 // Intersection was reported as invalid
1345 static std::string ticket_11018[2] =
1346     {
1347         "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)))",
1348         "MULTIPOLYGON(((67.840578 -31.37975347,67.77272059 -31.62519092,66.61484414 -31.38427789,66.68556685 -31.13932219,67.840578 -31.37975347)))",
1349     };
1350
1351
1352 // Integer, ccw, open
1353 static std::string ticket_11674[2] =
1354     {
1355         "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)))",
1356         "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)))",
1357     };
1358
1359 // Union was reported as invalid because of no generated interior rings, fixed
1360 static std::string ticket_11984[2] =
1361     {
1362         "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)))",
1363         "MULTIPOLYGON(((-31 6,-51 220,-84 241,-120 249,-146 224,-67 56,-74 52,-95 60,-38 10,-38 9)))",
1364     };
1365
1366 static std::string ticket_12118[2] =
1367     {
1368         "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)))",
1369         "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)))",
1370     };
1371
1372 static std::string ticket_12125[2] =
1373     {
1374         "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)))",
1375         "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)))",
1376     };
1377
1378 static std::string ticket_12751[4] =
1379     {
1380         /* a */     "MULTIPOLYGON(((1920 1462,3720 1462,3720 3262,1920 3262,1920 1462)))",
1381         /* 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)))",
1382         /* 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)))",
1383         /* d */     "MULTIPOLYGON(((1918 2155,1918 1957,2818 2653,3718 1957,3718 2154,2818 3055,1918 2155)))",
1384     };
1385
1386 static std::string ticket_12752[2] =
1387     {
1388         "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)))",
1389         "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)))"
1390     };
1391
1392
1393 // Ticket for validity, input is CCW
1394 static std::string ticket_12503[2] =
1395     {
1396         "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)))",
1397         "MULTIPOLYGON(((13 18,18 18,18 23,13 23,13 18)))"
1398     };
1399
1400 static std::string bug_21155501[2] =
1401     {
1402         "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)))",
1403         "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)))",
1404     };
1405
1406 static std::string mysql_21965285_b[2] =
1407     {
1408         "MULTIPOLYGON(((3 0, -19 -19, -7 3, -2 10, 15 0, 3 0)))",
1409         "MULTIPOLYGON(((1 1, 3 0, 19 -8, -4 -3, 1 1)),((3 0, -2 7, -3 16, 1 19, 8 12, 3 0)))"
1410     };
1411
1412 // formerly mysql_1
1413 static std::string mysql_23023665_7[2] =
1414     {
1415         "MULTIPOLYGON(((4 5,12 11,-12 -3,4 5)))",
1416         "MULTIPOLYGON(((5 4,-14 0,1 0,5 4)),((1 6,13 0,10 12,1 6)))"
1417     };
1418
1419 static std::string mysql_23023665_8[2] =
1420     {
1421         "MULTIPOLYGON(((0 0,0 40,40 40,40 0,0 0),(10 10,30 10,30 30,10 30,10 10)))",
1422         "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)))"
1423     };
1424
1425 static std::string mysql_23023665_9[2] =
1426     {
1427         "MULTIPOLYGON(((0 0, 0 40, 40 40, 40 0, 0 0),(10 10, 30 10, 30 30, 10 30, 10 10)))",
1428         "MULTIPOLYGON(((15 10, 10 15, 10 17, 15 10)),((15 10, 10 20, 10 22, 15 10)),"
1429                      "((15 10, 10 25, 10 27, 15 10)),((25 10, 30 17, 30 15, 25 10)),"
1430                      "((25 10, 30 22, 30 20, 25 10)),((25 10, 30 27, 30 25, 25 10)),"
1431                      "((18 10, 20 30, 19 10, 18 10)),((21 10, 20 30, 22 10, 21 10)))"
1432     };
1433
1434 static std::string mysql_23023665_12[2] =
1435     {
1436         "MULTIPOLYGON(((6 7,18 14,-8 1,0 0,18 -8,6 7),(6 0,-4 3,5 3,6 0)))",
1437         "MULTIPOLYGON(((2 3,-3 5,-10 -1,2 3)))"
1438     };
1439
1440 static std::string mysql_regression_1_65_2017_08_31[2] =
1441     {
1442         "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)))",
1443         "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)))",
1444     };
1445
1446 #endif // BOOST_GEOMETRY_TEST_MULTI_OVERLAY_CASES_HPP