¿Cómo calcular el área de una forma irregular?

17

Tengo un objeto de habitación definido por una colección de segmentos de línea en bucle para los que necesito calcular el área. Las clases se pueden describir de la siguiente manera (en pseudocódigo):

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

Las paredes de una habitación nunca pueden cruzarse en ninguna parte, pero en los puntos finales de los segmentos y cualquier "sub-bucle" creado también se separará en una nueva habitación. La solución no necesita ser perfectamente precisa (se acepta un margen de error del 10%) y tampoco se calcula con mucha frecuencia (<1 / s).

algorithm geometry
fuente
77
Tendría más sentido Roomcontener una lista de Points, y luego obtener los segmentos conectando cada punto y luego volverlo a recorrer. De lo contrario, con su configuración actual, es muy oriental obtener valores incorrectos (por ejemplo, habitación no cerrada, habitación con pared en el medio, etc.). Esta sería la mejor opción.
MCMastery
Otra opción es triangular la forma superior y calcular las áreas de cada triángulo. La parte difícil es la triangulación. Posible, pero no siempre bonita. La respuesta de los cordones de los zapatos sigue siendo mucho mejor.
Draco18s ya no confía en SE
@MCMastery Esa solución no funcionará, ya que requiere que Rooms esté siempre completa, y ese puede no ser el caso si hago que el jugador construya Rooms usando Segments. Además, una función de sala cerrada es fácil de definir (solo recorra los Segmentcorreos electrónicos y asegúrese de que crean una sala).

Respuestas:

31

Puedes usar la fórmula del cordón de Gauss :

Debe tomar la coordenada x de cada punto, multiplicarlos por la coordenada y del siguiente punto, luego restar la coordenada y del punto actual multiplicada por la coordenada x del siguiente punto del resultado y agregarlos al área total. Después de hacer esto para cada punto, reduzca a la mitad el área total para obtener el área real del polígono. Si el punto actual es el último, entonces el siguiente es el primero.

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
fuente
2
Siempre usé eso para calcular el producto cruzado de dos vectores que nunca supe que se llamaba algoritmo de cordones
Sidar
3
Tenga en cuenta que esto puede extenderse para calcular el volumen de un objeto 3D irregular hecho de triángulos, y puede considerarse un caso trivial del teorema fundamental del cálculo.
Dietrich Epp
55
El área aquí está firmada. Ir a través de los puntos en la otra dirección y Ase niega el final . Dependiendo de la meta, A = |A|puede ser necesario. Con el código de área negativo puede encontrar el área en una dona irregular usando la lista de puntos internos y externos (uno en el orden opuesto).
chux - Restablece a Monica el
66
Porque, por supuesto, Gauss o Euler tienen una fórmula para ello.
corsiKa
0

También podríamos usar un método de Monte Carlo.

Dibuja un rectángulo alrededor de la forma arbitraria. Tome una fuente de PRNG distribuida uniformemente, por ejemplo. mersenne twister, luego limita la salida por las longitudes X, Y del rectángulo usando la función de módulo. Cuenta el no. de puntos aleatorios que aterrizan dentro de tu figura. Dividir por la cantidad total de puntos generados. Multiplica ese cociente por el área del rectángulo. Con cada iteración convergerás al área real. El algoritmo es ridículamente paralelo y puede usarse para calcular 'volúmenes' arbitrarios de formas dimensionales, siempre que pueda determinar si una coordenada R ^ N cae dentro del límite R ^ N de la forma.

.

Aquí alguien está usando este método para encontrar el área del círculo y luego lo usa para calcular pi https://www.youtube.com/watch?v=VJTFfIqO4TU

FranG
fuente
2
-1: No quieres usar el módulo para ponerlo dentro del rango, quieres usar una distribución uniforme u otra distribución, hacerlo de forma modular tiene todo tipo de problemas estadísticos.
user1997744
12
Este método puede ser beneficioso cuando no tenemos un polígono simple, sino más bien algún tipo de forma implícita cuyo borde es difícil de expresar, como un bloc fractal o metaball. Sin embargo, para el caso de un polígono como en la pregunta, parece que sería innecesariamente costoso.
DMGregory
Como señaló @DMGregory, esto no es lo que estaba buscando. Sin embargo, creo que merece un +1 en caso de que alguien más lo necesite.
Esto es interesante, pero ¿no sería prohibitivo el costo de las pruebas de inclusión? Es decir, si tiene una forma que es lo suficientemente compleja como para justificar este enfoque, ¿las pruebas de inclusión tampoco serían realmente costosas, por lo que no querría hacer toneladas de ellas? (asumiendo polígonos)
Mattia
Ok, el módulo es realmente problemático, pero es una solución simple. Lo que realmente obtenemos es P = 1/2 bits aleatorios 0/1, por lo que lo que obtenemos es una distribución uniforme de números, por ejemplo. para 3 bits de 0 a 7. Al hacer rand% 5, si un número aleatorio toma el valor 6 o 7, se asigna a 1 o 2, aumentando efectivamente la frecuencia de 1,2 haciendo que la distribución no sea uniforme. Para evitar eso, necesita algo como una máquina de estado que gira el mapeo, por ejemplo. 6,7 se asigna a 1,2, luego a 3,4, luego a 5,0 y continúa. También podríamos tirar 6,7 cuando aparecieran. De todos modos, es un problema de implementación de la biblioteca.
FranG
-1

Otro enfoque: no lo hagas.

En lugar:

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;

Básicamente, corta un triángulo. El área de un triángulo es simple y al hacerlo redujimos el recuento de segmentos del resto en uno. Repita hasta que lo que quede sea un triángulo.

Loren Pechtel
fuente
2
La fórmula de Gauss 'Shoelace es una abreviatura para esto que reduce a la mitad o en tres el número de cálculos. Resolverlo.
Pieter Geerkens