S2RegionCoverer.getCoveringInternal Tries to cover whole globe!

A small number of my polygons were causing my whole pipeline to hang, often indefinitely. For the most part these were weird and wonderful shapes, often with artefacts in them that could be smoothed out. Unfortunately this then started happening on "normal" polygons so I went digging.

Turns out that for certain shapes what it was trying to do is spin over pretty much all the shapes in existence to determine the covering. The below code demonstrates this, working at level 0 we get all 6 faces and the runtime just increases exponentially from then on.

I'm not sure I get enough of S2's internals to fix/understand this without an amount of study I don't really have time for but I've got no problem putting a fix in for it if someone can help me pin it down.

Reproducible example below, the polygon is valid (according to geotools anyway!).

import com.google.common.base.Splitter;
import com.google.common.collect.Lists;
import com.google.common.geometry.*;

import java.util.List;
import java.util.regex.Matcher;
import java.util.regex.Pattern;

    public class WholeWorldCover {
        public static void main(String[] args){
        String wkt = "POLYGON ((-89.9974614685473 42.15403016972965, -89.99752600008779 42.15408700006392, " +
                "-89.99754400018493 42.15414700007223, -89.99807800018294 42.15445900022545, -89.99899900035857 " +
                "42.15480200025107, -89.99924099979629 42.15497899993318, -89.99934000002949 42.15512000023752, " +
                "-89.99943299984827 42.15537600025726, -89.99943199992789 42.15600500026407, -89.99980300014222 " +
                "42.15624099991698, -90.00021899969302 42.1564019997966, -90.00042300019753 42.15641199997486, " +
                "-90.00061899988526 42.15635400002513, -90.00096600024632 42.1563799999147, -90.00149700017636 " +
                "42.15658299986155, -90.00164199998356 42.15660600027495, -90.00206599973555 42.15655199990527, " +
                "-90.00211300016505 42.1565340001793, -90.00233399965521 42.15639599976716, -90.00243700009044 " +
                "42.15626100003033, -90.00185400009356 42.15523199992804, -90.00164600035576 42.15499299974192, " +
                "-90.00138000035743 42.1547950000587, -90.00073099994236 42.1545440002246, -90.00061000029626 " +
                "42.15447800026342, -90.00028399969882 42.15422200011501, -89.99982300036059 42.15406400001554, " +
                "-89.99972302165392 42.15401246897738, -89.9974614685473 42.15403016972965))";

        S2CellUnion x = WktToS2(wkt, 100, 0, 0);
        System.out.println(x.cellIds());
        System.out.println(x.cellIds().size());

        S2CellUnion y = WktToS2(wkt, 100, 15, 15);
        System.out.println(y.cellIds());
        System.out.println(y.cellIds().size());
        }

    static void ParseVertices(String wkt_coords, List<S2Point> vertices) {
        if (wkt_coords == null) {
            return;
        }

        for (String token : Splitter.on(", ").split(wkt_coords)) {
            int colon = token.indexOf(' ');
            if (colon == -1) {
                throw new IllegalArgumentException(
                        "Illegal string:" + token + ". Should look like '35 20'");
            }
            double lat = Double.parseDouble(token.substring(0, colon));
            double lng = Double.parseDouble(token.substring(colon + 1));
            vertices.add(S2LatLng.fromDegrees(lat, lng).toPoint());
        }
    }

    static S2Loop MakeLoop(String wkt_coords) {
        List<S2Point> vertices = Lists.newArrayList();
        ParseVertices(wkt_coords, vertices);
        return new S2Loop(vertices);
    }

    static S2CellUnion ConvertToUnion(S2Polygon poly, int maxCells, int smallestCell, int largestCell) {
        S2RegionCoverer coverer = new S2RegionCoverer();

        coverer.setMaxCells(maxCells);
        coverer.setMaxLevel(smallestCell);
        coverer.setMinLevel(largestCell);

        System.out.println("coverer");
        S2CellUnion polyCells = coverer.getCovering(poly);
        System.out.println("polyCells");
        polyCells.pack();

        return polyCells;
    }

    public static S2CellUnion WktToS2(String wkt, int maxPossCells, int smallestCell, int largestCell) {
        Pattern p = Pattern.compile("\\(([0-9 ,-.]+)\\)");
        Matcher m = p.matcher(wkt);
        List<S2Loop> loops = Lists.newArrayList();

        while (m.find()) {
            String lp = m.group(1);
            S2Loop loop = MakeLoop(lp);
            loop.normalize();
            loops.add(loop);
        }
        S2Polygon poly = new S2Polygon(loops);
        return ConvertToUnion(poly, maxPossCells, smallestCell, largestCell);
    }
}

google / s2-geometry-library-java

S2RegionCoverer.getCoveringInternal Tries to cover whole globe! #23