"MULTIPOLYGON(((1 1,1 2,2 2,2 1,1 1)),((1 2,0 1,0 3,1 4,1 2)))"
};
-static std::string case_101_multi[2] =
+static std::string case_101_multi[4] =
{
// interior ring / union
"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)))",
- "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)))"
+ "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)))",
+
+ // inverse versions
+ "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)))",
+ "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)))"
};
static std::string case_102_multi[4] =
"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)))",
"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)))",
- /* inverse versions (first was already having an interior, so outer ring is just removed */
+ // inverse versions (first was already having an interior, so outer ring is just removed
"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)))",
"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)))"
};
"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)))",
"MULTIPOLYGON(((5 7,6 8,6 10,7 9,8 10,8 8,7 8,6 7,6 6,5 7)))",
- /* inverse versions */
+ // inverse versions
"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)))",
"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)))"
};
"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)))"
};
+static std::string case_123_multi[2] =
+{
+ // Intersection: one cluster with 3 zones, intersection -> no holes
+ "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)))",
+ "MULTIPOLYGON(((1 0,1 2,2 2,2 0,1 0)),((0 1,0 2,1 1,0 1)))"
+};
+
+static std::string case_124_multi[2] =
+{
+ // Intersection: one cluster with 3 zones, intersection -> one hole
+ "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)))",
+ "MULTIPOLYGON(((1 0,1 2,2 2,2 0,1 0)),((0 1,0 2,1 1,0 1)))"
+};
+
+static std::string case_125_multi[2] =
+{
+ // Intersection: one cluster with 3 zones, intersection -> one hole (filled with other polygon)
+ "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)))",
+ "MULTIPOLYGON(((1 0,1 2,2 2,2 0,1 0)),((0 1,0 2,1 1,0 1)))"
+};
+
+static std::string case_126_multi[2] =
+{
+ // Intersection: should result in multi-polygon of 5 (needs self-intersections)
+ "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)))",
+ "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)))"
+};
+
+static std::string case_127_multi[2] =
+{
+ // Intersection/validity with ii at (4 4), and both have self intersections at (5 5)
+ "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)))",
+ "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)))"
+};
+
+static std::string case_128_multi[2] =
+{
+ // Contains isolated areas of two types
+ "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)))",
+ "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)))"
+};
+
+static std::string case_129_multi[2] =
+{
+ // Extract from rec.box #6
+ "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)))",
+ "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)))"
+};
+
+static std::string case_130_multi[2] =
+{
+ // For validity
+ "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)))",
+ "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)))"
+};
+
+static std::string case_131_multi[2] =
+{
+ // For validity, interior ring connections
+ "MULTIPOLYGON(((1 2,1 3,2 3,2 2,1 2)),((2 1,2 2,3 2,3 1,2 1)))",
+ "MULTIPOLYGON(((0 0,0 4,4 4,4 0,0 0),(3 3,1 3,1 1,3 1,3 3)))"
+};
+
+static std::string case_132_multi[2] =
+{
+ // For validity, interior ring connections including cluster
+ "MULTIPOLYGON(((2 4,2 6,4 6,4 4,2 4)),((4 2,4 4,6 4,6 2,4 2)))",
+ "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)))"
+};
+
+static std::string case_133_multi[2] =
+{
+ // Zoomed in version of case_recursive_boxes_49 with in both interiors an extra polygon (same for both)
+ "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)))",
+ "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)))"
+};
+
+static std::string case_134_multi[2] =
+{
+ // Zoomed in version of case_recursive_boxes_49 with two interior rings
+ "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)))",
+ "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)))"
+};
+
+static std::string case_135_multi[2] =
+{
+ // Contains two equal interior rings, both touching to their exterior rings
+ // Needs detection of isolated interior ring pattern
+ "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)))",
+ "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)))"
+};
+
+static std::string case_136_multi[2] =
+{
+ // Variant of 135, but approaching cluster is non equal
+ "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)))",
+ "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)))"
+};
+
+static std::string case_137_multi[2] =
+{
+ // Variant of 135, but leaving cluster is non equal
+ "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)))",
+ "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)))"
+};
+
+static std::string case_138_multi[2] =
+{
+ // Zoomed in version of case_recursive_boxes_49 with in both interiors an extra polygon (different for both)
+ "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)))",
+ "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)))"
+};
+
+static std::string case_139_multi[2] =
+{
+ // Another zoomed in version of case_recursive_boxes_49 with different interior polygons
+ "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)))",
+ "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)))"
+};
+
+static std::string case_140_multi[2] =
+{
+ // Another zoomed in version of case_recursive_boxes_49 with different interior polygons
+ "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)))",
+ "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)))"
+};
+
+static std::string case_141_multi[2] =
+{
+ // Version to test more isolation/validity cases
+ "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)))",
+ "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)))"
+};
+
static std::string case_recursive_boxes_1[2] =
{
"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)))",
"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)))"
};
+static std::string case_recursive_boxes_39[2] =
+{
+ // Needs check for back at start during traversal
+ "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)))",
+ "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)))"
+};
+
+static std::string case_recursive_boxes_40[2] =
+{
+ "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)))",
+ "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)))"
+};
+
+static std::string case_recursive_boxes_41[2] =
+{
+ // Smaller version of 35 for validity checks
+ "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)))",
+ "MULTIPOLYGON(((0 0,0 5,5 5,5 0,0 0),(2 3,2 4,1 4,1 3,2 3)))"
+};
+
+static std::string case_recursive_boxes_42[2] =
+{
+ // Smaller version of 2 for validity checks
+ "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)))",
+ "MULTIPOLYGON(((0 0,0 10,10 10,10 0,0 0),(6 7,7 7,7 8,6 8,6 7)))"
+};
+
+static std::string case_recursive_boxes_43[2] =
+{
+ // Smaller version of 35 for validity checks
+ "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)))",
+ "MULTIPOLYGON(((1 0,0 0,0 5,3 5,5 5,5 0,1 0),(1 0,2 1,1 1,1 0)))"
+};
+
+static std::string case_recursive_boxes_44[2] =
+{
+ // Needs discarding uu turns in intersections, either globally or in aggregations
+ "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)))",
+ "MULTIPOLYGON(((2 1,2 2,3 2,3 1,2 1)),((1 0,0 0,0 1,2 1,2 0,1 0)))"
+};
+
+static std::string case_recursive_boxes_45[2] =
+{
+ // Needs discarding u/x turns in aggregations (for clusters for intersections)
+ // This case did go wrong, don't make it smaller, it also depends on the order of turns
+ "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)))",
+ "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)))"
+};
+
+static std::string case_recursive_boxes_46[2] =
+{
+ "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)))",
+ "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)))"
+};
+
+static std::string case_recursive_boxes_47[2] =
+{
+ // Needs open_count==0 in get_ring_turn_info to select_rings
+ "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)))",
+ "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)))"
+};
+
+static std::string case_recursive_boxes_48[2] =
+{
+ // Needs discarding self-ii turns not located within the other geometry
+ "MULTIPOLYGON(((6 7,6 8,7 8,7 7,6 7)))",
+ "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)))"
+};
+
+static std::string case_recursive_boxes_49[2] =
+{
+ // Needs specific handling for cc interior rings touching one exterior ring
+ "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)))",
+ "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)))"
+};
+
+static std::string case_recursive_boxes_50[2] =
+{
+ // Same as 49 but needs the second variant
+ "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)))",
+ "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)))"
+};
+
+static std::string case_recursive_boxes_51[2] =
+{
+ // Needs keeping colocated turns with a xx turn to properly generate interior rings. It also needs self-turns for validity
+ "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)))",
+ "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)))"
+};
+
+static std::string case_recursive_boxes_52[2] =
+{
+ // Needs checking for isolated in handling of cc_ii clusters for intersection
+ "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)))",
+ "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)))"
+};
+
+static std::string case_recursive_boxes_53[2] =
+{
+ // Needs checking for intersection patterns intersection_pattern_common_interior2 with ii
+ "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)))",
+ "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)))"
+};
+
+static std::string case_recursive_boxes_54[2] =
+{
+ // Needs including blocked from-ranks/operations in aggregations
+ "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)))",
+ "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)))"
+};
+
+static std::string case_recursive_boxes_55[2] =
+{
+ // Needs correct handling for union clusters with 3 open spaces
+ "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)))",
+ "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)))"
+};
+
+static std::string case_recursive_boxes_56[2] =
+{
+ // Needs not discarding clustered self-turns if the cluster does not contain anything else
+ "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)))",
+ "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)))"
+};
+
+static std::string case_recursive_boxes_57[2] =
+{
+ // Needs handling of 3 open spaces in union to form interior ring
+ "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)))",
+ "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)))",
+};
+
+static std::string case_recursive_boxes_58[2] =
+{
+ // Needs correct handling for union clusters with 3 open spaces
+ "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)))",
+ "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)))",
+};
+
+static std::string case_recursive_boxes_59[2] =
+{
+ // Needs correct handling for union clusters with 3 open spaces
+ "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)))",
+ "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)))",
+};
+
+static std::string case_recursive_boxes_60[2] =
+{
+ // Needs checking left_count in union clusters
+ "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)))",
+ "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)))",
+};
+
+
+static std::string case_recursive_boxes_61[2] =
+{
+ // Needs pattern 4 for intersections
+ "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)))",
+ "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)))",
+};
+
+static std::string case_recursive_boxes_62[2] =
+{
+ // Needs discarding self-intersections within other geometry
+ "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)))",
+ "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)))",
+};
+
+static std::string case_recursive_boxes_63[2] =
+{
+ // Derived from 62, needs not excluding startable points for checking rings for traversals
+ "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)))",
+ "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)))",
+};
+
+static std::string case_recursive_boxes_64[2] =
+{
+ // Needs considering remaining_distance in clusters
+ "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)))",
+ "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)))"
+};
+
+static std::string case_recursive_boxes_65[2] =
+{
+ // Misses large hole in intersection
+ "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)))",
+ "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)))"
+};
+
+static std::string case_recursive_boxes_66[2] =
+{
+ // Needs self-turns startable, at least not determined using count left/right for self-turns
+ "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)))",
+ "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)))"
+};
+
+static std::string case_recursive_boxes_67[2] =
+{
+ // Needs to avoid including any untraveled ring with blocked turns
+ "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)))",
+ "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)))"
+};
+
+static std::string case_recursive_boxes_68[2] =
+{
+ // Needs checking blocked turns in colocated turns
+ "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)))",
+ "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)))"
+};
+
+static std::string case_recursive_boxes_69[2] =
+{
+ // Needs checking left_count instead of is_closed for decision to block untraversed rings
+ "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)))",
+ "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)))"
+};
+
+static std::string case_recursive_boxes_70[2] =
+{
+ // Needs checking left_count instead of is_closed for decision to block untraversed rings
+ "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)))",
+ "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)))"
+};
+
+static std::string case_recursive_boxes_71[2] =
+{
+ // Needs check for self-cluster within other geometry, in intersections
+ "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)))",
+ "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)))"
+};
+
+static std::string case_recursive_boxes_72[2] =
+{
+ // Needs selection of ranked point in union (to finish the ring)
+ "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)))",
+ "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)))"
+};
+
+static std::string case_recursive_boxes_73[2] =
+{
+ // Needs handling connection points identical for clustered/non-clustered turns
+ "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)))",
+ "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)))"
+};
+
+static std::string case_recursive_boxes_74[2] =
+{
+ // Needs another method to find isolated regions (previous attempted used parents, that is dropped now)
+ "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)))",
+ "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)))"
+};
+
+static std::string case_recursive_boxes_75[2] =
+{
+ // Needs intersection pattern 6 (skip all isolated ranks in between)
+ "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)))",
+ "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)))"
+};
+
+static std::string case_recursive_boxes_76[2] =
+{
+ // Needs considering ix/ix turns (opposite in both directions) as the same region
+ "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)))",
+ "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)))"
+};
+
+static std::string case_recursive_boxes_77[2] =
+{
+ // Needs discarding self i/u turn traveling to itself (for intersection only)
+ "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)))",
+ "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)))"
+};
+
+static std::string case_recursive_boxes_78[2] =
+{
+ // Needs checking intersection/right_count in overlay, as was already done for union
+ "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)))",
+ "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)))"
+};
+
+static std::string case_recursive_boxes_79[2] =
+{
+ // Found by bug in discard_self_turns_which_loop, it needs only checking intersection and not union
+ "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)))",
+ "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)))"
+};
+
+static std::string case_recursive_boxes_80[2] =
+{
+ // Creates very small interior ring (~0) for union. This is a robustness
+ // problem, it should not be generated. The intersection point is a tiny
+ // distance away from real IP, and therefore it generates a correct
+ // interior ring, and is considered as valid. But if you combine this
+ // resulting union later with other polygons, with another rescaling model,
+ // it most probably will be invalid.
+ // These cases are found with recursive_polygons and size=4.
+ // For size=5 the scaling is such that it does not occur (so often)
+ // It needs removing the rescaling.
+ "MULTIPOLYGON(((3.5 2.5,4 3,4 2,3 2,3 3,3.5 2.5)))",
+ "MULTIPOLYGON(((1 1,1 2,2 1,1 1)),((3 2,3 3,4 3,3 2)))"
+};
+
static std::string pie_21_7_21_0_3[2] =
{
"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)))",
"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)))"
};
+// Integer, ccw, open, reported by Volker
+static std::string ticket_9942[2] =
+ {
+ "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)))",
+ "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)))",
+ };
+
+// Simplified version showing the generated 'spike' which actually has an area because of the necessary rounding
+static std::string ticket_9942a[2] =
+ {
+ "MULTIPOLYGON(((2058 1761,1996 1700,1660 1370,1324 1040,2644 981,2338 1982)))",
+ "MULTIPOLYGON(((2674 884,2338 1982,1996 1712,1660 1442,1324 1148,1324 1136,1660 1304,1996 1460,2338 1610,2674 434)))",
+ };
+
// Integer, ccw, open
static std::string ticket_10661[3] =
{
"MULTIPOLYGON(((67.840578 -31.37975347,67.77272059 -31.62519092,66.61484414 -31.38427789,66.68556685 -31.13932219,67.840578 -31.37975347)))",
};
+
// Integer, ccw, open
static std::string ticket_11674[2] =
{
static std::string ticket_12125[2] =
{
"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)))",
- "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))) ",
+ "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)))",
+ };
+
+static std::string ticket_12751[4] =
+ {
+ /* a */ "MULTIPOLYGON(((1920 1462,3720 1462,3720 3262,1920 3262,1920 1462)))",
+ /* 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)))",
+ /* 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)))",
+ /* d */ "MULTIPOLYGON(((1918 2155,1918 1957,2818 2653,3718 1957,3718 2154,2818 3055,1918 2155)))",
+ };
+
+static std::string ticket_12752[2] =
+ {
+ "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)))",
+ "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)))"
+ };
+
+
+// Ticket for validity, input is CCW
+static std::string ticket_12503[2] =
+ {
+ "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)))",
+ "MULTIPOLYGON(((13 18,18 18,18 23,13 23,13 18)))"
};
static std::string bug_21155501[2] =
"MULTIPOLYGON(((2 3,-3 5,-10 -1,2 3)))"
};
+static std::string mysql_regression_1_65_2017_08_31[2] =
+ {
+ "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)))",
+ "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)))",
+ };
+
#endif // BOOST_GEOMETRY_TEST_MULTI_OVERLAY_CASES_HPP
projects / ceph.git / blobdiff