Como calcular a área de uma forma irregular?

17

Eu tenho um objeto de sala definido por uma coleção de segmentos de linha em loop para os quais preciso calcular a área. As classes podem ser descritas da seguinte maneira (em pseudo-có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();
}

As paredes de uma sala nunca podem se cruzar em lugar algum, mas nos pontos finais dos segmentos e quaisquer "sub-loops" criados também serão separados em uma nova sala. A solução não precisa ser perfeitamente precisa (margem de erro de 10% é aceitável) e também não é calculada com muita frequência (<1 / s).


fonte
7
Seria mais sensato Roomconter uma lista de Points e, em seguida, obter os segmentos conectando cada ponto e, em seguida, repetindo-o. Caso contrário, com a sua configuração atual, é muito leste para obter valores incorretos (por exemplo, sala não fechada, sala com parede no meio, etc.). Essa seria a melhor opção.
MCMastery
Outra opção é triangular a forma no topo e calcular as áreas de cada triângulo. A parte mais difícil é a triangulação. Factível, mas nem sempre bonito. A resposta do cadarço ainda é muito melhor.
Draco18s
@MCMastery Essa solução não funcionará, pois exige que Rooms esteja sempre completa, e esse pode não ser o caso se eu tiver o jogador construindo os Roomusando Segments. Além disso, é fácil definir uma função de sala fechada (basta percorrer os Segmentse certificar-se de que eles criam uma sala).

Respostas:

31

Você pode usar a fórmula do cadarço de Gauss :

Você precisa pegar a coordenada x de cada ponto, multiplicá-la pela coordenada y do próximo ponto e subtrair a coordenada y do ponto atual multiplicada pela coordenada x do próximo ponto do resultado e adicioná-las à área total. Depois de fazer isso para cada ponto, reduza pela metade a área total para obter a área real do polígono. Se o ponto atual é o último, o próximo é o primeiro.

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
fonte
2
Eu sempre usou isso para calcular o produto cruzado de dois vetores nunca soube que ele foi chamado algoritmo de cadarço
Sidar
3
Observe que isso pode ser estendido para calcular o volume de um objeto 3D irregular feito de triângulos, e pode ser considerado um caso trivial do teorema fundamental do cálculo.
precisa
5
A área aqui está assinada. Percorra os pontos na outra direção e a final Aserá negada. Dependendo do objetivo, um A = |A|pode ser necessário. Com código de área negativo, é possível encontrar a área em uma rosca irregular usando a lista de pontos interna e externa (uma na ordem oposta).
chux - Restabelece Monica
6
Porque é claro que Gauss ou Euler tem uma fórmula para isso.
corsiKa
0

Também poderíamos usar um método de Monte Carlo.

Desenhe um retângulo ao redor da forma arbitrária. Pegue uma fonte de PRNG uniformemente distribuída, por exemplo. mersenne twister, em seguida, limite a saída pelos comprimentos X, Y do retângulo usando a função modulo. Conte o não. de pontos aleatórios que caem dentro da sua forma. Divida pela quantidade total de pontos gerados. Multiplique esse quociente pela área do retângulo. Com cada iteração, você convergirá para a área verdadeira. O algoritmo é ridiculamente parrallelizable e pode ser usado para calcular 'volumes' arbitrários de formas dimensionais, desde que você possa determinar se uma coordenada R ^ N cai dentro do limite R ^ N da forma.

.

Aqui, alguém está usando esse método, encontre a área do círculo e a usa para calcular pi https://www.youtube.com/watch?v=VJTFfIqO4TU

FranG
fonte
2
-1: Você não deseja usar o módulo para obtê-lo dentro do alcance, deseja usar uma distribuição uniforme ou outra distribuição, fazê-lo da maneira que o módulo possui todos os tipos de problemas estatísticos.
user1997744
12
Esse método pode ser benéfico quando não temos um polígono simples, mas algum tipo de forma implícita cuja borda é difícil de expressar, como um fractal ou uma bolha metabólica. Para o caso de um polígono, como na pergunta, parece que seria desnecessariamente caro.
DMGregory
Como o @DMGregory apontou, não era isso que eu estava procurando. No entanto, acho que merece um +1, caso alguém precise.
Isso é interessante, mas o custo dos testes de inclusão não seria proibitivo? Ou seja, se você tem uma forma suficientemente complexa para justificar essa abordagem, os testes de inclusão também não seriam muito caros para que você não desejasse fazer muitos deles? (assumindo polígonos)
Mattia
Ok, o módulo é realmente problemático, mas é uma solução simples. O que realmente obtemos é aleatório P = 1/2 bits 0/1, então o que obtemos é uma distribuição uniforme de números, por exemplo. para 3 bits de 0 a 7. Fazer rand% 5, se um número aleatório assumir o valor 6 ou 7, é mapeado para 1 ou 2, aumentando efetivamente 1,2 a frequência, tornando a distribuição não uniforme. Para evitar isso, você precisa de algo como uma máquina de estado que gire o mapeamento, por exemplo. 6,7 mapeia para 1,2 e depois para 3,4 e depois 5,0 e continua. Também poderíamos jogar fora 6,7 ​​sempre que surgissem. Enfim, isso é um problema de implementação de biblioteca.
Frang
-1

Outra abordagem: não.

Em vez de:

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;

Basicamente, corte um triângulo. A área de um triângulo é simples e, ao fazer isso, reduzimos a contagem de segmentos do restante em um. Repita até que restar um triângulo.

Loren Pechtel
fonte
2
A fórmula de Gauss 'Shoelace é uma abreviação para isso que reduz pela metade ou o terço do número de cálculos. Trabalhe com isso.
Pieter Geerkens