Identify if point is in the polygon

Question

As per my requirement, I am drawing polygons on google map shown in the image below.(using maps v2) enter image description here

Now I need to show an alert when user enters that particular polygons.

How to identify if my current location is with in the polygon. (Need optimized way without draining battery)

Thanks in advance.

Nope. I just drew that polygon using PolygonOptions. Searching for a best way to identify whether current location is in that polygon. — Supriya, Sep 24 '14 at 10:28
You can use Geofence for this. http://developer.android.com/training/location/geofencing.html — Ranjit, Sep 24 '14 at 10:30
I think Geofence is if we can have a location and give a particular radius, it will alert if user enters in to the location. In my case, am drawing a polygon using multiple locations. — Supriya, Sep 24 '14 at 10:34
When you give a radious to a location, geofence stores each point inside the area surrounded by the radious..your question is some related to this..you can draw poligon instead of circle in geofence. — Ranjit, Sep 24 '14 at 10:39

score 34 · Accepted Answer · answered Sep 25 '14 at 04:54

Just tried Ray Casting algorithm which identifies point in polygon. This works perfect.

Refer http://en.wikipedia.org/wiki/Point_in_polygon for thesis of Ray-Casting

private boolean isPointInPolygon(LatLng tap, ArrayList<LatLng> vertices) {
        int intersectCount = 0;
        for (int j = 0; j < vertices.size() - 1; j++) {
            if (rayCastIntersect(tap, vertices.get(j), vertices.get(j + 1))) {
                intersectCount++;
            }
        }

        return ((intersectCount % 2) == 1); // odd = inside, even = outside;
    }

    private boolean rayCastIntersect(LatLng tap, LatLng vertA, LatLng vertB) {

        double aY = vertA.latitude;
        double bY = vertB.latitude;
        double aX = vertA.longitude;
        double bX = vertB.longitude;
        double pY = tap.latitude;
        double pX = tap.longitude;

        if ((aY > pY && bY > pY) || (aY < pY && bY < pY)
                || (aX < pX && bX < pX)) {
            return false; // a and b can't both be above or below pt.y, and a or
                            // b must be east of pt.x
        }

        double m = (aY - bY) / (aX - bX); // Rise over run
        double bee = (-aX) * m + aY; // y = mx + b
        double x = (pY - bee) / m; // algebra is neat!

        return x > pX;
    }

@Supriya Working good. Thanks for this. If possible I request you to explain how the intersect is working. — Arnold Brown, Jan 11 '19 at 12:11
this implementation will not work if m = (aY - bY) / (aX - bX) = 0 — user1581432, Aug 03 '22 at 13:49
dear Supriya, This will work only if the user's Current Location coordinates have complete match with any one of the coordinates of Polygone. If It's slightly different, It will not work. Let me know If I am wrong. — Jaimin Modi, Nov 05 '22 at 10:53

DoruChidean · Answer 2 · 2017-09-20T08:24:22.080

24

I found ray-casting method unreliable but I ended up using the PolyUtil from google maps.

You need the dependency compile 'com.google.maps.android:android-maps-utils:0.5'

And then the method looks like this

PolyUtil.containsLocation(userLocation, polyPointsList, false);

EDIT

This is the description of this method found in source code

Computes whether the given point lies inside the specified polygon. The polygon is always considered closed, regardless of whether the last point equals the first or not. Inside is defined as not containing the South Pole -- the South Pole is always outside. The polygon is formed of great circle segments if geodesic is true, and of rhumb (loxodromic) segments otherwise.

edited Sep 20 '17 at 08:24

answered Mar 29 '17 at 14:37

DoruChidean

7,941
1
29
33

1

why last parameter false? what is that parameter? – Virat18 Sep 20 '17 at 07:53
I've added the description of the method, as I found it in their source code – DoruChidean Sep 20 '17 at 08:24
Thanks! Awesome answer! – Virat18 Sep 20 '17 at 09:57
Both of these worked consistently. I added them both and put the map touch listener as the evocation. No issues. But this is clearly the cleaner implementation. – StarWind0 Jan 17 '18 at 04:41

score 2 · Answer 3 · edited May 23 '17 at 12:02

2

Refer this link

Polygon Touch detection Google Map API V2

Its RayCasting algorithm, it may help you :)

A brief description about the algorithm:

A horizontal line is drawn from your point to the right, if it intersects the sides of polygon at odd number of times then the point is inside the polygon else outside :)

These wiki links will give you complete idea:

http://en.wikipedia.org/wiki/Point_in_polygon

http://rosettacode.org/wiki/Ray-casting_algorithm

edited May 23 '17 at 12:02

Community

1
1

answered Sep 24 '14 at 11:08

Revathi

172
8

trying this. Thanks :) – Supriya Sep 24 '14 at 11:14
Worked for my few tests. Checking its thesis. :) Thanks – Supriya Sep 24 '14 at 11:33

score 0 · Answer 4 · answered May 15 '21 at 10:04

Here is the code in Dart, taken from: https://github.com/KohlsAdrian/google_maps_utils/blob/master/lib/poly_utils.dart

  /// Checks if [point] is inside [polygon]
  static bool containsLocationPoly(Point point, List<Point> polygon) {
    num ax = 0;
    num ay = 0;
    num bx = polygon[polygon.length - 1].x - point.x;
    num by = polygon[polygon.length - 1].y - point.y;
    int depth = 0;

    for (int i = 0; i < polygon.length; i++) {
      ax = bx;
      ay = by;
      bx = polygon[i].x - point.x;
      by = polygon[i].y - point.y;

      if (ay < 0 && by < 0) continue; // both "up" or both "down"
      if (ay > 0 && by > 0) continue; // both "up" or both "down"
      if (ax < 0 && bx < 0) continue; // both points on left

      num lx = ax - ay * (bx - ax) / (by - ay);

      if (lx == 0) return true; // point on edge
      if (lx > 0) depth++;
    }

    return (depth & 1) == 1;
  }

Identify if point is in the polygon

4 Answers4

Linked

Related