Feature request: simple polygon test (geodesic)

[bubenheimer]

Summary:

I need to determine whether a user-defined geodesic polygon is a simple (non-intersecting) polygon. Only simple polygons are usable by my app. Non-simple polygons would cause problems. My app lets users draw polygons to define areas on top of Google Maps.

Expected behavior:

Add a utility method such as:

boolean isSimplePolygon(java.util.List<LatLng> polygon, boolean geodesic)

Alternatively, a way to determine if two geodesic "straight" line segments intersect would get me there.

Or if someone can point me to a ready-made algorithm, great. I don't know the math to pull this off.

[barbeau]

http://geomalgorithms.com/a09-_intersect-3.html#simple_Polygon() gives a pretty good summary of well known algorithms to determine if a polygon is complex. The simplest solution is to brute force it and compare every segment to every other segment to see if any cross, but this is O(n^2) time complexity and gets ugly for large number of edges. For a relatively small number of intersections the Bentley-Ottmann Algorithm discussed above works well and has O(n log n) time complexity.

[bubenheimer]

Thanks @barbeau. Your answer made me realize that I made the problem too complicated when looking at it and that I should have just thought of it as a plain two-dimensional coordinate system; I guess the bulge in the coordinate system does not matter for determining line intersection. However, I don't see how to handle the case where a polygon crosses the line at -180 and 180 longitude. Any insights?

[barbeau]

Anytime you're handling crossing the IDL it gets tricky. Off the top of my head, the biggest item you need to determine is that, given a set of points, if the intention is to actually cross the IDL, or if it should wrap the other direction around the globe. I've seen this differentiated by labeling a set of points that are lowerLeftCorner and upperRightCorner, vs minLat/Lon and maxLat/Log - the former makes this unambiguous, while the later does not. Without looking at it I'm not sure if the prior link I referenced properly handles this or not. A lot of software I've seen just chooses not to address this case, and you get some strange performance in that situation. Last time I looked Google Earth was one of those.

[bubenheimer]

Thanks - in my use case using the shortest distance between two points would make the most sense, and that appears to match how Google Maps handles Polylines. However, your comment raises the question if whatever approach I choose would match the android-maps-utils logic for related functionality like determining whether a point is inside the polygon, which I also use. So I'll hope that someone will add consistent line intersection and simple polygon functions to the library at some point, and in the meantime I'll have to live with the fact that my app may not work well in a place like Fiji. I imagine that I could handle the IDL problem by carefully wrapping around in the line intersection algorithm, but chances are I'd just introduce a bunch of bugs, at least if I use one of the more performant algorithms.

[bubenheimer]

Really, all I need is this: Maps can fill a simple polygon with a solid color. When the polygon is not simple, it will not fill it. The only problem is that Maps does not expose whether it filled the polygon or not, so I have no idea about the actual state of the polygon. Simply exposing the information would solve the problem.

I've created a Maps feature request at https://issuetracker.google.com/issues/36838419

[caopeng000]

Does Google Maps have to provide broadcasts to monitor whether the current location is in the geo fence?

[bubenheimer]

A polygonal geofence broadcast would be useful to receive from Location Services and Awareness APIs. In my current architecture I process location information in a foreground service regardless of whether a map is currently displayed, and determine geofence state via PolyUtil.containsLocation(). Location Services and Awareness APIs currently support circular regions for geofences - I would need polygonal regions.

[stale[bot]]

This issue has been automatically marked as stale because it has not had recent activity. Please comment here if it is still valid so that we can reprioritize. Thank you!

[bubenheimer]

I am still very much interested in this feature. Thanks.

[ram-wavity]

Hey, is there any polygon support in the latest Geofence APIs?

[stale[bot]]

This issue has been automatically marked as stale because it has not had recent activity. Please comment here if it is still valid so that we can reprioritize. Thank you!

[bubenheimer]

Not stale, still looking for API from Google Maps team. Thanks.

[sonth-bhsoft]

I've searched for a week but still find no solution for this issue.

[stale[bot]]

This issue has been automatically marked as stale because it has not had recent activity. Please comment here if it is still valid so that we can reprioritize. Thank you!

[bubenheimer]

Still interested in public API to address this issue. Thanks.

[stale[bot]]

This issue has been automatically marked as stale because it has not had recent activity. Please comment here if it is still valid so that we can reprioritize. Thank you!

[bubenheimer]

Still interested in public API to address this issue. Thanks.

[stale[bot]]

Closing this. Please reopen if you believe it should be addressed. Thank you for your contribution.

[bubenheimer]

Still interested in public API to address this issue. Thanks.