Line 258-260 as below should be removed:

            if (!u.contains(xId)) {
              u.getIntersection(xCells, yId);
            }

It is extraneous and guarantees the subsequent assertTrue(u.contains(xId)); on 
line 261 will always work even though this is the line that is being ultimately 
tested.

Original issue reported on code.google.com by [email protected] on 9 Jul 2013 at 1:39

Would it be possible for the good folks here to please help me with a problem that I am trying to solve with the S2 geometry library? I am a complete novice, so please bear with me if I do not make sense.

Problem
I am trying to determine the best way to write an offline point-in-polygon check for the Android platform. Essentially, convert (lat,lng) to a country. In future, I plan to increase the granularity to regions, states, provinces, counties and cities/towns.

Research
My initial research landed me up on https://github.com/AReallyGoodName/OfflineReverseGeocode with http://download.geonames.org/export/dump/cities1000.zip. From what I understand, this is (lat,lng) to nearest neighbor. Now, I do get the country from this, but it relies on finding the nearest neighbor city with population, which may not be accurate.

Further research led me to S2. It is here that I am struggling, and request your guidance.

Current Approach
A) Computation at app startup:

1. Get geojson co-ordinates from http://download.geonames.org/export/dump/shapes_simplified_low.zip.
2. For each country,
   i) Convert geojson co-ordinates into S2 LatLng and then S2 Loops.
   ii) Build S2 Polygon using S2 Loops.
   iii) If MultiPolygon, use S2PolygonBuilder.addPolygon() to add additional polygons.

B) LatLng input during app functioning:

1. Convert Lat Lng Input to S2Point.
2. Iterate over country polygons, checking for S2Polygon.contains(S2Point).
3. Return country.

Questions

1. Some geojson countries are "multipolygon", whereas there is no multipolygon in S2. Are S2 polygons equivalent to multipolygons from geojson?
2. Can the geojson to S2Polygon initial computation result be persisted, to avoid re-computation at app startup?
3. Geonames geojson input does not seem to conform to counter clockwise (CCW) convention. Would S2PolygonBuilder be able to tackle this correctly?
4. Is there a better way to search for point-in-polygon rather than iterating over each countries S2Polygons.contains function call? Does this mechanism also help avoid polygon re-computation?
5. Is there a better way to achieve the offline point-in-polygon check?
6. Is there a better (small, accurate) source for country boundaries for use with S2?

Thank you for your time.

@eengle @hagbard @kluever @cpovirk

Please change this S2 project to Maven project and upload release version. Thank you.

Hi,
i need to create the cell for list of lat and long and then have to retrieve the cells based on shortest distance or nearby cells.

List S2CellList = new ArrayList();
S2Cell s2cell = new S2Cell(S2LatLng.fromDegrees(lat,long).toPoint());
S2CellList.add(s2cell);

like that i have added the set of cell to list for the list of lat and long. Now i need to show the cell with shortest distance. please guide me in coding.

Hi,
what is the recommended way to find two polylines (intersecting each other) are in same direction.
Is there any function written for it?

Any Help??

Where is the method S1Angle.fromEarthDistance() , the S1Angle.fromEarthDistance(5000) is mentioned in class S2ClosestPointQuery , but I can't find it

Level 0's average area is 2.0943951023931953 and 4 times of it is supposed to cover the entire Earth's area.

Hello,
maybe I am doing something wrong here but I notice the following:

I am querying to find out if the S2LatLng.fromDegrees(-16.8583,-72.3417).toPoint() is inside the polygon:
# # -16.8583:-72.3453,-17.2876:-72.3453,-17.2876:-71.8962,-16.8583:-71.8962,-16.8583:-72.345. From my point of view it is touching the edge so the distance is zero i.e the point is contained.

• When I run this in CPP (with the help of R), I see the expected:

  s2::s2_contains(s2::s2_geog_from_text('MULTIPOLYGON(((-72.3453 -16.4279, -72.3453 -16.8583, -71.8962 -16.8583, -71.8962 -16.4279, -72.3453 -16.4279)))') , s2::s2_geog_from_text('POINT(-72.3417 -16.8583)')) TRUE s2::s2_distance(s2::s2_geog_from_text('MULTIPOLYGON(((-72.3453 -16.4279, -72.3453 -16.8583, -71.8962 -16.8583, -71.8962 -16.4279, -72.3453 -16.4279)))') ,s2::s2_geog_from_text('POINT(-72.3417 -16.8583)'))`

  0

• In Java I get:

S2ShapeIndex index = S2TextFormat.makeIndex("# #16.8583:-72.3453,-17.2876:-72.3453,-17.2876:-71.8962,-16.8583:-71.8962,-16.8583:-72.345")
S2ContainsPointQuery query= new S2ContainsPointQuery(index);
index.contains(S2LatLng.fromDegrees(-16.8583,-72.3417).toPoint());

False //!!

Or equivalently for distance:

S2ClosestEdgeQuery.Query query = S2ClosestEdgeQuery.builder()
            .setMaxDistance(S1ChordAngle.fromDegrees(60))
            .setMaxError(S1ChordAngle.fromDegrees(0.0001))
            .setMaxResults(1)
            .build(index);

S2ClosestEdgeQuery.PointTarget<S1ChordAngle> target  =new S2ClosestEdgeQuery.PointTarget(pt);

S1ChordAngle = 3.5607445507733077E-6d instead of Zero

Any hint to what might be wrong here?

Hi,
i want to create the cell by mentioning the level.

S2Cell cell = new S2Cell(S2LatLng.fromDegrees(0.5, 14.3).toPoint());

S2CellId cellid = cell.id();

cellid.level() // its coming as 30.. is it possible to change the level to 12.

Hi,

i want to create the cell using lat and long by mentioning level. Once created, need to loop through the cell to get the nearest cell information. Please guide me for coding

Thanks.

Hi,
what is the recommended way to create an S2Polygon from a set of (connected) S2Cells?

-Matthias

I'm getting the message Bad Directed edges when trying to Union merge two polygons with correctly oriented edges, and the resulting polygon is not correct. I haven't been able to determine the exact reason it's failing, but I suspect that the edge of one of my polygons is completely obscured by the other polygon and ending up in the unused Edges array and therefore returning false from the polygon builder.

I've noticed that it also happens when trying to union two polygons that share an edge (they will correctly assemble however using the polygonbuilder directed xor options)

Is anyone able to confirm if initToUnion behaves as expected, and if it does, what are the limitations on calling this method?

Thanks
Mark

Hi folks,

I miss being part of Geo, hope you all are doing well! I was wondering if there are J2CL annotations for this library (@JsMethod/@JsType/etc), and if so would it be possible to update this library and release them?

Thank you!

Hi there,

while making myself familiar with this great library I was trying to convert an S2Cell into a WKT Polygon using its four vertices. As it turned out, the values of all four vertices are identical with any of my test cells. Here is an example:

1011111111100000000000000000000000000000000000000000000000000000
[Lo=(-1.5707963267948966, -3.141592653589793), Hi=(-0.6154797086703869, 3.141592653589793)]
V0: (-35.264389682754654, -135.0)
V1: (-35.264389682754654, -135.0)
V2: (-35.264389682754654, -135.0)
V3: (-35.264389682754654, -135.0)

This is the code I am using:

private static String toWKTPolygon(final S2Cell cell){
    String wkt = new String("POLYGON((");
    S2LatLng point;

    System.out.println(cell.toString());
    System.out.println(toBinaryString(cell.id().id()));
    System.out.println(cell.getRectBound().toString());

    // vertex order in S2LatLng is CCW, thus compliant with vertex order in WKT
    for (int i=0; i<4; i++){
        System.out.println("V" + i + ": " + cell.getVertex(i).toDegreesString());
        point = new S2LatLng(cell.getVertex(i));
        wkt = wkt.concat(point.lngDegrees() + " " + point.latDegrees() + ",");
    }

    // close the poly loop
    point = new S2LatLng(cell.getVertex(0));
    wkt = wkt.concat(point.lngDegrees() + " " + point.latDegrees() + "))");
    return wkt;
}

If this is not a bug, how would I obtain the "natural" vertices of an S2Cell?

Dear list,

I want to implement a function which could get all cellids within a circle of specific radius.
it looks like:

    public static String getLnglatradius(String position,double radius,int accuracy) {
        double lon= Double.parseDouble(position.split(",")[0]);
        double lat= Double.parseDouble(position.split(",")[1]);
        double capHeight = (2 * S2.M_PI) * (radius / 40075017);
        S2LatLng s2LatLng= S2LatLng.fromDegrees(lat, lon);
        String cellidlist = getCapCellidList(accuracy, capHeight, s2LatLng);
        return  cellidlist;
    }

 private static String getCapCellidList(int accuracy, double capHeight, S2LatLng s2LatLng) {
        String cellidlist="";
        double v = (capHeight * capHeight) / 2;
        S2Cap cap = S2Cap.fromAxisHeight(s2LatLng.toPoint(), v );
        S2RegionCoverer coverer = new S2RegionCoverer();
        coverer.setMaxLevel(accuracy);
        coverer.setMinLevel(accuracy);
        S2CellUnion covering = coverer.getCovering(cap);
        System.out.println(covering.size());

        ArrayList<S2CellId> s2CellIds = coverer.getCovering(cap).cellIds();
        for (S2CellId s2CellId : s2CellIds) {
            long id = s2CellId.id();
            if (cellidlist.length() == 0) {
                cellidlist = cellidlist + id;
            } else {
                cellidlist = cellidlist + "," + id;
            }
        }
        return cellidlist;
    }

but when I print the cellidlist on the map, it obviously loses some cells.
The following image is the result when I want to get all cellids within a circle of 5km radius, as you can see there are some cells lost around the central of the circle. (please ignore the color of the small dots)

Is there any problems in my code or is it a bug?
Thanks a lot!

Hi,
I would like to add additional attribute to the S2Polygon class since its final I can't extend it.
The only way I can think of it is by replicating the class and adding additional constructor.

Is there any better way of doing it or the recommendation for such use case?

Original issue - google/s2geometry#116

Hi,

I was looking around and I'm interested in using this library, but I noticed that the last commits were 4-5 years ago. Has there been any updates/bug fixes/etc since? The library is also using ant. I converted my fork to gradle and moved the packages appropriately to src/main/java and src/test/java, but wouldn't open a pr for that...also is there any official documentation?

Cheers!

Jay

New ant target is added to build.xml
name: "docs"
description: "Generate documentation"

Original issue reported on code.google.com by [email protected] on 20 Sep 2013 at 10:32

Attachments:

• build.xml.patch

Hi,

Any plans to add this library to a known repository (maven, jcenter, etc..?)

Thanks

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);
    }
}

I am trying to port a c++ application to Java that uses S2RegionTermIndexer class in s2-geometry c++ library. I do not see a corresponding Java implementation for this class in this repo.

In short, I am specifically trying to address the use-case addressed in section titled "Indexing for Search " & "Querying for Search" in s2-geometry quickstart here: https://s2geometry.io/devguide/cpp/quickstart.

My questions are:

• Is there a Java implementation for S2RegionTermIndexer or equivalent functionality
• Is this on the roadmap/backlog
• The c++ implementation for S2RegionTermIndexer class is under 300 loc. This looks like a fairly straight forward translation effort. Is there anything I need to know (i.e. pitfalls etc) if I try to port the c++ logic to java for my project.

Any feedback is appreciated.

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))

Can you please publish the latest version (with 2022 Q4 updates) to maven repo?

I encountered a problem where the centroid seems wrong, i.e., the centroid is outside the polygon even when the polygon itself is a convex.

The code below plots a hexagon but the centroid seems to be way off, did I do anything wrong, thanks a lot for help?

  double[] coordinates = new double[]{
            47.167511,-122.1521,
            47.167568,-122.151952,
            47.167684,-122.151952,
            47.167746,-122.1521,
            47.167691,-122.152248,
            47.16757,-122.152248,
            47.167511,-122.1521,
    };
    List<S2Point> s2Points = new ArrayList<>();
    for (int i = 0; i < coordinates.length /2; i++) {
        double lat = coordinates[2 * i];
        double lng = coordinates[2 * i + 1];
        System.out.println(lat + "," + lng + ",");
        S2LatLng s2LatLng = S2LatLng.fromDegrees(lat, lng);
        s2Points.add(s2LatLng.toPoint());
    }
    S2Loop s2Loop  = new S2Loop(s2Points);
    s2Loop.normalize();
    S2Polygon s2Polygon = new S2Polygon(s2Loop);
    S2Point s2PolygonCentroid = s2Polygon.getCentroid();
    System.out.println("Center: " + s2PolygonCentroid.toDegreesString() + " in_polygon " + s2Polygon
            .contains(s2PolygonCentroid));

Output:
Center: (47.167557150782145, -122.15163675765044) in_polygon false

Kml file:

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!

Basically, I would like to see most (if not all) of the methods available in https://github.com/googlemaps/android-maps-utils/blob/master/library/src/com/google/maps/android/SphericalUtil.java to be part of an S2LatLng so that I can, for example, add X miles to an S2LatLng at a certain heading/angle.

Hi,
we have a library in kotlin almost up to date to the original library.
https://github.com/Enovea/s2-geometry-kotlin