c++geometrys2

Google S2 Geometry: polygon contains check does not work as expected


I'm using the Google S2 Geometry library to check whether a given geo point is within a polygon.

The following assertion should pass, but is failing and I'm unable to explain what's going wrong:

    std::vector<S2Point> vertices = {
            S2LatLng::FromDegrees(60, -118).ToPoint(),
            S2LatLng::FromDegrees(23, -118).ToPoint(),
            S2LatLng::FromDegrees(23, 34).ToPoint(),
            S2LatLng::FromDegrees(60, 34).ToPoint(),
    };

    auto loop = new S2Loop(vertices, S2Debug::DISABLE);
    S2Point p = S2LatLng::FromDegrees(42.716450, -67.079284).ToPoint();
    ASSERT_TRUE(loop->Contains(p));

The point is certainly within the polygon indicated by the vertices but S2 says that the point is not inside.


Solution

  • S2 uses geodesic edges, so the loop is not just a rectangle on a flat map, but the "horizontal" edges are curved towards the poles following the shortest path on spherical Earth. For small distances, the difference from planar maps are negligible, but for huge distances like here the shortest path is quite different.

    The loop and the point can be seen on the picture below, and the loop does not contain the point:

    loop and point

    BTW, to visualize the loop and the point on this picture, I used Google's BigQuery GeoViz tool (you need to setup BigQuery account, free tier should be enough). It might be a good debugging tool for S2. You can read more about it here: https://cloud.google.com/bigquery/docs/geospatial-visualize#geo_viz. I used the following query (in SQL the order of coordinates is longitute-latitude):

    select st_geogfromtext('polygon((-118 60, -118 23, 34 23, 34 60, -118 60))') p
    union all
    select st_geogpoint(-67.079284, 42.716450);