Existe-t-il un algorithme permettant de calculer la surface d’une forme en fonction de coordonnées définissant la forme?

J’ai donc une fonction qui reçoit N points 2D aléatoires.

Existe-t-il un algorithme pour calculer l’aire de la forme définie par les points d’entrée?

Vous voulez calculer l’aire d’un polygone ?

(Extrait du lien, converti en C #)

 class Point { double x, y; } double PolygonArea(Point[] polygon) { int i,j; double area = 0; for (i=0; i < polygon.Length; i++) { j = (i + 1) % polygon.Length; area += polygon[i].x * polygon[j].y; area -= polygon[i].y * polygon[j].x; } area /= 2; return (area < 0 ? -area : area); } 

Définir la “zone” de votre collection de points peut être difficile, par exemple, si vous voulez obtenir la plus petite région avec des limites de lignes droites qui entourent votre ensemble, je ne sais pas comment procéder. Ce que vous voulez probablement faire, c’est calculer l’aire de la shell convexe de votre ensemble de points; Il s’agit d’un problème standard. Steven Skiena, dans le référentiel Stony Brook Algorithms , donne une description du problème à l’aide de liens vers des implémentations de solutions. À partir de là, une façon de calculer l’aire (il me semble que c’est la manière la plus évidente) serait de sortinganguler la région et de calculer l’aire de chaque sortingangle.

Vous pouvez utiliser l’algorithme de Timothy Chan pour trouver une shell convexe dans nlogh, où n est le nombre de points, h le nombre de sumts de shell convexe. Si vous voulez un algorithme facile, optez pour le scan de Graham.

De plus, si vous savez que vos données sont classées comme une simple chaîne, les points ne se croisant pas, vous pouvez utiliser l’algorithme de Melkman pour calculer la shell convexe dans O (N).

En outre, une propriété plus intéressante de shell convexe est que, il a le périmètre minimum.

Votre problème n’implique pas directement qu’il existe un polygone prêt à l’emploi (supposé par cette réponse ). Je recommanderais une sortingangulation telle qu’une sortingangulation de Delaunay et ensuite calculer sortingvialement l’aire de chaque sortingangle. OpenCV (je l’ai utilisé avec un grand nombre de points 2D et c’est très efficace) et CGAL fournissent d’excellentes implémentations pour déterminer la sortingangulation.

J’ai trouvé une autre fonction écrite en Java , donc je l’ai traduite en C #

 public static double area(List lats,List lons) { double sum=0; double prevcolat=0; double prevaz=0; double colat0=0; double az0=0; for (int i=0;i=90) { az=0; } else if (lats[i]<=-90) { az=Math.PI; } else { az=Math.Atan2(Math.Cos(lats[i]*Math.PI/180) * Math.Sin(lons[i]*Math.PI/180),Math.Sin(lats[i]*Math.PI/180))% (2*Math.PI); } if(i==0) { colat0=colat; az0=az; } if(i>0 && i