Obliczanie obszaru poligonowego

Question

Dostałem ten kod w javascript, aby obliczyć nieregularny obszar wielokąta z sieci.

function polygonArea(X, Y, numPoints) 
{  
area = 0; // Accumulates area in the loop 
j = numPoints-1; // The last vertex is the 'previous' one to the first 

    for (i=0; i<numPoints; i++) 
    { area = area + (X[j]+X[i]) * (Y[j]-Y[i]); 
     j = i; //j is previous vertex to i 
    } 
    return area/2; 
} 

var xPts = [3, 3, 2, 2, 3, 3, 6, 6, 9, 9, 4, 4 ]; 
var yPts = [2, 4, 4, 5, 5, 6, 6, 5, 5, 3, 3, 2]; 

var a = polygonArea(xPts, yPts, 4); 
alert("Area = " + a); 

Wyniki wydaje się być poprawne. jeśli wierzchołek jest śledzony w kierunku zgodnym z ruchem wskazówek zegara, będzie pokazywał pozytywne wyniki, ale będzie ujemny, jeśli wyśleduję wierzchołek w kierunku przeciwnym do ruchu wskazówek zegara. Dlaczego to jest takie?

Jak działa ten algorytm? naprawdę chcę wiedzieć, jakie jest matematyczne wyjaśnienie, ponieważ wciąż mam trudności z zrozumieniem wyjaśnienia w sieci.

Answer 1

Wyobraź sobie rysowanie poziomych linii od każdego wierzchołka do osi Y; dla każdej z krawędzi, to opisują trapezu:

Y-axis 
^ 
| 
|--------o (X[j], Y[j]) 
|   \ 
|   \ 
|   \ 
|------------o (X[i], Y[i]) 
| 
+----------------------------> X-axis 

Wzór (X[j]+X[i]) * (Y[j]-Y[i]) w pętli wewnętrznej oblicza dwukrotnie powierzchnię tego trapezu jeśli Y[i] <= Y[j] lub negatywny dwukrotnie powierzchni, jeżeli Y[i] >= Y[j].

W przypadku wielokąta zamkniętego naturalnie odejmuje on obszar po lewej stronie "unoszących się" krawędzi od obszaru po lewej stronie od krawędzi "w dół". Jeśli wielokąt jest zgodny z ruchem wskazówek zegara, to dokładnie wycina dokładny (podwójny) obszar wielokąta; jeśli przeciwnie do ruchu wskazówek zegara, otrzymasz ujemny (podwójny) obszar.

Aby obliczyć powierzchnię danego wielokąta,

Y-axis 
^ 
| 
|  o------o 
|  |  \ 
|  |  \ 
|  o   \ 
|   \   o     
|   \  /
|   \ /
|   \ /
|    \/
|    o 
| 
+-------------------------> X-axis 

wziąć obszar downgoing:

Y-axis 
^ 
| 
|--------o------o 
|    \ 
|     \ 
|  o   \ 
|     o     
|    /
|    /
|    /
|    /
|--------------o 
| 
+-------------------------> X-axis 

minus obszar upgoing:

Y-axis 
^ 
| 
|--------o  o 
|  | 
|  | 
|  o 
|   \   o     
|   \ 
|   \ 
|   \ 
|    \ 
|--------------o 
| 
+-------------------------> X-axis 

Chociaż powyższy przykład używa wypukły wielokąt, obliczenia tego obszaru są poprawne dla dowolnych wielokątów, bez względu na to, ile klepnięć w górę i w dół hs mogą mieć.

Answer 2

Nie ma za tym żadnej magii. Wystarczy spojrzeć na wyznacznik macierzy (http://en.wikipedia.org/wiki/Determinant#2.C2.A0.C3.97.C2.A02_matrices)

edit:

Szczerze mówiąc: jest jakaś magia w tym kodzie:

1. potrzebujesz triangulacji. Tutaj: tworzymy trójkąty zaczynające się od (0,0) i posiadając (Xi, Yi) i (Xj, Yj)
2. obliczasz wyznacznik dla każdego trójkąta, aby uzyskać: Xi Yj - Xj Yi. Ale tutaj ktoś oblicza (X[j]+X[i]) * (Y[j]-Y[i]) = Xj Yj - Xj Yi + Xi Yj - Xi Yi = (Xj Yj - Xi Yi) + (Xi Yj - Xj Yi). Ale szczęśliwie, jeśli dodasz wszystkie te części, sama się anuluje. Więc to jest trudna część.

Answer 3

Kumuluje podpisany obszar między każdym zorientowanym segmentem P [i], P [i + 1] a osią Y. Na końcu pętli obszar poza polem zostanie anulowany (zostanie policzony dwukrotnie z różnymi znakami), a podpisany obszar wnętrza pozostanie.

Answer 4

Istnieje algorytm do obliczania powierzchni wielokąta:

function calcPolygonArea(vertices) { 
    var total = 0; 

    for (var i = 0, l = vertices.length; i < l; i++) { 
     var addX = vertices[i].x; 
     var addY = vertices[i == vertices.length - 1 ? 0 : i + 1].y; 
     var subX = vertices[i == vertices.length - 1 ? 0 : i + 1].x; 
     var subY = vertices[i].y; 

     total += (addX * addY * 0.5); 
     total -= (subX * subY * 0.5); 
    } 

    return Math.abs(total); 
}