Calculate area out of geo-coordinates on non-convex polygons

I would like to calculate the area of a polygon that I get from a GPS track. So basically I store the position of the device/user after a period of time, let's say 5 seconds.

Out of this track polygon I would like to calculate the area the track is in. For convex polygons this shouldn't be a problem since I guess I just need to calculate the area of the triangles (when each triangly has one starting point in the first point). Basically as it's shown in the left image. (Yellow Polygon is the polygon made of the GPS-Locations, dark lines show triangles for area calculation, light-yellow is the desired area)

But last n开发者_如何转开发ight I discovered a backdraw on that idea which is when the polygon is not convex. Not only will a part that is outside the polygon (upper left side) being calculated in the area, also will some area of the polygon be measured more than once (look at the overlapping triangles in the bottom left).

Does anybody have an idea on how I can achieve this? I mean it's still difficult to even know which area should be calculated if my polygon is like S-shaped... (but I could live with that... as long as it gets a fair enough result on polygons that are (almost) closed.

My other idea of calculating the convex hull of the polygon and then doing the area calculation on that won't work well either if the polygon is non-convex. I then wouldn't count some areas more than once but as in the right image I would calculate a bigger area than it is.

Would be great if anyone could help me with this! Thanks!

You might have a look at the general formula for polygon area: http://mathworld.wolfram.com/PolygonArea.html. This also covers the case of non-convex polygons (as long as they are not self-intersecting).

I do this all the time, but I don't know the algorithm, because I use a library like GEOS in C/C++, JTS in Java, or Shapely in Python.

If you can afford to take on an extra dependency, I would highly recommend it, as the calculations are robust, tested, take an open-standard input format (Well-Known Text) and work with strange and unusual geometries (e.g. polygons with holes, etc.). You can do all sorts of strange and wonderful things with geometry once you have this working.

A bit late, but I just implemented this in Java for gps coordinates. You have to normalize the gps coordinates as described here: Polygon area calculation using Latitude and Longitude generated from Cartesian space and a world file. Works well but there is a margin of error of about 0.005% because the cartesian coordinates are an approximation based on an ideal earth radius. Note code below assumes geojson style [longitude,latitude] pairs and not the other way around.

public static double area(double[][] polygon) {
    Validate.isTrue(polygon.length > 3,"polygon should have at least three elements");

    double total=0;
    double[] previous=polygon[0];

    double[] center = polygonCenter(polygon);
    double xRef=center[0];
    double yRef=center[1];


    for(int i=1; i< polygon.length;i++) {
        double[] current = polygon[i];
        // convert to cartesian coordinates in meters, note this not very exact
        double x1 = ((previous[0]-xRef)*( 6378137*PI/180 ))*Math.cos( yRef*PI/180 );
        double y1 = (previous[1]-yRef)*( Math.toRadians( 6378137 ) );
        double x2 = ((current[0]-xRef)*( 6378137*PI/180 ))*Math.cos( yRef*PI/180 );
        double y2 = (current[1]-yRef)*( Math.toRadians( 6378137 ) );

        // calculate crossproduct
        total += x1*y2 - x2*y1;
        previous=current;
    }

    return 0.5 * Math.abs(total);
}

You want to look at a space-filling-curve, for example a z-curve or a hilbert-curve. A sfc curve subdivide the surface in many tiles and reduce the 2 dimensional problem to a 1 dimensional problem. You want to search for Nick's blog about spatial index hilbert curve and quadtree.