Comment calculer l'aire d'une forme irrégulière?

17

J'ai un objet de pièce défini par une collection de segments de ligne en boucle dont j'ai besoin pour calculer l'aire. Les classes peuvent être décrites comme suit (en pseudo-code):

class Point {
    float x; 
    float y;
    ...
    float distanceFrom(Point p);
}

class Segment {
    Point start;
    Point end;
    ...
    float length();
}

class Room {
    List<Segment> walls;
    ...
    float area();
}

Les murs d'une pièce ne peuvent jamais se croiser n'importe où, mais aux extrémités des segments et les "sous-boucles" créées seront également séparées dans une nouvelle pièce. La solution n'a pas besoin d'être parfaitement précise (une marge d'erreur de 10% est acceptable) et n'est pas non plus calculée très souvent (<1 / s).

algorithm geometry
la source
7
Il serait plus logique Roomde contenir une liste de Points, puis d'obtenir les segments en connectant chaque point ensemble, puis en le bouclant. Sinon, avec votre configuration actuelle, il est très à l'est d'obtenir des valeurs incorrectes (par exemple une pièce non fermée, une pièce avec un mur au milieu, etc.). Ce serait la meilleure option.
MCMastery
Une autre option consiste à trianguler le haut de la forme et à calculer les aires de chaque triangle. La partie difficile est la triangulation. Faisable, mais pas toujours jolie. La réponse au lacet est encore bien meilleure.
Draco18 ne font plus confiance au SE
@MCMastery Cette solution ne fonctionnera pas, car elle exige que Rooms soit toujours complet, et ce ne sera peut-être pas le cas si je demande au joueur de construire les Rooms en utilisant Segments. De plus, une fonction de pièce fermée est facile à définir (il suffit de parcourir les Segments et de s'assurer qu'ils créent une pièce).

Réponses:

31

Vous pouvez utiliser la formule de lacet de Gauss :

Vous devez prendre la coordonnée x de chaque point, les multiplier par la coordonnée y du point suivant, puis soustraire la coordonnée y du point actuel multipliée par la coordonnée x du point suivant du résultat et les ajouter à la zone totale. Après avoir fait cela pour chaque point, divisez par deux la surface totale pour obtenir la surface réelle du polygone. Si le point actuel est le dernier, alors le suivant est le premier.

A = 0

for (i = 0; i < points.length; i++) do

    A += points[i].x * points[(i + 1) % points.length].y - points[i].y * points[(i + 1) % points.length].x

end

A /= 2
Bálint
la source
2
J'ai toujours utilisé cela pour calculer le produit croisé de deux vecteurs, je ne savais pas qu'il s'appelait algorithme de lacet
Sidar
3
Notez que cela peut être étendu pour calculer le volume d'un objet 3D irrégulier fait de triangles, et cela peut être considéré comme un cas trivial du théorème fondamental du calcul.
Dietrich Epp
5
La zone ici est signée. Parcourez les points dans l'autre sens et la finale Aest annulée. Selon l'objectif, un A = |A|peut être nécessaire. Avec un code de zone négatif, vous pouvez trouver la zone sur un beignet irrégulier en utilisant la liste de points intérieure et extérieure (une dans l'ordre opposé).
chux
6
Parce que bien sûr, Gauss ou Euler a une formule pour cela.
corsiKa
0

Nous pourrions également utiliser une méthode de Monte Carlo.

Tracez un rectangle autour de la forme arbitraire. Prenez une source PRNG uniformément distribuée, par exemple. mersenne twister, puis a lié la sortie par les longueurs X, Y du rectangle à l'aide de la fonction modulo. Comptez le non. de points aléatoires qui atterrissent à l'intérieur de votre forme. Divisez par le nombre total de points générés. Multipliez ce quotient par la zone du rectangle. À chaque itération, vous convergerez vers la vraie zone. L'algorithme est ridiculement parrallélisable et peut être utilisé pour calculer des volumes de forme dimensionnelle arbitraires, tant que vous pouvez déterminer si une coordonnée R ^ N tombe dans la limite R ^ N de la forme.

.

Ici, quelqu'un utilise cette méthode pour trouver la zone du cercle, puis l'utilise pour calculer pi https://www.youtube.com/watch?v=VJTFfIqO4TU

FranG
la source
2
-1: Vous ne voulez pas utiliser modulo pour le mettre à portée, vous voulez utiliser une distribution uniforme ou une autre distribution, le faire de la manière modulo a toutes sortes de problèmes statistiques.
user1997744
12
Cette méthode peut être bénéfique lorsque nous n'avons pas un simple polygone, mais plutôt une sorte de forme implicite dont la frontière est difficile à exprimer, comme un blob fractal ou metaball. Dans le cas d'un polygone comme dans la question, il semble que ce serait inutilement cher.
DMGregory
Comme l'a souligné @DMGregory, ce n'est pas ce que je cherchais. Cependant, je pense que cela mérite un +1 au cas où quelqu'un d'autre en aurait besoin.
C'est intéressant mais le coût des tests d'inclusion ne serait-il pas prohibitif? C'est-à-dire que si vous avez une forme suffisamment complexe pour justifier cette approche, les tests d'inclusion ne seraient-ils pas aussi très chers, donc vous ne voudriez pas en faire des tonnes? (en supposant des polygones)
Mattia
Ok modulo est en effet problématique, mais c'est une solution simple. Ce que nous obtenons vraiment est aléatoire P = 1/2 bits 0/1, donc ce que nous obtenons est une distribution uniforme de nombres, par exemple. pour 3 bits de 0 à 7. Faire rand% 5, si un nombre aléatoire prend la valeur 6 ou 7, est mappé à 1 ou 2, augmentant efficacement la fréquence de 1,2 rendant la distribution non uniforme. Pour éviter cela, vous avez besoin de quelque chose comme une machine d'état qui fait tourner le mappage, par exemple. 6,7 correspond à 1,2 puis à 3,4 puis à 5,0 et ça continue. Nous pourrions également jeter 6,7 à chaque fois qu'ils arrivaient. Quoi qu'il en soit, c'est un problème d'implémentation de bibliothèque.
2017
-1

Une autre approche: ne le faites pas.

Au lieu:

while (Segments.Count > 3)
{
    Segment A = Segments[Segments.Count - 2];
    Segment B = Segments[Segments.Count - 1];
    Segment C = new Segment(B.End, A.Start);
    Triangle T = new Triangle(A, B, C);
    Segments[Segments.Count - 2] = C;
    Segments.RemoveAt(Segments.Count - 1);
    if (B is inside the new shape Segments)
        Area -= T.Area;
    else
        Area += T.Area;
}
Area += new Triangle(Segments[0], Segments[1], Segments[2]).Area;

Fondamentalement, coupez un triangle. L'aire d'un triangle est simple et, ce faisant, nous avons réduit le nombre de segments du reste d'une unité. Répétez jusqu'à ce que ce qui reste soit un triangle.

Loren Pechtel
la source
2
La formule de Lacet de Gauss est un raccourci pour cela qui divise par deux ou par trois le nombre de calculs. Trouvez ça.
Pieter Geerkens