search

google / s2-geometry-library-java

Automatically exported from code.google.com/p/s2-geometry-library-java
Apache License 2.0
533 stars 230 forks source link

[BUG] OOM happened when S2RegionCoverer try to getCovering !!! #17

Closed ChrisXuzhou closed 3 years ago

ChrisXuzhou commented 5 years ago

My code like this:

` S2Polygon s2Polygon = makePolygon(polygon);

    S2RegionCoverer cover = new S2RegionCoverer();
    cover.setMaxLevel(cellLevel);
    cover.setMinLevel(cellLevel);
    cover.setMaxCells(MAX_CELLS);

    ArrayList<S2CellId> covering = new ArrayList<>();
    cover.getCovering(s2Polygon, covering);`

OOM happened!

analyzed the java.hprof, found the PriorityQueue used 3.5GB memory, which leaded to the out of memory.

the parameter polygon like this:

POLYGON((81.285967 30.993679,81.270861 30.984114,81.281333 30.984555,81.269488 30.974253,81.284251 30.974106,81.268973 30.965863,81.277384 30.963214,81.275153 30.974253,81.276011 30.978521,81.297125 30.98117,81.279616 30.961889,81.276869 30.970573,81.284251 30.972192,81.281676 30.978816,81.287856 30.98691,81.295409 30.982936,81.283221 30.98014,81.294894 30.969837,81.306395 30.979404,81.301245 30.986763,81.315493 30.99,81.30485 30.957914,81.293349 30.960564,81.285281 30.9613,81.297125 30.97543,81.297469 30.994121,81.290431 30.995298,81.314463 31.000742,81.30382 30.98117,81.299357 30.982789,81.293692 30.989117,81.294036 30.992796,81.269488 30.978227,81.306052 30.977491,81.296954 30.970868,81.287169 30.964097,81.284251 30.967482,81.277556 30.969396,81.310343 30.970573,81.327166 30.982642,81.303134 30.978668,81.320815 30.972928,81.312232 30.956442,81.30382 30.966894,81.300044 30.962772,81.315837 30.979257,81.315837 30.985291,81.333861 30.989412,81.318583 30.994856,81.311545 30.994709,81.303305 30.98794,81.30794 30.976019,81.307082 30.982348,81.311717 30.985585,81.339526 30.983967,81.326651 30.971015,81.325621 30.976019,81.321845 30.976608,81.32236 30.966746,81.314807 30.96601,81.327338 30.963067,81.31206 30.959239,81.310515 30.962036,81.304507 30.960417,81.297297 30.961889,81.291976 30.964097,81.279959 30.963361,81.272406 30.970868,81.272063 30.979404,81.270346 30.980876,81.279101 30.989706,81.282534 31.000154,81.302447 31.000006,81.300559 30.993238,81.306395 30.994709,81.317553 30.998976,81.285967 30.993679))

ChrisXuzhou commented 5 years ago

ADD more code of converting from polygon:

` public static S2Polygon makePolygon(String str) {

    try {
        String poly = parsePolygonFrom(str);
        List<S2Loop> loops = Lists.newArrayList();

        for (String token : Splitter.on(';').omitEmptyStrings().split(poly)) {
            S2Loop loop = makeLoop(token);
            loop.normalize();
            loops.add(loop);
        }

        return new S2Polygon(loops);
    } catch (Exception e) {
        throw new GeometryException(GeometryException.WKT_FORMAT_ERROR, GeometryException.WKT_FORMAT_ERROR, e);
    }
}`

` private final static String POLYGON_PREFIX = "POLYGON\(\("; private final static String POLYGON_SUFFIX = "\)\)";

public static String parsePolygonFrom(String origin) {
    String p1 = origin.replaceAll(POLYGON_PREFIX, "");
    return p1.replaceAll(POLYGON_SUFFIX, "");
}

`

' static S2Loop makeLoop(String str) { List vertices = Lists.newArrayList(); parseVertices(str, vertices); return new S2Loop(vertices); } '

rockwotj commented 4 years ago

@ChrisXuzhou what is the value for MAX_CELLS?

bright-chan commented 4 years ago

@ChrisXuzhou Hi. I had same problem yesterday. make sure your loops are normalized. S2Loop's direction must be CCW direction. but your polygon isn't. usenormalize() to normalize your loops

stevebriskin commented 3 years ago

Had a similar problem. Normalization alone did not help. As I understand, normalize() ensures the correct direction but does not ensure that the loop is a valid polygon. In addition to normalization, ensure that your vertices are listed in the correct order or add an isValid() check before getting a cover.

eengle commented 3 years ago

Normalization occurs after the covering is generated, so it has no chance of helping.

The PriorityQueue contains relatively small objects, so if you're OOMing it's very likely because of the parameters you're using.

Steve, Chris, can you share more complete examples, in particular showing how you each construct an S2RegionCoverer?

Thanks,

eengle commented 3 years ago

I'm closing this, but feel free to reopen if you have more details to share.