Android Google Maps PolygonOptions not plotted from given set of coordinates

Question

I am trying to plot a complex polygon around a route, following its steps with a given radius. To do so I drew 50-sided uniform polygons (which are practically circles) around each step (coordinate) of the route. Now I obtain a set of coordinates of all the plotted circles around the route, and I can see them on the map but they are overlapped which is not very good looking, and it's not a good practice to add such a huge number of overlays on the map.

So what I need to do now is to merge all the polygons I have now into one polygon and plot it in the map.

I tried deleting the intersection points of every two polygons (testing if points of polygon1 lie inside polygon2 and vice versa) and merging all the rest of the coordinates in one array and then construct my new polygon but it didn't work. Here's a code snippet of how I'm doing this:

public ArrayList<PolygonOptions> polygons = new ArrayList<>();

// lineOptions is the set of route coordinates
    for (int i = 0; i < lineOptions.getPoints().size() - 1; i++) {
        // Draw a circle around each point of the route
        PolygonOptions circle1 = drawCircle(lineOptions.getPoints().get(i), 0.1);
        PolygonOptions circle2 = drawCircle(lineOptions.getPoints().get(i + 1), 0.1);
        // Draw a convex hull between every two successive circles
        PolygonOptions convexHull = convexHull(circle1, circle2);

        convexHull.strokeWidth(0);
        convexHull.fillColor(0x7F729E47);
        activity.range.add(activity.mMap.addPolygon(convexHull));
        polygons.add(convexHull);
    }


if (polygons.size() == 1) {
        pts.addAll(polygons.get(0).getPoints());
    } else {
        for (int i = 0; i < polygons.size() - 1; i++) {
            ArrayList<LatLng> pts1 = new ArrayList<>();
            ArrayList<LatLng> pts2 = new ArrayList<>();
            pts1.addAll(polygons.get(i).getPoints());
            pts2.addAll(polygons.get(i + 1).getPoints());

            for (int j = 0; j < pts1.size(); j++) {
                if (pointInPolygon(pts1.get(j), pts2)) {
                    pts1.remove(j);
                }
            }

            for (int j = 0; j < pts2.size(); j++) {
                if (pointInPolygon(pts2.get(j), pts1)) {
                    pts2.remove(j);
                }
            }

            pts.addAll(pts1);
            pts.addAll(pts2);
        }
    }

// This part didn't work
// PolygonOptions range = new PolygonOptions();
// range.addAll(pts);
// range.strokeWidth(0);
// range.fillColor(0x7F729E47);
// activity.range.add(activity.mMap.addPolygon(range));

Answer 1

Following @antonio's directions, and using JTS Topology Suit I was able to plot a polygon around the route (buffer the route) with a defined radius. When I used the buffer function in the JTS library I obtained a buffer of the route but the caps were oval, I read about it and this happens because the computed coordinates are projected on the earth's map which is not flat, the caps get more oval when the route is closer to the earth's poles, and more round when closer to the equator line (0º latitude). Anyway, I used another functionality from thhe library to union all the polygons that I already had in my question, and this was the result:

    public ArrayList<Polygon> polys = new ArrayList<>();

    //lineOptions is the set of route coordinates
    for (int i = 0; i < lineOptions.getPoints().size() - 1; i++) {
        // Draw a circle around each point of the route
        PolygonOptions circle1 = drawCircle(lineOptions.getPoints().get(i), 0.1);
        PolygonOptions circle2 = drawCircle(lineOptions.getPoints().get(i + 1), 0.1);


        // Draw a convex hull between every two successive circles
        PolygonOptions convexHull = convexHull(circle1, circle2);



        List<LatLng> latLngs = convexHull.getPoints();
        List<Coordinate> coords = new ArrayList<>();

        for (int j=0; j<latLngs.size(); j++) {
            coords.add(new Coordinate(latLngs.get(j).latitude, latLngs.get(j).longitude));
            if(j==latLngs.size()-1)
                coords.add(new Coordinate(latLngs.get(0).latitude, latLngs.get(0).longitude));
        }

        Coordinate[] coordinates = coords.toArray(new Coordinate[coords.size()]);

        GeometryFactory fact = new GeometryFactory();
        LinearRing linear = new GeometryFactory().createLinearRing(coordinates);
        Polygon poly = new Polygon(linear, null, fact);

        polys.add(poly);

    }


    PolygonOptions combine = combineIntoOnePolygon(polys);
    combine.strokeWidth(0);
    combine.fillColor(0x7F729E47);
    activity.range = activity.mMap.addPolygon(combine);

The function that does the combining:

static PolygonOptions combineIntoOnePolygon(Collection<Polygon> geometries ){
    Geometry all = null;
    PolygonOptions allPolygon = new PolygonOptions();

    for(Iterator<Polygon> i = geometries.iterator(); i.hasNext(); ){
        Polygon geometry = i.next();
        if( geometry == null ) continue;
        if( all == null ){
            all = geometry;
        }
        else {
            all = all.union( geometry );
        }
    }

    List<Coordinate> bufferCoordinates = Arrays.asList(all.getCoordinates());

    for (Coordinate c : bufferCoordinates) {
        allPolygon.add(new LatLng(c.x, c.y));
    }

    return allPolygon;
}

Answer 2

You need to compute the buffer of the line. According to Wikipedia:

A buffer is an area defined by the bounding region determined by a set of points at a specified maximum distance from all nodes along segments of an object.

The buffer of a geometry is computed using the Minkowski sum. The Minkowsky sum takes two polygons (one is your polyline and the other is a circle if you want rounded caps) and moves the second one throught the path of the first one.

You can find some concrete implementations of the Minkowski sum that you can study. For example https://github.com/perelo/computational-geometry/blob/master/src/computational_geometry/model/algorithms/Minkowski.java