Convex Hull from GeoJSON

I’m working with the Environment Agency Real Time flood-monitoring API which returns flood areas as GeoJSON, these areas are made up of many thousands of points and displaying them on Android GoogleMaps as-is (using the GoogleMap Utility Library) kills performance, for example the local Walsden flood area GeoJSON has 7347 points, but the effected flood report could apply to anywhere within this region, so the detail isn’t useful or necessary:

1447444652


What I want to do instead is trace the outline of the flood area and place a marker at the centre, the name for a bounding polygon of an array of points is called a Convex Hull.

To get this shape I need all the points that make up the GsoJSON shape, iterating through the GeoJSON using JSONObject/JSONArray to extract a list of Lat/Lon pairs would be very expensive, instead you can pass the raw GeoJSON String through a regular expression:

public static List<LatLng> getPoints(String jsonStr){
    List<LatLng> points = new ArrayList<>();
    Pattern pattern = Pattern.compile("\\[([^\\[\\],]*),([^\\[\\],]*)]");
    Matcher latLonMatcher = pattern.matcher(jsonStr);
    while (latLonMatcher.find()) {
        double v1 = Double.parseDouble(latLonMatcher.group(1));
        double v2 = Double.parseDouble(latLonMatcher.group(2));

        if(v1 > v2){
            points.add(new LatLng(v1, v2));
        }else{
            points.add(new LatLng(v2, v1));
        }
    }

    return points;
}

Calculating the centre point for the marker is easy, just an average of the Latitude and Longitude points:

public static LatLng getCenter(List<LatLng> points){
    double totalLatitude = 0;
    double totalLongitude = 0;
    for(LatLng point : points){
        totalLatitude += point.latitude;
        totalLongitude += point.longitude;
    }

    return new LatLng(totalLatitude/points.size(), totalLongitude/points.size());
}

I found a beautiful Convex Hull implementation from Jared Rummler which works with x,y points, instead of adapting this code to work with Lat,Longs we can just convert between the two using the GoogleMap Projection class: convert the LatLng list to Points, run through the Quick Hull algorithm then convert back to LatLng, not efficient but still reasonable:

public static ArrayList<Point> convertToPoint(List<LatLng> coords, Projection projection){
    ArrayList<Point> points = new ArrayList<Point>();

    for(LatLng coord : coords){
        points.add(projection.toScreenLocation(coord));
    }

    return points;
}

public static ArrayList<LatLng> convertToLatLng(List<Point> points, Projection projection){
    ArrayList<LatLng> coords = new ArrayList<LatLng>();

    for(Point point : points){
        coords.add(projection.fromScreenLocation(point));
    }

    return coords;
}

The final convex hull has just 23 points:

1447444893