Calculer l'aire à partir de coordonnées géographiques sur des polygones non convexes

Question

Je voudrais calculer l'aire d'un polygone que je reçois d'une trace GPS. Donc, fondamentalement, je stocke la position de l'appareil/utilisateur après une période de temps, disons 5 secondes. En dehors de ce tracé, je voudrais calculer la zone dans laquelle se trouve la piste. Pour les polygones convexes cela ne devrait pas poser de problème car je suppose que je dois juste calculer l'aire des triangles (quand chaque triangle a un point de départ dans le premier point). Fondamentalement, comme cela est montré dans l'image de gauche. (Polygone jaune est le polygone fait des GPS-Emplacements, les lignes sombres montrent des triangles pour le calcul de surface, jaune clair est la zone désirée)

Mais la nuit dernière j'ai découvert un backdraw sur cette idée qui est quand le polygone n'est pas convexe. Non seulement une partie située à l'extérieur du polygone (côté supérieur gauche) sera calculée dans la zone, mais une partie du polygone sera mesurée plus d'une fois (voir les triangles qui se chevauchent en bas à gauche).

Est-ce que quelqu'un a une idée sur la façon dont je peux y parvenir? Je veux dire qu'il est encore difficile de savoir quelle zone devrait être calculée si mon polygone est en forme de S ... (mais je pourrais vivre avec ça ... tant que ça obtient un résultat assez juste sur les polygones qui sont (presque)

Mon autre idée de calcul de la coque convexe du polygone et de faire le calcul de surface ne fonctionnera pas bien non plus si le polygone est non-convexe, alors je ne compterais pas certaines zones plus d'une fois mais comme dans l'image de droite, je calculais une zone plus grande que c'est

si quelqu'un pouvait me aider Merci

Answer 1

Vous pourriez jeter un oeil à la formule générale pour la zone du polygone.!: http://mathworld.wolfram.com/PolygonArea.html. Cela couvre aussi le cas des polygones non convexes (tant qu'ils ne s'intersectent pas).

Answer 2

Vous voulez regarder une courbe de remplissage d'espace, par exemple une courbe en z ou une courbe d'hilbert. Une courbe sfc subdivise la surface en de nombreuses tuiles et réduit le problème bidimensionnel à un problème en une dimension. Vous voulez rechercher le blog de Nick sur l'indice spatial hilbert curve et quadtree.

Answer 3

Je fais cela tout le temps, mais je ne connais pas l'algorithme, car j'utilise une bibliothèque comme GEOS en C/C++, JTS en Java, ou Shapely en Python. Si vous pouvez vous permettre d'avoir une dépendance supplémentaire, je vous le recommande fortement, car les calculs sont robustes, testés, prennent un format d'entrée standard ouvert (Well-Known Text) et fonctionnent avec des géométries étranges et inhabituelles (par exemple des polygones avec trous, etc.). Vous pouvez faire toutes sortes de choses étranges et merveilleuses avec la géométrie une fois que vous avez ce travail.

Answer 4

Un peu en retard, mais je viens de l'implémenter en Java pour les coordonnées GPS. Vous devez normaliser les coordonnées GPS comme décrit ici: Polygon area calculation using Latitude and Longitude generated from Cartesian space and a world file. Fonctionne bien mais il y a une marge d'erreur d'environ 0,005% car les coordonnées cartésiennes sont une approximation basée sur un rayon terrestre idéal. Le code de note ci-dessous suppose que les paires de style geojson [longitude, latitude] et non l'inverse.

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