0

I have searched for lot of threads but still I am facing the issue. I have to find out if a lat/lng is inside or outside the polygon. I have used following method:

private boolean LineIntersect(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; }
       double m = (aY-bY) / (aX-bX);               
        double bee = (-aX) * m + aY;                // y = mx + b
        double x = (pY - bee) / m;                 
        return x > pX;


    }

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


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

}

I am calling it as:

          if(isPointInPolygon(mLatLng, points))
              {
                  Toast.makeText(getApplicationContext(), "inside", 
                           Toast.LENGTH_LONG).show();
              }
              else
              {
                  Toast.makeText(getApplicationContext(), "outside", 
                           Toast.LENGTH_LONG).show();
              }

The problem I am getting is, when I am inside the geofence I am getting both true and false. WHenever I am inside the geofence I am getting 2 toasts inside and outside both. Please let me know where I am wrong.

Neharika
  • 95
  • 11
  • Don't know the geolocation but two ideas: 1st, near the "edge", successive points may "wobble" between inside/outside; 2nd, do the positions ever give "spurious" values? Either an "I don't know where I am" value (e.g. 0,0), or perhaps occasionally only coarse positioning is available and this is outside the polygon. Try tracing the positions, particularly after having seen an "inside" one and look for rogue values. If there are some, and you can't obviously filter them out, maybe once you've seen an "inside" point, require three consecutive "outside" points before announcing the fact. – TripeHound Apr 16 '14 at 08:28
  • Maybe you could check this: [Point in polygon algorithm][1] [1]: http://stackoverflow.com/questions/11716268/point-in-polygon-algorithm – Daniele P. Apr 16 '14 at 08:29

1 Answers1

1

I have created geofence app that successfully worked here is the code i used this https://github.com/sromku/polygon-contains-point to figure out our location inside or outside of polygon. here is the code

    public class MainActivity extends Activity {

        private double Longitude, Latitude;
        private LocationListener locListener;
        private LocationManager lm;
        private ProgressDialog gpsProgressDialog;
        private Button button_gps;

        @Override
        protected void onCreate(Bundle savedInstanceState) {
            super.onCreate(savedInstanceState);
            setContentView(R.layout.activity_main);
            button_gps = (Button)findViewById(R.id.button_gps);
             lm = (LocationManager) MainActivity.this.getSystemService(MainActivity.this.LOCATION_SERVICE);
            button_gps.setOnClickListener(new OnClickListener() {

                @Override
                public void onClick(View arg0) {
                    // TODO Auto-generated method stub
                    getLoction();
                //  testSimplePolygon();

            //      testPolygonWithHoles();


                }
            });
        }

        class GpsLogation implements LocationListener {

            @Override
            public void onLocationChanged(Location location) {
                if (location != null) {
                    lm.removeUpdates(locListener);
                    Longitude = location.getLongitude();
                    Latitude = location.getLatitude();
                /*  Toast.makeText(MainActivity.this,
                            "Longitude :" + Longitude + " Latitude :" + Latitude,
                            Toast.LENGTH_LONG).show();*/

                    Polygon polygon = Polygon.Builder()
                            .addVertex(new Point(6.048857f, 80.211021f)) // change polygon  according to your location
                            .addVertex(new Point(6.048137f, 80.210546f))
                            .addVertex(new Point(6.048590f, 80.210197f))
                            .addVertex(new Point(6.049163f, 80.211050f)).build();


                //  isInside(polygon, new Point((float)Latitude, (float)Longitude));

                if( polygon.contains(new Point((float)Latitude, (float)Longitude))==true)
                {
                    Toast.makeText(MainActivity.this, "You are inside", Toast.LENGTH_LONG).show();
                }
                else
                {
                    Toast.makeText(MainActivity.this, "You are outside", Toast.LENGTH_LONG).show();

                }


                    // /////////////do something//////////////
                    // insertSalesOrder();



                    Log.i("TTTAG", "Latitude:" + Latitude);
                    Log.i("TTTAG", "Longitude:" + Longitude);

                    if (gpsProgressDialog.isShowing()) {
                        gpsProgressDialog.dismiss();
                    }

                }

            }

            @Override
            public void onProviderDisabled(String arg0) {
                // TODO Auto-generated method stub

            }

            @Override
            public void onProviderEnabled(String arg0) {
                // TODO Auto-generated method stub

            }

            @Override
            public void onStatusChanged(String arg0, int arg1, Bundle arg2) {
                // TODO Auto-generated method stub
            }

        }

        public void getLoction() {
            locListener = new GpsLogation();
            boolean enabled = lm.isProviderEnabled(LocationManager.GPS_PROVIDER);
            if (!enabled) {
                Toast.makeText(MainActivity.this, "Please switch on the GPS",Toast.LENGTH_LONG).show();
                Intent intent = new Intent(Settings.ACTION_LOCATION_SOURCE_SETTINGS);
                MainActivity.this.startActivity(intent);
                return;
            }
            Log.i("GPS INFO", " OK Gps Is ON");
            gpsProgressDialog = ProgressDialog.show(MainActivity.this, "", "Please wait ... ", true);
            lm.requestLocationUpdates(LocationManager.GPS_PROVIDER, 0, 0,locListener);
        }


//    Here is the polygon java class and i'm not author of it

public class Polygon
{
    private final BoundingBox _boundingBox;
    private final List<Line> _sides;

    private Polygon(List<Line> sides, BoundingBox boundingBox)
    {
        _sides = sides;
        _boundingBox = boundingBox;
    }

    /**
     * Get the builder of the polygon
     * 
     * @return The builder
     */
    public static Builder Builder()
    {
        return new Builder();
    }

    /**
     * Builder of the polygon
     * 
     * @author Roman Kushnarenko (sromku@gmail.com)
     */
    public static class Builder
    {
        private List<Point> _vertexes = new ArrayList<Point>();
        private List<Line> _sides = new ArrayList<Line>();
        private BoundingBox _boundingBox = null;

        private boolean _firstPoint = true;
        private boolean _isClosed = false;

        /**
         * Add vertex points of the polygon.<br>
         * It is very important to add the vertexes by order, like you were drawing them one by one.
         * 
         * @param point
         *            The vertex point
         * @return The builder
         */
        public Builder addVertex(Point point)
        {
            if (_isClosed)
            {
                // each hole we start with the new array of vertex points
                _vertexes = new ArrayList<Point>();
                _isClosed = false;
            }

            updateBoundingBox(point);
            _vertexes.add(point);

            // add line (edge) to the polygon
            if (_vertexes.size() > 1)
            {
                Line Line = new Line(_vertexes.get(_vertexes.size() - 2), point);
                _sides.add(Line);
            }

            return this;
        }

        /**
         * Close the polygon shape. This will create a new side (edge) from the <b>last</b> vertex point to the <b>first</b> vertex point.
         * 
         * @return The builder
         */
        public Builder close()
        {
            validate();

            // add last Line
            _sides.add(new Line(_vertexes.get(_vertexes.size() - 1), _vertexes.get(0)));
            _isClosed = true;

            return this;
        }

        /**
         * Build the instance of the polygon shape.
         * 
         * @return The polygon
         */
        public Polygon build()
        {
            validate();

            // in case you forgot to close
            if (!_isClosed)
            {
                // add last Line
                _sides.add(new Line(_vertexes.get(_vertexes.size() - 1), _vertexes.get(0)));
            }

            Polygon polygon = new Polygon(_sides, _boundingBox);
            return polygon;
        }

        /**
         * Update bounding box with a new point.<br>
         * 
         * @param point
         *            New point
         */
        private void updateBoundingBox(Point point)
        {
            if (_firstPoint)
            {
                _boundingBox = new BoundingBox();
                _boundingBox.xMax = point.x;
                _boundingBox.xMin = point.x;
                _boundingBox.yMax = point.y;
                _boundingBox.yMin = point.y;

                _firstPoint = false;
            }
            else
            {
                // set bounding box
                if (point.x > _boundingBox.xMax)
                {
                    _boundingBox.xMax = point.x;
                }
                else if (point.x < _boundingBox.xMin)
                {
                    _boundingBox.xMin = point.x;
                }
                if (point.y > _boundingBox.yMax)
                {
                    _boundingBox.yMax = point.y;
                }
                else if (point.y < _boundingBox.yMin)
                {
                    _boundingBox.yMin = point.y;
                }
            }
        }

        private void validate()
        {
            if (_vertexes.size() < 3)
            {
                throw new RuntimeException("Polygon must have at least 3 points");
            }
        }
    }

    /**
     * Check if the the given point is inside of the polygon.<br>
     * 
     * @param point
     *            The point to check
     * @return <code>True</code> if the point is inside the polygon, otherwise return <code>False</code>
     */
    public boolean contains(Point point)
    {
        if (inBoundingBox(point))
        {
            Line ray = createRay(point);
            int intersection = 0;
            for (Line side : _sides)
            {
                if (intersect(ray, side))
                {
                    // System.out.println("intersection++");
                    intersection++;
                }
            }

            /*
             * If the number of intersections is odd, then the point is inside the polygon
             */
            if (intersection % 2 == 1)
            {
                return true;
            }
        }
        return false;
    }

    public List<Line> getSides()
    {
        return _sides;
    }

    /**
     * By given ray and one side of the polygon, check if both lines intersect.
     * 
     * @param ray
     * @param side
     * @return <code>True</code> if both lines intersect, otherwise return <code>False</code>
     */
    private boolean intersect(Line ray, Line side)
    {
        Point intersectPoint = null;

        // if both vectors aren't from the kind of x=1 lines then go into
        if (!ray.isVertical() && !side.isVertical())
        {
            // check if both vectors are parallel. If they are parallel then no intersection point will exist
            if (ray.getA() - side.getA() == 0)
            {
                return false;
            }

            float x = ((side.getB() - ray.getB()) / (ray.getA() - side.getA())); // x = (b2-b1)/(a1-a2)
            float y = side.getA() * x + side.getB(); // y = a2*x+b2
            intersectPoint = new Point(x, y);
        }

        else if (ray.isVertical() && !side.isVertical())
        {
            float x = ray.getStart().x;
            float y = side.getA() * x + side.getB();
            intersectPoint = new Point(x, y);
        }

        else if (!ray.isVertical() && side.isVertical())
        {
            float x = side.getStart().x;
            float y = ray.getA() * x + ray.getB();
            intersectPoint = new Point(x, y);
        }

        else
        {
            return false;
        }

        // System.out.println("Ray: " + ray.toString() + " ,Side: " + side);
        // System.out.println("Intersect point: " + intersectPoint.toString());

        if (side.isInside(intersectPoint) && ray.isInside(intersectPoint))
        {
            return true;
        }

        return false;
    }

    /**
     * Create a ray. The ray will be created by given point and on point outside of the polygon.<br>
     * The outside point is calculated automatically.
     * 
     * @param point
     * @return
     */
    private Line createRay(Point point)
    {
        // create outside point
        float epsilon = (_boundingBox.xMax - _boundingBox.xMin) / 100f;
        Point outsidePoint = new Point(_boundingBox.xMin - epsilon, _boundingBox.yMin);

        Line vector = new Line(outsidePoint, point);
        return vector;
    }

    /**
     * Check if the given point is in bounding box
     * 
     * @param point
     * @return <code>True</code> if the point in bounding box, otherwise return <code>False</code>
     */
    private boolean inBoundingBox(Point point)
    {
        if (point.x < _boundingBox.xMin || point.x > _boundingBox.xMax || point.y < _boundingBox.yMin || point.y > _boundingBox.yMax)
        {
            return false;
        }
        return true;
    }

    private static class BoundingBox
    {
        public float xMax = Float.NEGATIVE_INFINITY;
        public float xMin = Float.NEGATIVE_INFINITY;
        public float yMax = Float.NEGATIVE_INFINITY;
        public float yMin = Float.NEGATIVE_INFINITY;
    }
}

////    Here is the Line java class and i'm not author of it

public class Line
{
    private final Point _start;
    private final Point _end;
    private float _a = Float.NaN;
    private float _b = Float.NaN;
    private boolean _vertical = false;

    public Line(Point start, Point end)
    {
        _start = start;
        _end = end;

        if (_end.x - _start.x != 0)
        {
            _a = ((_end.y - _start.y) / (_end.x - _start.x));
            _b = _start.y - _a * _start.x;
        }

        else
        {
            _vertical = true;
        }
    }

    /**
     * Indicate whereas the point lays on the line.
     * 
     * @param point
     *            - The point to check
     * @return <code>True</code> if the point lays on the line, otherwise return <code>False</code>
     */
    public boolean isInside(Point point)
    {
        float maxX = _start.x > _end.x ? _start.x : _end.x;
        float minX = _start.x < _end.x ? _start.x : _end.x;
        float maxY = _start.y > _end.y ? _start.y : _end.y;
        float minY = _start.y < _end.y ? _start.y : _end.y;

        if ((point.x >= minX && point.x <= maxX) && (point.y >= minY && point.y <= maxY))
        {
            return true;
        }
        return false;
    }

    /**
     * Indicate whereas the line is vertical. <br>
     * For example, line like x=1 is vertical, in other words parallel to axis Y. <br>
     * In this case the A is (+/-)infinite.
     * 
     * @return <code>True</code> if the line is vertical, otherwise return <code>False</code>
     */
    public boolean isVertical()
    {
        return _vertical;
    }

    /**
     * y = <b>A</b>x + B
     * 
     * @return The <b>A</b>
     */
    public float getA()
    {
        return _a;
    }

    /**
     * y = Ax + <b>B</b>
     * 
     * @return The <b>B</b>
     */
    public float getB()
    {
        return _b;
    }

    /**
     * Get start point
     * 
     * @return The start point
     */
    public Point getStart()
    {
        return _start;
    }

    /**
     * Get end point
     * 
     * @return The end point
     */
    public Point getEnd()
    {
        return _end;
    }

    @Override
    public String toString()
    {
        return String.format("%s-%s", _start.toString(), _end.toString());
    }
}


////    Here is the point java class and i'm not author of it


public class Point
{
    public Point(float x, float y)
    {
        this.x = x;
        this.y = y;
    }

    public float x;
    public float y;

    @Override
    public String toString()
    {
        return String.format("(%.2f,%.2f)", x, y);
    }
}

/*I coded only Mainactivity class other owner of other classes is https://github.com/sromku and all credit goes to him*/
Lahiru Prasanna
  • 1,012
  • 2
  • 15
  • 32