Como faço para calcular a área de um polígono 2d?

Assumindo uma série de pontos no espaço 2D que não se auto-interceptam, qual é um método eficiente de determinar a área do polígono resultante?

Como uma nota lateral, isso não é lição de casa e eu não estou procurando por código. Eu estou procurando uma descrição que eu possa usar para implementar meu próprio método. Eu tenho minhas idéias sobre como puxar uma seqüência de triângulos da lista de pontos, mas eu sei que há um monte de casos de borda sobre polígonos convexos e côncavos que eu provavelmente não vou pegar.

Aqui está o método padrão , AFAIK. Basicamente, some os produtos cruzados em torno de cada vértice. Muito mais simples que a triangulação.

Código Python, dado um polígono representado como uma lista de coordenadas de vértice (x, y), envolvendo implicitamente o último vértice até o primeiro:

def area(p): return 0.5 * abs(sum(x0*y1 - x1*y0 for ((x0, y0), (x1, y1)) in segments(p))) def segments(p): return zip(p, p[1:] + [p[0]]) 

David Lehavi comenta: Vale a pena mencionar por que este algoritmo funciona: É uma aplicação do teorema de Green para as funções −y e x; exatamente como um planímetro funciona. Mais especificamente:

Fórmula acima
integral_over_perimeter(-y dx + x dy) =
integral_over_area((-(-dy)/dy+dx/dx) dy dx) =
2 Area

O produto cruzado é um clássico.

Se você tiver zillion de tal cálculo para fazer, tente a seguinte versão otimizada que requer metade das multiplicações:

 area = 0; for( i = 0; i < N; i += 2 ) area += x[i+1]*(y[i+2]-y[i]) + y[i+1]*(x[i]-x[i+2]); area /= 2; 

Eu uso o subscrito de array para maior clareza. É mais eficiente usar pointers. Embora bons compiladores façam isso por você.

Presume-se que o polígono esteja "fechado", o que significa que você copia o primeiro ponto como um ponto com o subscrito N. Ele também assume que o polígono tem um número par de pontos. Anexe uma cópia adicional do primeiro ponto, se N não for par.

O algoritmo é obtido desenrolando e combinando duas iterações sucessivas do algoritmo clássico de produto cruzado.

Não tenho certeza de como os dois algoritmos se comparam à precisão numérica. Minha impressão é que o algoritmo acima é melhor que o clássico porque a multiplicação tende a restaurar a perda de precisão da subtração. Quando restrito a usar flutuadores, como acontece com a GPU, isso pode fazer uma diferença significativa.

EDIT: "Área de Triângulos e Polígonos 2D e 3D" descreve um método ainda mais eficiente

 // "close" polygon x[N] = x[0]; x[N+1] = x[1]; y[N] = y[0]; y[N+1] = y[1]; // compute area area = 0; for( size_t i = 1; i <= N; ++i ) area += x[i]*( y[i+1] - y[i-1] ); area /= 2; 

Esta página mostra que a fórmula

insira a descrição da imagem aqui

pode ser simplificado para:

insira a descrição da imagem aqui

Se você escrever alguns termos e agrupá-los de acordo com fatores comuns de xi , a igualdade não será difícil de ver.

A sum final é mais eficiente, pois requer apenas n multiplicações em vez de 2n .

 def area(x, y): return abs(sum(x[i] * (y[i + 1] - y[i - 1]) for i in xrange(-1, len(x) - 1))) / 2.0 

Eu aprendi esta simplificação de Joe Kington, aqui .


Se você tem NumPy, esta versão é mais rápida (para todos os arrays, exceto muito pequenos):

 def area_np(x, y): x = np.asanyarray(x) y = np.asanyarray(y) n = len(x) shift_up = np.arange(-n+1, 1) shift_down = np.arange(-1, n-1) return (x * (y.take(shift_up) - y.take(shift_down))).sum() / 2.0 

Um conjunto de pontos sem outras restrições não define necessariamente de forma exclusiva um polígono.

Então, primeiro você tem que decidir qual polígono construir a partir desses pontos – talvez o casco convexo? http://en.wikipedia.org/wiki/Convex_hull

Em seguida, triangule e calcule a área. http://www.mathopenref.com/polygonirregulararea.html

Para expandir as áreas de triangulação e sum de triângulo, elas funcionam se você tiver um polígono convexo OU, por acaso, você escolhe um ponto que não gera linhas para todos os outros pontos que cruzam o polígono.

Para um polígono geral sem interseção, você precisa sumr o produto cruzado dos vetores (ponto de referência, ponto a), (ponto de referência, ponto b) onde a e b são “próximos” um ao outro.

Supondo que você tenha uma lista de pontos que definem o polígono em ordem (sendo os pontos i e i + 1 formam uma linha do polígono):

Soma (produto cruzado ((ponto 0, ponto i), (ponto 0, ponto i + 1)) para i = 1 a n – 1.

Pegue a magnitude desse produto cruzado e você terá a área de superfície.

Isto irá lidar com polígonos côncavos sem ter que se preocupar em escolher um bom ponto de referência; Quaisquer três pontos que geram um triângulo que não esteja dentro do polígono terão um produto cruzado que aponta na direção oposta de qualquer triângulo que esteja dentro do polígono, de forma que as áreas sejam sumdas corretamente.

Calcular a área do polígono

http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=geometry1#polygon_area

 int cross(vct a,vct b,vct c) { vct ab,bc; ab=ba; bc=cb; return ab.x*bc.y-ab.y*bc.x; } double area(vct p[],int n) { int ar=0; for(i=1;i+1 

Ou faça uma integral de contorno. O Teorema de Stokes permite expressar uma integral de área como uma integral de contorno. Uma pequena quadratura de Gauss e Bob é seu tio.

Uma maneira de fazer isso seria decompor o polígono em triângulos , calcular a área dos triângulos e considerar a sum como a área do polígono.

  1. Defina um ponto base (o ponto mais convexo). Este será seu ponto de pivô dos triângulos.
  2. Calcule o ponto mais esquerdo (arbitrário), além do ponto base.
  3. Calcule o segundo ponto mais à esquerda para completar seu triângulo.
  4. Salve esta área triangulada.
  5. Mude um ponto para a direita em cada iteração.
  6. Soma as áreas trianguladas

Melhor do que sumr triângulos é sumr trapézios no espaço cartesiano:

 area = 0; for (i = 0; i < n; i++) { i1 = (i + 1) % n; area += (vertex[i].y + vertex[i1].y) * (vertex[i1].x - vertex[i].x) / 2.0; } 

solução independente de linguagem:

DADO: um polígono pode SEMPRE ser composto por n-2 triângulos que não se sobrepõem (n = número de pontos OU lados). 1 triângulo = polígono de 3 lados = 1 triângulo; 1 quadrado = polígono de 4 lados = 2 triângulos; etc ad nauseam QED

portanto, um polígono pode ser reduzido por “corte” de triângulos e a área total será a sum das áreas desses triângulos. tente com um pedaço de papel e tesoura, é melhor se você visualizar o processo antes de seguir.

Se você pegar 3 pontos consecutivos em um caminho de polígonos e criar um triângulo com esses pontos, você terá um e apenas um dos três cenários possíveis:

  1. o triângulo resultante está completamente dentro do polígono original
  2. triângulo resultante é totalmente fora do polígono original
  3. o triângulo resultante está parcialmente contido no polígono original

estamos interessados ​​apenas nos casos que caem na primeira opção (totalmente contidos).

toda vez que encontramos uma delas, nós a cortamos, calculamos sua área (fácil, não vamos explicar a fórmula aqui) e fazemos um novo polígono com um lado a menos (equivalente ao polígono com esse triângulo cortado). até que tenhamos apenas um triângulo.

como implementar isso programaticamente:

crie uma matriz de pontos (consecutivos) que representam o caminho AO REDOR do polígono. comece no ponto 0. execute o array fazendo triângulos (um de cada vez) dos pontos x, x + 1 e x + 2. Transforme cada triângulo de uma forma em uma área e cruze-a com a área criada a partir do polígono. Se a interseção resultante é idêntica ao triângulo original, então o dito triângulo está totalmente contido no polígono e pode ser cortado. remova x + 1 da matriz e comece novamente de x = 0. caso contrário (se o triângulo estiver fora do polígono [parcialmente ou completamente]), vá para o próximo ponto x + 1 na matriz.

Além disso, se você deseja integrar-se ao mapeamento e começar a partir de geopoints, é necessário converter de geopoints em pontos de canvas FIRST. isso requer decidir uma modelagem e uma fórmula para a forma da Terra (embora tendamos a pensar na Terra como uma esfera, ela é na verdade um ovóide irregular (formato de ovo), com dentes). Existem muitos modelos por aí, para mais informações wiki. Uma questão importante é se você considerará ou não a área como um avião ou como uma curva. em geral, áreas “pequenas”, onde os pontos estão separados por alguns quilômetros, não gerarão erro significativo se considerarem planares e não convexos.

A implementação da fórmula do Shoelace pode ser feita em Numpy. Assumindo estes vértices:

 import numpy as np x = np.arange(0,1,0.001) y = np.sqrt(1-x**2) 

Podemos definir a seguinte function para encontrar a área:

 def PolyArea(x,y): return 0.5*np.abs(np.dot(x,np.roll(y,1))-np.dot(y,np.roll(x,1))) 

E obtendo resultados:

 print PolyArea(x,y) # 0.26353377782163534 

Evitar o loop torna esta function ~ 50X mais rápida que PolygonArea :

 %timeit PolyArea(x,y) # 10000 loops, best of 3: 42 µs per loop %timeit PolygonArea(zip(x,y)) # 100 loops, best of 3: 2.09 ms per loop 

Nota: Eu escrevi esta resposta para outra pergunta , apenas menciono isto aqui para ter uma lista completa de soluções.

Minha inclinação seria simplesmente começar a cortar triângulos. Eu não vejo como qualquer outra coisa poderia evitar ser muito peludo.

Tome três pontos sequenciais que compõem o polígono. Assegure-se de que o ângulo seja menor que 180. Agora você tem um novo triângulo que não deve ser problema para calcular, exclua o ponto do meio da lista de pontos do polígono. Repita até que você tenha apenas três pontos restantes.

C maneira de fazer isso:

 float areaForPoly(const int numVerts, const Point *verts) { Point v2; float area = 0.0f; for (int i = 0; i 

Código Python

Como descrito aqui: http://www.wikihow.com/Calculate-the-Area-of-a-Polygon

Com pandas

 import pandas as pd df = pd.DataFrame({'x': [10, 20, 20, 30, 20, 10, 0], 'y': [-10, -10, -10, 0, 10, 30, 20]}) df = df.append(df.loc[0]) first_product = (df['x'].shift(1) * df['y']).fillna(0).sum() second_product = (df['y'].shift(1) * df['x']).fillna(0).sum() (first_product - second_product) / 2 600 

Eu vou dar algumas funções simples para calcular a área do polígono 2d. Isso funciona tanto para polígonos convexos quanto côncavos. nós simplesmente dividimos o polígono em muitos sub-triângulos.

 //don't forget to include cmath for abs function struct Point{ double x; double y; } // cross_product double cp(Point a, Point b){ //returns cross product return ax*by-ay*bx; } double area(Point * vertices, int n){ //n is number of sides double sum=0.0; for(i=0; i