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

4
votes

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 night 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).

Sample polygons

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!

4
algorithmgeometrygeolocationpolygon
I suggest splitting the polygon into many convex polygons, which area would be easily computed. However, I can't think of any good way to split it. – Mikulas Dite
If you go down the splitting route, you might want to consider delaunay triangulation. – fmark
Note: your approach is almost the same as Howard's. You just aren't using negative area for segments which "backtrack". – Tom Sirgedas
there is an excel spreadsheet with formulas to calculate regular and irregular polygon by using cartesian coordinates. It can be used to calculate land lot area, etc... maruzar.blogspot.com/2011/12/… – user1115212
Actually the track occupies zero area, but you make it into a polygon by connecting the last point back to the first. Assuming the track started at the point where all the thin lines meet, if either of the tracks you showed takes a sharp right turn next, so that it travels into the interior of the polygon shown in the diagram, the area of your polygon will decrease. And if you follow the clockwise-counterclockwise convention in the MathWorld page, the areas of the two polygons you've shown are both negative. These results may be what you want--we can't know without more context. – David K

4 Answers

5
votes

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).

2
votes

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.

1
votes

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);
}
0
votes

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.