Calculate area from geocoordinates on non-convex polygons

Question

I would like to calculate the polygon area that I get from a GPS track. So basically I keep the device / user position after a while, say 5 seconds.

From this polygon of the track, I would like to calculate the area in which the track is located. For convex polygons this should not be a problem, since I think I just need to calculate the area of ​​the triangles (when each triangular point has one starting point at the first point). Basically, as shown in the left image. (A yellow polygon is a polygon of GPS locations, dark lines are triangles for calculating area, light yellow is the desired area)

But last night I found feedback with this idea when the polygon is not convex. Not only is the part outside the polygon (upper left side) calculated in the region, it will also measure some area of ​​the polygon more than once (look at the overlapping triangles in the lower left corner).

Does anyone have an idea on how I can achieve this? I mean, it’s still hard to understand which area should be calculated if my polygon looks like an S-shaped ... (but I could live with it ... until it gets a fairly fair result on the polygons which are (almost) closed.

My other idea of ​​calculating the convex hull of a polygon and then calculating the area on it will not work well if the polygon is not convex. Then I will not count some areas more than once, but, as in the correct image, I would calculate a larger area than this.

It would be great if someone could help me! Thanks!

Answer 1

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

Answer 2

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 additional dependency, I would highly recommend it, since the calculations were robust, tested, accept an open input format ( Well-known text ) and work with strange and unusual geometries (e.g. polygons with holes, etc.) d.). You can do all kinds of weird and wonderful things with geometry as soon as you do it.

Answer 3

A bit late, but I just implemented this in Java for gps coordinates. You should normalize the gps coordinates as described here: Calculation of the polygon area using the Locator and longitude generated from the Cartesian space and the world file . It works well, but the error is about 0.005%, because the Cartesian coordinates are an approximation based on the ideal radius of the Earth. The code below assumes that the pairs are geojson style [longitude, latitude], and not vice versa.

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

Answer 4

You want to look at the space filling curve, for example, the z-curve or the Hilbert curve. The sfc curve divides the surface in many fragments and reduces the two-dimensional problem to a one-dimensional problem. You want to find Nick's blog about the hilbert and quadtree spatial index curves.