Produkt krzyżowy jest klasykiem.

Jeśli masz do wykonania miliard takich obliczeń, wypróbuj następującą zoptymalizowaną wersję, która wymaga o połowę mniej mnożenia:

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;

Używam indeksu array dla jasności. Bardziej wydajne jest używanie wskaźników. Chociaż dobre Kompilatory zrobią to za Ciebie.

Wielokąt zakłada się jako "zamknięty", co oznacza, że pierwszy punkt jest kopiowany jako punkt z indeksem N. zakłada się również, że wielokąt ma parzystą liczbę punktów. Dołącz dodatkowa kopia pierwszego punktu, jeśli N nie jest parzyste.

Algorytm otrzymuje się przez rozwinięcie i połączenie dwóch kolejnych iteracji klasycznego algorytmu iloczynu krzyżowego.

Nie jestem pewien, jak te dwa algorytmy porównują precyzję numeryczną. Mam wrażenie, że powyższy algorytm jest lepszy od klasycznego, ponieważ mnożenie ma tendencję do przywracania utraty precyzji odejmowania. Gdy jest ograniczony do używania pływaków, tak jak w przypadku GPU, może to znacząca różnica.

EDIT: "Obszar trójkątów i wielokątów 2D & 3D" opisuje jeszcze bardziej efektywną metodę

// "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;

Ta strona pokazuje, że wzór

Można uprościć do:

Jeśli napiszesz kilka terminów i pogrupujesz je według wspólnych czynników xi, równość nie jest trudna do zauważenia.

Ostateczne podsumowanie jest bardziej efektywne, ponieważ wymaga tylko n mnożenia zamiast 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

Nauczyłem się tego uproszczenia od Joe Kingtona, tutaj .

Jeśli masz NumPy, ta wersja jest szybciej (dla wszystkich ale bardzo małych tablic):

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

Zbiór punktów bez innych ograniczeń niekoniecznie jednoznacznie definiuje wielokąt.

Więc najpierw musisz zdecydować, jaki wielokąt zbudować z tych punktów-może wypukły kadłub? http://en.wikipedia.org/wiki/Convex_hull

Następnie triangulować i obliczyć obszar. http://www.mathopenref.com/polygonirregulararea.html

Aby rozszerzyć obszary trójkąta triangulate i sum, działają one, jeśli zdarzy ci się mieć wielokąt wypukły lub zdarzy ci się wybrać punkt, który nie generuje linii do każdego innego punktu przecinającego wielokąt.

Dla ogólnego wielokąta nie przecinającego się, należy zsumować iloczyn krzyżowy wektorów (punkt odniesienia, punkt a), (punkt odniesienia, punkt b), gdzie a i b są "następne" względem siebie.

Zakładając, że masz listę punktów definiujących wielokąt w kolejności (kolejność będąc punktami i I + 1 tworzą linię wielokąta):

Suma (iloczyn krzyżowy ((punkt 0, punkt i), (punkt 0, punkt i + 1)) dla i = 1 do n - 1.

Weź wielkość tego iloczynu krzyżowego i masz pole powierzchni.

To obsłuży wklęsłe wielokąty bez konieczności martwienia się o Wybór dobrego punktu odniesienia; wszelkie trzy punkty, które generują trójkąt, który nie znajduje się wewnątrz wielokąta, będą miały iloczyn poprzeczny, który wskazuje w przeciwnym kierunku trójkąta, który jest wewnątrz wielokąta, więc obszary są sumowane poprawnie.

Aby obliczyć obszar wielokąta

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=b-a;
    bc=c-b;
    return ab.x*bc.y-ab.y*bc.x;
}    
double area(vct p[],int n)
{ 
    int ar=0;
    for(i=1;i+1<n;i++)
    {
        vct a=p[i]-p[0];
        vct b=p[i+1]-p[0];
        area+=cross(a,b);
    }
    return abs(area/2.0);
}    

Lub wykonać całkę konturową. Twierdzenie Stokesa pozwala wyrazić całkę obszaru jako całkę konturową. Mała kwadratura Gaussa i Bob jest Twoim wujkiem.

Jednym ze sposobów, by to zrobić, byłoby rozłożyć wielokąt na Trójkąty, obliczyć obszar trójkątów i przyjąć sumę jako obszar wielokąta.

1. Ustaw punkt bazowy (najbardziej wypukły punkt). To będzie twój punkt obrotu trójkątów.
2. Oblicz najbardziej lewy punkt (dowolny), inny niż twój punkt bazowy.
3. Oblicz drugi najbardziej lewy punkt, aby zakończyć Trójkąt.
4. zapisz ten trójkątny obszar.
5. Przesuń o jeden punkt w prawo każdej iteracji.
6. suma obszarów triangulowanych

Lepsze od sumowania trójkątów jest sumowanie trapezoidów w przestrzeni kartezjańskiej:

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

Rozwiązanie niezależne od języka:

Dany: wielokąt może być zawsze złożony przez N-2 trójkąty, które nie nakładają się na siebie (n = liczba punktów lub boków). 1 trójkąt = 3 wielokąt jednostronny = 1 Trójkąt; 1 kwadrat = 4 wielokąt jednostronny = 2 Trójkąty; itd.]}

Dlatego wielokąt może być zredukowany przez" odcięcie " trójkątów, a powierzchnia całkowita będzie sumą obszarów tych trójkątów. spróbuj z kartką papieru i nożyczkami, najlepiej jest, jeśli ca Wizualizacji procesu przed pójściem za nim.

Jeśli weźmiesz dowolne 3 kolejne punkty na ścieżce wielokątów i utworzysz trójkąt z tymi punktami, będziesz miał JEDEN i tylko jeden z trzech możliwych scenariuszy:

1. powstały trójkąt jest całkowicie wewnątrz oryginalnego wielokąta
2. powstały trójkąt jest całkowicie poza oryginalnym wielokątem
3. powstały trójkąt jest częściowo zawarty w oryginalnym wielokątu

Interesują nas tylko przypadki, które wchodzą w pierwszą opcję (całkowicie zawarte).

Za każdym razem, gdy znajdujemy jeden z nich, odcinamy go, obliczamy jego powierzchnię (łatwe, nie wyjaśniamy tu wzoru) i tworzymy nowy wielokąt o jednej stronie mniejszej (odpowiednik wielokąta z tym trójkątem odciętym). dopóki nie zostanie nam tylko jeden trójkąt.

Jak zaimplementować ten program:

Utwórz tablicę (kolejnych) punktów, które reprezentują ścieżkę wokół wielokąta. zacznij od punktu 0. Uruchom tablicę tworząc Trójkąty (jeden po drugim) z punktów x, x + 1 i x+2. przekształć każdy trójkąt z kształtu na obszar i przecinaj go z obszarem utworzonym z wielokąta. Jeśli powstałe przecięcie jest identyczne z pierwotnym trójkątem, to trójkąt ten jest całkowicie zawarty w wielokątu i można go odciąć. Usuń x + 1 z tablicy i zacznij od x=0. w przeciwnym wypadku (jeśli trójkąt znajduje się poza [częściowo lub całkowicie] wielokątem), należy przejść do następnego punktu x+1 w tablicy.

DODATKOWO jeśli chcesz zintegrować z mapowaniem i zaczynasz z geopunktów najpierw musisz przekonwertować z geopunktów na punkty ekranowe. wymaga to podjęcia decyzji o modelowaniu i formułowaniu kształtu Ziemi (choć mamy tendencję do myślenia o Ziemi jako kuli, jest to w rzeczywistości nieregularna jajowata (jajowata), z wgnieceniami). istnieje wiele modeli tam, dla dalszych info wiki. ważną kwestią jest to, czy uznasz obszar za płaszczyznę lub za zakrzywiony. ogólnie rzecz biorąc, "małe" obszary, gdzie punkty znajdują się w odległości do kilku km, Nie wygenerują znaczących błąd, jeśli rozważymy planarne, a nie wypukłe.

Implementacja wzoru sznurowadła może być wykonana w Numpy. Zakładając te wierzchołki:

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

Możemy zdefiniować następującą funkcję, aby znaleźć obszar:

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

I uzyskanie wyników:

print PolyArea(x,y)
# 0.26353377782163534

Unikanie pętli powoduje, że funkcja ta jest ~50x szybsza niż 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

Uwaga: napisałem tę odpowiedź na inne pytanie , wspomniałem o tym tutaj, aby mieć pełną listę rozwiązań.

Moją skłonnością byłoby po prostu zacząć wycinać Trójkąty. Nie rozumiem, jak cokolwiek innego mogłoby uniknąć bycia strasznie włochatym.

Weź trzy kolejne punkty, które składają się na wielokąt. Upewnij się, że kąt jest mniejszy niż 180. Teraz masz nowy trójkąt, który nie powinien być problemem do obliczenia, Usuń punkt środkowy z listy punktów wielokąta. Powtarzaj, aż zostaną Ci tylko trzy punkty.

C sposób wykonania:

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

    for (int i = 0; i<numVerts; i++){
        v2 = verts[(i + 1) % numVerts];
        area += verts[i].x*v2.y - verts[i].y*v2.x;
    }

    return area / 2.0f;
}

Kod Pythona

Jak opisano tutaj: http://www.wikihow.com/Calculate-the-Area-of-a-Polygon

Z pand

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

Podam kilka prostych funkcji do obliczania powierzchni wielokąta 2d. Działa to zarówno dla wielokątów wypukłych, jak i wklęsłych. po prostu dzielimy wielokąt na wiele pod-trójkątów.

//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 a.x*b.y-a.y*b.x;
}

double area(Point * vertices, int n){  //n is number of sides
  double sum=0.0;
  for(i=0; i<n; i++){
    sum+=cp(vertices[i], vertices[(i+1)%n]); //%n is for last triangle
  }
  return abs(sum)/2.0;
}