Android: how to arrange Latlog in android google so that it form rectangle polygon?

Question

I have 4 LatLng. For making a rectangle polygon, they should be in a list in either clockwise or anti-clockwise direction, so that when i add these LatLng in addPolygon(new LatLng) in google map it will create a rectangle shape. But in my case, they might be in clockwise or anti-clockwise or in different form. One example is -> 1st LatLng followed by 3rd LatLng followed by 2nd LatLng followed by 4th LatLng. In this case, It will not create rectangle polygon on google map. So I have to arrange it in clockwise or anti clockwise, so that the shape form must be rectangle, When i Put this LatLng list in addPolygon() in google map.

Suppose:

val rectOptions = PolygonOptions()
        .add(
            LatLng(37.35, -122.0),
            LatLng(37.45, -122.0),
            LatLng(37.45, -122.2),
            LatLng(37.35, -122.2)
        )

If I put rectOptions in AddPolygon() in mMap.addPolygon(rectOptions) it will Create a rectangular shape on google map. In my case:

val rectOptions = PolygonOptions()
        .add(
            LatLng(37.45, -122.0),
            LatLng(37.45, -122.2),
            LatLng(37.35, -122.0),
            LatLng(37.35, -122.2)
        )

This will not create rectangular shape. So I have to arrange these LatLng so that they form rectangular shape.

Actually it is a requirement. I have to write a program. – Anurag Apr 21 '20 at 14:07 — Anurag, Apr 21 '20 at 14:07

score 1 · Answer 1 · answered Apr 21 '20 at 18:51

In general your task is Convex hull construction and can be solved by one of Convex hull algorithms, e.g. like Gift wrapping (aka Jarvis) algorithm in this implementation.

Note that most of Convex hull algorithms implementations is for flat (x,y) point coordinates, not for LatLng location coordinates, so easiest way is to convert LatLng to flat (x,y) points with Projection.toScreenLocation() method and than, after Convex hull algorithm apply, convert it back to LatLng with Projection.fromScreenLocation() method.

Also remember, that the Projection object will only return valid values after the map has passed the layout process (i.e. it has valid width and height set) and you can get it in OnCameraIdleListener or use approach, described by andr in this answer.

So full demo source code can be like that:

public class MainActivity extends AppCompatActivity implements OnMapReadyCallback {

    private GoogleMap mGoogleMap;
    private SupportMapFragment mMapSupportedFragment;

    @Override
    protected void onCreate(Bundle savedInstanceState) {
        super.onCreate(savedInstanceState);
        setContentView(R.layout.activity_main);

        mMapSupportedFragment = (SupportMapFragment) getSupportFragmentManager().findFragmentById(R.id.map_fragment);
        mMapSupportedFragment.getMapAsync(MainActivity.this);
    }

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

        mGoogleMap.setOnCameraIdleListener(new GoogleMap.OnCameraIdleListener() {
            @Override
            public void onCameraIdle() {
                ArrayList<LatLng> sourcePoints = new ArrayList<>();
                sourcePoints.add(new LatLng(37.35, -122.0));
                sourcePoints.add(new LatLng(37.45, -122.2));
                sourcePoints.add(new LatLng(37.40, -122.1));
                sourcePoints.add(new LatLng(37.35, -122.2));
                sourcePoints.add(new LatLng(37.45, -122.0));

                Projection projection = mGoogleMap.getProjection();
                ArrayList<Point> screenPoints = new ArrayList<>(sourcePoints.size());
                for (LatLng location : sourcePoints) {
                    Point p = projection.toScreenLocation(location);
                    screenPoints.add(p);
                }

                ArrayList<Point> convexHullPoints = convexHull(screenPoints);
                ArrayList<LatLng> convexHullLocationPoints = new ArrayList(convexHullPoints.size());
                for (Point screenPoint : convexHullPoints) {
                    LatLng location = projection.fromScreenLocation(screenPoint);
                    convexHullLocationPoints.add(location);
                }

                PolygonOptions polygonOptions = new PolygonOptions();
                for (LatLng latLng : convexHullLocationPoints) {
                    polygonOptions.add(latLng);
                }

                mGoogleMap.clear();
                Polygon polygon = mGoogleMap.addPolygon(polygonOptions.strokeColor(Color.argb(255, 49, 101, 187)).fillColor(Color.argb(100, 49, 101, 187)));
            }
        });
    }

    private boolean CCW(Point p, Point q, Point r) {
        return (q.y - p.y) * (r.x - q.x) - (q.x - p.x) * (r.y - q.y) > 0;
    }

    public ArrayList<Point> convexHull(ArrayList<Point> points)
    {
        int n = points.size();
        if (n <= 3) return points;

        ArrayList<Integer> next = new ArrayList<>();

        // find the leftmost point
        int leftMost = 0;
        for (int i = 1; i < n; i++)
            if (points.get(i).x < points.get(leftMost).x)
                leftMost = i;
        int p = leftMost, q;
        next.add(p);

        // iterate till p becomes leftMost
        do {
            q = (p + 1) % n;
            for (int i = 0; i < n; i++)
                if (CCW(points.get(p), points.get(i), points.get(q)))
                    q = i;
            next.add(q);
            p = q;
        } while (p != leftMost);

        ArrayList<Point> convexHullPoints = new ArrayList();
        for (int i = 0; i < next.size() - 1; i++) {
            int ix = next.get(i);
            convexHullPoints.add(points.get(ix));
        }

        return convexHullPoints;
    }
}

Also you can find more simple algorithm if you need to "sort" points only for rectangles (e.g. you need to test which 3 points form a right angle and add it from first to third and then add fourth point and so on).

Android: how to arrange Latlog in android google so that it form rectangle polygon?

1 Answers1