Find the closest point on polygon to user location

Question

I have an app that find the shortest distance between my user to a polygon.

I want to convert the polygon to Geofence to check the distance between the user to the area to give mor accurate information to the user.

how can I do that?

this is the MapsActivity

public class MapsActivity extends FragmentActivity implements OnMapReadyCallback, LocationListener, MinimumDistanceTask.GetMinimumDistanceListener {
    private GoogleMap mMap;
    private  LocationManager manager;
    private double lat, lng;
    private KmlLayer layer;
    private LatLng latLngTest;
    private  boolean contains = false;
    private  ArrayList<LatLng> outerBoundary;

    @Override
    protected void onCreate(Bundle savedInstanceState) {
        super.onCreate(savedInstanceState);
        setContentView(R.layout.activity_maps);
        // Obtain the SupportMapFragment and get notified when the map is ready to be used.
        SupportMapFragment mapFragment = (SupportMapFragment) getSupportFragmentManager()
                .findFragmentById(R.id.map);
        mapFragment.getMapAsync(this);
        manager = (LocationManager) getSystemService(LOCATION_SERVICE);
    }

    @Override
    protected void onResume() {
        super.onResume();
        String provider = LocationManager.GPS_PROVIDER;

        //take the user location every second
        try {
            manager.requestLocationUpdates(provider, 1000, 0, this);
        }catch (SecurityException e){

        }
    }

    @Override
    public void onMapReady(GoogleMap googleMap) {
        mMap = googleMap;
    }

    @Override
    public void onLocationChanged(Location location) {
        //clear map before create new location
        mMap.clear();
        try {
            //load the kml file
            layer = new KmlLayer(mMap, R.raw.polygon_layer, this);
            layer.addLayerToMap();

        } catch (IOException e) {
            e.printStackTrace();
        } catch (XmlPullParserException e) {
            e.printStackTrace();
        }

        lat = location.getLatitude();
        lng = location.getLongitude();
        latLngTest = new LatLng(lat,lng);
        // Add a marker in user location
        LatLng userLocation = new LatLng(latLngTest.latitude, latLngTest.longitude);
        mMap.addMarker(new MarkerOptions().position(userLocation).title("you are here"));
        mMap.animateCamera(CameraUpdateFactory.newLatLngZoom(userLocation, 15));

        //check if the user in the polygon
        boolean inside = ifUserInside();

        if(inside){
            Toast.makeText(MapsActivity.this, "you are in the polygon", Toast.LENGTH_SHORT).show();
        }else{
            Toast.makeText(MapsActivity.this, "you are outside the polygon", Toast.LENGTH_SHORT).show();
            //create the string address for the url
            String address = "";
            for (int i = 0; i < outerBoundary.size(); i++) {
                address += (outerBoundary.get(i).toString() + "|");
                address = address.replace("lat/lng:", "");
                address = address.replace(" ", "");
                address = address.replace("(", "");
                address = address.replace(")", "");
            }
            MinimumDistanceTask task = new MinimumDistanceTask(this);
            task.execute("https://maps.googleapis.com/maps/api/distancematrix/json?units=imperial&origins="+latLngTest.latitude+ "," + latLngTest.longitude
                    + "&destinations=" + address + "&mode=walking");
        }

    }

    @Override
    public void getMinimumDistance(int closeLocation) {
        //check if you get results properly
        if(closeLocation != -1) {
            GetDirection direction = new GetDirection();
            direction.execute("https://maps.googleapis.com/maps/api/directions/json?origin=" + latLngTest.latitude + "," + latLngTest.longitude
                    + "&destination=" + outerBoundary.get(closeLocation).latitude + "+" + outerBoundary.get(closeLocation).longitude);
        }
    }

    @Override
    public void onStatusChanged(String provider, int status, Bundle extras) {

    }

    @Override
    public void onProviderEnabled(String provider) {

    }

    @Override
    public void onProviderDisabled(String provider) {

    }

    public boolean ifUserInside(){
        if (layer.getContainers() != null) {
            for (KmlContainer container : layer.getContainers()) {
                if (container.getPlacemarks() != null) {
                    for (KmlPlacemark placemark : container.getPlacemarks()) {
                        contains = false;

                        if (placemark.getGeometry() instanceof KmlPolygon) {
                            KmlPolygon polygon = (KmlPolygon) placemark.getGeometry();

                            // Get the outer boundary and check if the test location lies inside
                            outerBoundary = polygon.getOuterBoundaryCoordinates();
                            contains = PolyUtil.containsLocation(latLngTest, outerBoundary, true);



                            if (contains) {
                                // Get the inner boundaries and check if the test location lies inside
                                ArrayList<ArrayList<LatLng>> innerBoundaries = polygon.getInnerBoundaryCoordinates();
                                if (innerBoundaries != null) {
                                    for (ArrayList<LatLng> innerBoundary : innerBoundaries) {
                                        // If the test location lies in a hole, the polygon doesn't contain the location
                                        if (PolyUtil.containsLocation(latLngTest, innerBoundary, true)) {
                                            contains = false;

                                        }
                                    }
                                }
                            }
                        }
                    }
                }
            }
        }
        return contains;
    }

    public class GetDirection extends AsyncTask<String , Void, String> {
        HttpsURLConnection connection = null;
        BufferedReader reader = null;
        StringBuilder builder = new StringBuilder();
        @Override
        protected String doInBackground(String... params) {
            String address = params[0];

            try {
                URL url = new URL(address);
                connection = (HttpsURLConnection) url.openConnection();
                if(connection.getResponseCode() != HttpURLConnection.HTTP_OK){
                    return "Error from server";
                }

                reader = new BufferedReader(new InputStreamReader(connection.getInputStream()));
                String line;
                while ((line = reader.readLine()) != null){
                    builder.append(line);
                }

            } catch (MalformedURLException e) {
                e.printStackTrace();
            } catch (IOException e) {
                e.printStackTrace();
            }

            return builder.toString();
        }

        @Override
        protected void onPostExecute(String s) {
        //get the polyline string
            String polygonPoints = "";

            try {
                JSONObject object = new JSONObject(s);
                JSONArray array = object.getJSONArray("routes");
                for (int i = 0; i < array.length(); i++) {
                    JSONObject arrObj1 = array.getJSONObject(i);
                    JSONObject points = arrObj1.getJSONObject("overview_polyline");
                    polygonPoints = points.getString("points");

                }
                //convert the string to polyline;
                ArrayList<LatLng> a = new ArrayList<>(decodePolyPoints(polygonPoints));
                //add polyline to the map
                mMap.addPolyline(new PolylineOptions().addAll(a).width(10).color(Color.BLUE));

            } catch (JSONException e) {
                e.printStackTrace();
            }
        }
    }

    //the method that convert the string to polyline
    public static ArrayList<LatLng> decodePolyPoints(String encodedPath){
        int len = encodedPath.length();

        final ArrayList<LatLng> path = new ArrayList<LatLng>();
        int index = 0;
        int lat = 0;
        int lng = 0;

        while (index < len) {
            int result = 1;
            int shift = 0;
            int b;
            do {
                b = encodedPath.charAt(index++) - 63 - 1;
                result += b << shift;
                shift += 5;
            } while (b >= 0x1f);
            lat += (result & 1) != 0 ? ~(result >> 1) : (result >> 1);

            result = 1;
            shift = 0;
            do {
                b = encodedPath.charAt(index++) - 63 - 1;
                result += b << shift;
                shift += 5;
            } while (b >= 0x1f);
            lng += (result & 1) != 0 ? ~(result >> 1) : (result >> 1);

            path.add(new LatLng(lat * 1e-5, lng * 1e-5));
        }

        return path;
    }
}

This is my AsyncTask to get the minimum distance point

public class MinimumDistanceTask extends AsyncTask<String, Void, Integer>{

    private int closeLocation;
    // private String points;
    private GetMinimumDistanceListener listener;

    public MinimumDistanceTask(GetMinimumDistanceListener listener){
        // this.points = points;
        this.listener = listener;
    }

    @Override
    protected Integer doInBackground(String... params) {
        HttpsURLConnection connection = null;
        BufferedReader reader = null;
        StringBuilder builder = new StringBuilder();
        int minimumDis = -1;

            String address = params[0];

            try {
                URL url = new URL(address);
                connection = (HttpsURLConnection) url.openConnection();
                if(connection.getResponseCode() != HttpURLConnection.HTTP_OK){
                    return -1;
                }

                reader = new BufferedReader(new InputStreamReader(connection.getInputStream()));
                String line;
                while ((line = reader.readLine()) != null){
                    builder.append(line);
                }
            ///get the json data
                JSONObject jsonObject1 = new JSONObject(builder.toString());
                JSONArray points = jsonObject1.getJSONArray("rows");
                JSONObject jsonObject2 = points.getJSONObject(0);
                JSONArray elements = jsonObject2.getJSONArray("elements");
                for (int i = 0; i < elements.length(); i++) {
                    JSONObject jsonObject3 = elements.getJSONObject(i);
                    JSONObject distance = jsonObject3.getJSONObject("distance");
                    if( distance.getInt("value") < minimumDis || minimumDis == -1) {
                        minimumDis = distance.getInt("value");
                        closeLocation = i;
                    }
                }

            } catch (MalformedURLException | JSONException e) {
                e.printStackTrace();
            } catch (IOException e) {
                e.printStackTrace();
            }

        return closeLocation;
        }

    @Override
    protected void onPostExecute(Integer closeLocation) {
            listener.getMinimumDistance(closeLocation);

    }

    public interface GetMinimumDistanceListener{
        void getMinimumDistance(int closeLocation);
    }
}

thanks a lot :)

Apolitical

I understand that you have a List of LatLng as your polygon and you want to calculate the minimum distance from a given LatLng to the polygon, is that correct? – Archibold

i have the minimum distans from the points of the polygon. but i want to get the distans from the whole area. if my user is between two points i calculate the distans to the nearest point but not to the short way to the Edge fo the polygone – Apolitical

and yes. I have a list of LatLng and I want to calculate the minimum distance from a given LatLng to the area – Apolitical

Answer 1

You can use a function like the following to calculate the nearest point from polygon defined by a List<LatLng> and a given LatLng.

It uses the PolyUtil.distanceToLine from the Google Maps Android API Utility Library to compute the distance between the test LatLng and every segment of the list, and a method based on the distanceToLine method from https://github.com/googlemaps/android-maps-utils/blob/master/library/src/com/google/maps/android/PolyUtil.java to compute the projection of a point on a segment.

private LatLng findNearestPoint(LatLng test, List<LatLng> target) {
    double distance = -1;
    LatLng minimumDistancePoint = test;

    if (test == null || target == null) {
        return minimumDistancePoint;
    }

    for (int i = 0; i < target.size(); i++) {
        LatLng point = target.get(i);

        int segmentPoint = i + 1;
        if (segmentPoint >= target.size()) {
            segmentPoint = 0;
        }

        double currentDistance = PolyUtil.distanceToLine(test, point, target.get(segmentPoint));
        if (distance == -1 || currentDistance < distance) {
            distance = currentDistance;
            minimumDistancePoint = findNearestPoint(test, point, target.get(segmentPoint));
        }
    }

    return minimumDistancePoint;
}

/**
 * Based on `distanceToLine` method from
 * https://github.com/googlemaps/android-maps-utils/blob/master/library/src/com/google/maps/android/PolyUtil.java
 */
private LatLng findNearestPoint(final LatLng p, final LatLng start, final LatLng end) {
    if (start.equals(end)) {
        return start;
    }

    final double s0lat = Math.toRadians(p.latitude);
    final double s0lng = Math.toRadians(p.longitude);
    final double s1lat = Math.toRadians(start.latitude);
    final double s1lng = Math.toRadians(start.longitude);
    final double s2lat = Math.toRadians(end.latitude);
    final double s2lng = Math.toRadians(end.longitude);

    double s2s1lat = s2lat - s1lat;
    double s2s1lng = s2lng - s1lng;
    final double u = ((s0lat - s1lat) * s2s1lat + (s0lng - s1lng) * s2s1lng)
            / (s2s1lat * s2s1lat + s2s1lng * s2s1lng);
    if (u <= 0) {
        return start;
    }
    if (u >= 1) {
        return end;
    }

    return new LatLng(start.latitude + (u * (end.latitude - start.latitude)),
            start.longitude + (u * (end.longitude - start.longitude)));


}

You can test it with the following code:

List<LatLng> points = new ArrayList<>();
points.add(new LatLng(2, 2));
points.add(new LatLng(4, 2));
points.add(new LatLng(4, 4));
points.add(new LatLng(2, 4));
points.add(new LatLng(2, 2));

LatLng testPoint = new LatLng(3, 0);

LatLng nearestPoint = findNearestPoint(testPoint, points);
Log.e("NEAREST POINT: ", "" + nearestPoint); // lat/lng: (3.0,2.0)
Log.e("DISTANCE: ", "" + SphericalUtil.computeDistanceBetween(testPoint, nearestPoint)); // 222085.35856591124

Archibold

oh.. that mean i dont need to use the Matrix google api. just use this and get the distance result? and then calculate the distance from the result to my user location? – Apolitical

Of course you can use the Matrix API, but this method works too – Archibold

mm.. so i dont understand. the Matrix api give me a result to a point in the polygon. I want to direct my user to space between two points of the polygon – Apolitical

I understood in the comments that you needed the minimum distance. I have updated my answer to return the nearest point in the nearest segment of the polygon to the test point – Archibold

I don't have time right now, but i will check it tonight. If I understand the method, it will return to me a new LatLng that exist between two point of the polygon. right? – Apolitical

Yes, The solution will give you a point on a segment of the polygon that is the closest point to your test point – Archibold

Thank tou so much!! Workins almost perfectly!! :) – Apolitical

You're welcome. Glad to help :) but, why almost? Why is it not perfect yet? If you improve the solution please, update my answer – Archibold

It's almost because it find the closest point in air range but not in walking. I need to think how to make the path that I am drawing on the map to stop on the first time it touch the polygon edge. – Apolitical

any way to do it without using PolyUtil.distanceToLine – Swaggering

@Kaveesh Why don't you want to use PolyUtil.distanceToLine? Of course you can write your own function to compute the distance but this one is well tested... – Archibold

@Antonio Do i need to import that entire library from Github in order to use PolyUtil.distanceToLine ? OR can i just add "compile 'com.google.maps.android:android-maps-utils:0.4+" in my app gradle? – Swaggering

Thanks for the answer Antonio, i think i got this. I will get back to you if in case i face any problem. :) – Swaggering

So this is great, How is this done when the polygon data is in a KML layer? – Dorina

thank you so much for sharing such nice concept! it is helpful. – Countenance

@Archibold Please help me to find the distance from polygon boundary to any point (lat,long) , that may be the user location. – Countenance