Polygon Point Containment from Lat/Lon

[Todd Lehn]

Greetings,

I am attempting to use the golang geo library to add a geofence capability to a go service. The concept is to know when a person, based on their GPS coordinates, has entered or exited a geofenced area. I have introduced the s2.Point primitive into a planar algorithm via s2.PointFromLatLng where the s2.LatLng is created from a Coordinate value comprised of latitude and longitude values represented as decimal degrees. This planar algorithm works as expected according to unit tests of a predefined geofence and points known to be inclusive or exclusive.

Wanting to utilize a robust, maintained library over my simplistic algorithm, I had a naive assumption that I could convert the ordered list of coordinate values to points, construct an s2.Loop from the ordered (CCW) list of points and determine the point containment from calling s2.Loop.ContainsPoint. However, the unit tests that pass with the planar algorithm are failing. Attempting to decompose the problem down to a manageable size, I ran some tests by constructing a simple bounding box in the Cartesian coordinate system and points that would fall within the bounding box (inclusive) on a flat plane. The tests reveal that s2.Loop.ContainsPoint returns false when the point lies on a vertex or line segment.

I'm obviously struggling with spherical geometry concepts and primitives and am looking for some guidance on being able to leverage this library go implement the geofence capability. I'm eager to learn about a topic I am unfamiliar with and am open to any and all guidance.

Many thanks,

Todd

// Coordinate defines a location comprised of latitude and longitude values

// expressed as decimal degrees.

type Coordinate struct {

    Lat float64 `json:"latitude"`

    Lon float64 `json:"longitude"`

}

// init initializes the polygon's point vector which is used in the calculation

// of the polygon point containment problem and the polygon (a.k.a loop)

// validation check.

func (poly *Polygon) init() {

    poly.points = make(s2.PointVector, len(poly.Coordinates))

    for i, c := range poly.Coordinates {

        ll := s2.LatLngFromDegrees(c.Lat, c.Lon)

        point := s2.PointFromLatLng(ll)

        poly.points[i] = point

    }

}

// Contains returns true if the coordinate is contained within the boundary and

// false if the coordinate is not within the boundary.

func (poly *Polygon) Contains(c Coordinate) bool {

    if poly.points == nil {

        poly.init()

    }

    ll := s2.LatLngFromDegrees(c.Lat, c.Lon)

    p := s2.PointFromLatLng(ll)

    loop := s2.LoopFromPoints(poly.points)

    return loop.ContainsPoint(p)

}

[Eric Engle]

The S2 library uses what you might call a half open containment model. So when your query point is on a vertex, about half of the time it will say that point is contained, and the other half of the time it is not contained.

That is, the S2Loop.contains(S2Point) operation has no notion of "on the boundary"; points are always judged to be inside or outside, regardless of whether they are far from the boundary, or right on top of it.

This should cause no problem for a geofence use case, since the transition from inside to outside or vice-versa is what you're looking for.

If you wanted to test whether a point is "moving along the fence" then you would need to bring your own notion of what that means. E.g. always within 10 meters of the fence, or something like that. Which isn't the same as a contains point test.

Let me know if that clears anything up for you, and by all means if you have any other questions just ask.

- Eric

--
You received this message because you are subscribed to the Google Groups "s2geometry-io" group.
To unsubscribe from this group and stop receiving emails from it, send an email to s2geometry-i...@googlegroups.com.
To post to this group, send email to s2geom...@googlegroups.com.
Visit this group at https://groups.google.com/group/s2geometry-io.
To view this discussion on the web visit https://groups.google.com/d/msgid/s2geometry-io/360ec108-e5ad-429f-8006-8217313112a4%40googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

[Todd Lehn]

Eric,

Thank you for the reply and information. The "on the vertex or boundary" makes sense. I'm still not able to verify or reason about if the s2.Point and s2.Loop primitives can be used to provide the geofence functionality. I have a few unit units and they all fail using the s2.Loop.ContainsPoint for an s2.Loop that is constructed from points that outline the top of my office building. The same tests pass when they are run against a flat geometry algorithm. This makes me wonder if I'm using the primitives incorrectly, choosing the wrong primitives or my validation approach is incorrect. Given the small area of an office roof, I reasoned the surface would be relatively flat, thus the spherical and flat algorithms would return the same results.

Do points need to be in a counter-clockwise orientation when creating a loop? My current tests are ordered CCW but I'm thinking a step ahead for functional tests should I get to that stage. 

Many Thanks,

Todd

[Eric Engle]

The inside area of a loop is on the left when walking the vertices. So given roof corners designated N or S for north or south and E or W for east or west, you should include the corners in for example the order SW, SE, NE, NW. The other orientation will result in the complement of the region you want.

Best,

Eric

To view this discussion on the web visit https://groups.google.com/d/msgid/s2geometry-io/a4bfba24-3a0f-4b89-92f9-336c34d90ba0%40googlegroups.com.