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)

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.

Bragdon

did you use geofence here ? – Abolish

Nope. I just drew that polygon using PolygonOptions. Searching for a best way to identify whether current location is in that polygon. – Bragdon

You can use Geofence for this. developer.android.com/training/location/geofencing.html – Abolish

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. – Bragdon

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. – Abolish

Try this github.com/sromku/polygon-contains-point – Sciolism

Answer 1

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

Bragdon

your algorithm always return false , why? – Gagne

@Bragdon Working good. Thanks for this. If possible I request you to explain how the intersect is working. – Bronze

this implementation will not work if m = (aY - bY) / (aX - bX) = 0 – Jonna

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. – Dismast

Answer 2

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.

Indelible

why last parameter false? what is that parameter? – Gerlac

I've added the description of the method, as I found it in their source code – Indelible

Thanks! Awesome answer! – Gerlac

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. – Jackdaw

Answer 3

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

Pollen

trying this. Thanks :) – Bragdon

Worked for my few tests. Checking its thesis. :) Thanks – Bragdon

Answer 4

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

Caudex