Regular Shape polygon Android map on Map Click

Question

I want to create a regular polygon shape no matter the order of click on map. Currently I am facing a problem if a click on the map to draw polygon in the following manner then it works fine order is following top left top right bottom right bottom left. IF this order is maintained then polygon drawn is perfectly fine similarly if i click on top right ,top left bottom right bottom it is also drawing perfectly fine. If when I change a single pint in order it does not draw proper shaped polygon Image1

Image 2

Code 2 draw polygon is following

     gMap.setOnMapClickListener(new GoogleMap.OnMapClickListener() {
            @Override
            public void onMapClick(LatLng latLng) {
                llClearSelection.setVisibility(View.VISIBLE);
                gMap.addMarker(new MarkerOptions().anchor(0.5f, 0.5f).icon(BitmapDescriptorFactory.fromResource(R.drawable.marker)).position(latLng));
                if (markerClicked) {
//                    latLngArrayListPolygon.clear();
                    if (polygon != null) {
                        polygon.remove();
                        polygon = null;
                    }

                    polygonOptions.add(latLng);
                    latLngArrayListPolygon.add(latLng);
                    polygonOptions.strokeColor(Color.RED);
                    polygonOptions.fillColor(shadeColor);
                    polygon = gMap.addPolygon(polygonOptions);
                    if (latLngArrayListPolygon.size() > 1)
                        ivSaveMap.setVisibility(View.VISIBLE);
                    else
                        ivSaveMap.setVisibility(View.GONE);
                } else {
                    if (polygon != null) {
                        polygon.remove();
                        polygon = null;
                    }
                    polygonOptions = new PolygonOptions().add(latLng);
                    latLngArrayListPolygon.add(latLng);
                    markerClicked = true;
                }
            }
        });

My concern is I want to draw a regular shape irrespective of the order of click on map

Answer 1

Finally I derived solution to create regular shape polygon. This is not related to Convex hull. Following are the Step to create regular shape polygon whether you click clock wise on map or counter clock wise on map.

1. Find the mid points of the edges of polygon
2. Calculate the nearest coordinate by finding distance between mid point of each edge and the coordinate to be drawn
3. The nearest coordinate = the edge with minimum distance from mid point to the coordinate to be drawn
4. move the nearest coordinate at the end by shifting array right Following is the code :

 ArrayList<LatLng> latLngArrayListPolygon = new ArrayList<>();
ArrayList<Double> distancesFromMidPointsOfPolygonEdges = new ArrayList<>();
    private void adjustPolygonWithRespectTo(LatLng point) {
        double minDistance = 0;

        if (latLngArrayListPolygon.size() > 2) {
            distancesFromMidPointsOfPolygonEdges.clear();
            //midPointsOfPolygonEdges?.removeAll()

            for (int i = 0; i < latLngArrayListPolygon.size(); i++) {
                // 1. Find the mid points of the edges of polygon
                ArrayList<LatLng> list = new ArrayList<>();

                if (i == (latLngArrayListPolygon.size() - 1)) {
                    list.add(latLngArrayListPolygon.get(latLngArrayListPolygon.size() - 1));
                    list.add(latLngArrayListPolygon.get(0));
                } else {
                    list.add((latLngArrayListPolygon.get(i)));
                    list.add((latLngArrayListPolygon.get(i + 1)));
                }


                LatLng midPoint = computeCentroid(list);

                // 2. Calculate the nearest coordinate by finding distance between mid point of each edge and the coordinate to be drawn
                Location startPoint = new Location("");
                startPoint.setLatitude(point.latitude);
                startPoint.setLongitude(point.longitude);
                Location endPoint = new Location("");
                endPoint.setLatitude(midPoint.latitude);
                endPoint.setLongitude(midPoint.longitude);
                double distance = startPoint.distanceTo(endPoint);

                distancesFromMidPointsOfPolygonEdges.add(distance);
                if (i == 0) {
                    minDistance = distance;
                } else {

                    if (distance < minDistance) {
                        minDistance = distance;
                    }
                }
                //midPointsOfPolygonEdges?.append(midPoint)
            }

            // 3. The nearest coordinate = the edge with minimum distance from mid point to the coordinate to be drawn
            int position = minIndex(distancesFromMidPointsOfPolygonEdges);


            // 4. move the nearest coordinate at the end by shifting array right
            int shiftByNumber = (latLngArrayListPolygon.size() - position - 1);

            if (shiftByNumber != latLngArrayListPolygon.size()) {
                latLngArrayListPolygon = rotate(latLngArrayListPolygon, shiftByNumber);
            }
        }

        // 5. Now add coordinated to be drawn
        latLngArrayListPolygon.add(point);
    }

    public static int minIndex(ArrayList<Double> list) {
        return list.indexOf(Collections.min(list));
    }

    public static <T> ArrayList<T> rotate(ArrayList<T> aL, int shift) {
        if (aL.size() == 0)
            return aL;

        T element = null;
        for (int i = 0; i < shift; i++) {
            // remove last element, add it to front of the ArrayList
            element = aL.remove(aL.size() - 1);
            aL.add(0, element);
        }

        return aL;
    }

    private LatLng computeCentroid(List<LatLng> points) {
        double latitude = 0;
        double longitude = 0;
        int n = points.size();

        for (LatLng point : points) {
            latitude += point.latitude;
            longitude += point.longitude;
        }

        return new LatLng(latitude / n, longitude / n);
    }

And to draw polygon on clicking on map is Following

 gMap.setOnMapClickListener(new GoogleMap.OnMapClickListener() {
        @Override
        public void onMapClick(LatLng latLng) {
            gMap.addMarker(new MarkerOptions().anchor(0.5f, 0.5f).icon(BitmapDescriptorFactory.fromResource(R.drawable.marker)).position(latLng));
            if (markerClicked) {
                if (polygon != null) {
                    polygon.remove();
                    polygon = null;
                }
                adjustPolygonWithRespectTo(latLng);
                PolygonOptions polygonOptions = null;
                for (int i = 0; i < latLngArrayListPolygon.size(); i++)
                    if (i == 0)
                        polygonOptions = new PolygonOptions().add(latLngArrayListPolygon.get(0));
                    else
                        polygonOptions.add(latLngArrayListPolygon.get(i));
                polygonOptions.strokeColor(Color.BLACK);
                polygonOptions.strokeWidth(5f);
                polygonOptions.fillColor(shadeColor);
                polygon = gMap.addPolygon(polygonOptions);
            } else {
                if (polygon != null) {
                    polygon.remove();
                    polygon = null;
                }
                polygonOptions = new PolygonOptions().add(latLng);
                latLngArrayListPolygon.add(latLng);
                markerClicked = true;
            }
        }

    });

Answer 2

Have a look at How can I determine whether a 2D Point is within a Polygon?

As your user clicks on the map you have to determine if the new vertex is within the polygon or outside. If it is inside, ignore. Else, add the polygon and run the algorithm for every point in polygon.

Hope this helps.