google / s2geometry

Computational geometry and spatial indexing on the sphere
http://s2geometry.io/
Apache License 2.0
2.29k stars 302 forks source link

Unexpected S2Loop contains check failure #262

Closed kishorenc closed 2 years ago

kishorenc commented 2 years ago

I'm checking whether a given geo point is within a large polygon. The following assertion should pass, but is failing:

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

I'm not able to figure out what's going wrong, because I have other examples where this is working in an expected fashion.

jmr commented 2 years ago

Your vertices look like they're counterclockwise, so that's good. That's the most common cause of these "Contains is broken" bug reports.

What makes you think this point should be contained in this loop?

Edges in S2 are geodesics. The top and bottom edges start and end at the same latitude, but span 152 degrees, so they're going to go quite far north.

http://www.gcmap.com/mapui?P=60N+118W+-+60N+34E,+23N+118W+-+23N+34E,+42.716450N+W67.079284

From this it looks like the point isn't in the loop.

kishorenc commented 2 years ago

@jmr

Thank you for your prompt response. I was actually plotting these points on Google maps to verify but it looks very different on Google Maps: is that because Google Maps does not represent points as they look on a spherical surface?

Screenshot 2022-07-10 at 7 38 54 AM
jmr commented 2 years ago

The points are in the right place. It's just that the geodesic (shortest path) connecting them is not a straight line on this projection (Mercator). If you drew the lines with geodesic: true in the maps API, you would also see them going far north.

https://developers.google.com/maps/documentation/javascript/geometry#SphericalGeometry

If you actually want to just compare lat/lng, use S2LatLngRect.