Point in polygon algortim using location class in android?

Question

I've a a set of location that forms a closed path (similar to polygon). Is there any possible way to check if a certain latitude and longitude is inside the closed path?

Answer 1

You need a ray-casting algorithm. Good for you that someone already did this: ;-)

Point in Polygon Algorithm

And for a little background knowledge:

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

Answer 2

If there is no restriction on corner cases, you can add the list of locations to a LatLngBounds and then use bounds.contains(lat,lng).

LatLngBounds.Builder builder = new LatLngBounds.Builder();
builder.include(new LatLng (52.39455,13.73096));
builder.include(new LatLng (52.39650,13.71644));   
builder.include(new LatLng (52.38719,13.69940));
LatLngBounds bound = builder.build();

if (bounds.contains(lat,lng)
// your code goes here

Note: This will not work if you want to ensure exactly if the point is within the polygon because the LatLngBounds will be a box enclosing the polygon formed by your list of locations.

Answer 3

Better Way,

 ArrayList<LatLng> polyLoc = new ArrayList<LatLng>();

    public boolean Contains(LatLng location)
        {
            if (location==null)
                return false;

            LatLng lastPoint = polyLoc.get(polyLoc.size()-1);
            boolean isInside = false;
            double x = location.longitude;

            for(LatLng point: polyLoc)
            {
                double x1 = lastPoint.longitude;
                double x2 = point.longitude;
                double dx = x2 - x1;

                if (Math.abs(dx) > 180.0)
                {
                    // we have, most likely, just jumped the dateline (could do further validation to this effect if needed).  normalise the numbers.
                    if (x > 0)
                    {
                        while (x1 < 0)
                            x1 += 360;
                        while (x2 < 0)
                            x2 += 360;
                    }
                    else
                    {
                        while (x1 > 0)
                            x1 -= 360;
                        while (x2 > 0)
                            x2 -= 360;
                    }
                    dx = x2 - x1;
                }

                if ((x1 <= x && x2 > x) || (x1 >= x && x2 < x))
                {
                    double grad = (point.latitude - lastPoint.latitude) / dx;
                    double intersectAtLat = lastPoint.latitude + ((x - x1) * grad);

                    if (intersectAtLat > location.latitude)
                        isInside = !isInside;
                }
                lastPoint = point;
            }

            return isInside;
        }

Refer the below link for actual post, Checking if a longitude/latitude coordinate resides inside a complex polygon in an embedded device?

Answer 4

By using ray casting algoritham.Below is java code to do that

public  boolean CheckPointInPolyGon(LocObj locObj,ArrayList<LocObj> ArraylocObjs){
int polyCorners=ArraylocObjs.size()-1;
    int j=polyCorners-1;
    boolean isPointInPolygon=false;


    for (int i=0; i<polyCorners; i++) 
      {   
          if ((ArraylocObjs.get(i).lng< locObj.lng && ArraylocObjs.get(j).lng>=locObj.lng   
                  ||   ArraylocObjs.get(j).lng< locObj.lng && ArraylocObjs.get(i).lng>=locObj.lng)      
                  &&  (ArraylocObjs.get(i).lat<=locObj.lat || ArraylocObjs.get(j).lat<=locObj.lat)) 
          {
              if (ArraylocObjs.get(i).lat+(locObj.lng-ArraylocObjs.get(i).lng)/(ArraylocObjs.get(j).lng-ArraylocObjs.get(i).lng)
                      *(ArraylocObjs.get(j).lat-ArraylocObjs.get(i).lat)<locObj.lat) 
              {
                isPointInPolygon=!isPointInPolygon; 
              }
          }
          j=i; 
      } 


return isPointInPolygon;}

And in my case i have created one POJO class for storing this Location Point in case if you want you can use "LatLng" class to store points

public class LocObj{Double lat,lng; 
public LocObj(){}   
LocObj(Double lat,Double lng){
    this.lat=lat;
    this.lng=lng;
    }}