Zakładając serię punktów w przestrzeni 2d, które nie przecinają się same, jaka jest skuteczna metoda wyznaczania pola powierzchni powstałego wielokąta?
Na marginesie, to nie jest praca domowa i nie szukam kodu. Szukam opisu, który mógłbym wykorzystać do wdrożenia własnej metody. Mam pomysły na wyciągnięcie sekwencji trójkątów z listy punktów, ale wiem, że jest kilka przypadków krawędzi dotyczących wielokątów wypukłych i wklęsłych, których prawdopodobnie nie złapię.
Odpowiedzi:
Oto standardowa metoda AFAIK. Zasadniczo zsumuj iloczyny poprzeczne wokół każdego wierzchołka. Znacznie prostsze niż triangulacja.
Kod Pythona, biorąc pod uwagę wielokąt reprezentowany jako lista współrzędnych wierzchołków (x, y), niejawnie zawijający się od ostatniego wierzchołka do pierwszego:
David Lehavi komentuje: Warto wspomnieć, dlaczego ten algorytm działa: Jest to aplikacja twierdzenia Greena dla funkcji −y i x; dokładnie tak, jak działa planymetr . Dokładniej:
Wzór powyżej =
integral_over_perimeter(-y dx + x dy) =
integral_over_area((-(-dy)/dy+dx/dx) dy dx) =
2 Area
źródło
abs()
usuwa wylogowanie.Produkt krzyżowy to klasyk.
Jeśli masz do wykonania milion takich obliczeń, wypróbuj następującą zoptymalizowaną wersję, która wymaga o połowę mniej mnożeń:
Dla przejrzystości używam indeksu tablicy. Bardziej efektywne jest używanie wskaźników. Chociaż dobrzy kompilatorzy zrobią to za Ciebie.
Zakłada się, że wielokąt jest „zamknięty”, co oznacza, że kopiujesz pierwszy punkt jako punkt z indeksem dolnym N. Zakłada się również, że wielokąt ma parzystą liczbę punktów. Dołącz dodatkową kopię pierwszego punktu, jeśli N nie jest parzyste.
Algorytm uzyskuje się poprzez rozwinięcie i połączenie dwóch kolejnych iteracji klasycznego algorytmu krzyżowego.
Nie jestem pewien, jak oba algorytmy porównują się pod względem dokładności numerycznej. Mam wrażenie, że powyższy algorytm jest lepszy od klasycznego, ponieważ mnożenie ma tendencję do przywracania utraty precyzji odejmowania. W przypadku ograniczenia do używania pływaków, tak jak w przypadku GPU, może to mieć znaczący wpływ.
EDYCJA: „Obszar trójkątów i wielokątów 2D i 3D” opisuje jeszcze wydajniejszą metodę
źródło
Ta strona pokazuje, że formuła
można uprościć do:
Jeśli napiszesz kilka terminów i pogrupujesz je według wspólnych czynników
xi
, nie jest trudno zauważyć równość.Końcowe sumowanie jest bardziej wydajne, ponieważ wymaga tylko
n
mnożenia zamiast2n
.Nauczyłem się tego uproszczenia od Joe Kingtona tutaj .
Jeśli masz NumPy, ta wersja jest szybsza (dla wszystkich oprócz bardzo małych tablic):
źródło
Zestaw punktów bez żadnych innych ograniczeń niekoniecznie musi jednoznacznie definiować 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 wykonaj triangulację i oblicz obszar. http://www.mathopenref.com/polygonirregulararea.html
źródło
Aby rozszerzyć obszary trójkątów i trójkątów sumujących, działają one, jeśli zdarzy się, że masz wypukły wielokąt LUB wybierzesz punkt, który nie generuje linii do każdego innego punktu przecinającego wielokąt.
W przypadku ogólnego nieprzecinającego się wielokąta należy zsumować iloczyn poprzeczny wektorów (punkt odniesienia, punkt a), (punkt odniesienia, punkt b), gdzie aib są „obok” siebie.
Zakładając, że masz listę punktów, które definiują wielokąt w kolejności (kolejność, w której punkty i i i + 1 tworzą linię wielokąta):
Suma (iloczyn poprzeczny ((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.
Pozwoli to obsłużyć wklęsłe wielokąty bez martwienia się o wybranie dobrego punktu odniesienia; dowolne trzy punkty, które generują trójkąt, który nie znajduje się wewnątrz wielokąta, będą miały iloczyn poprzeczny wskazujący w przeciwnym kierunku niż dowolny trójkąt wewnątrz wielokąta, więc obszary zostaną poprawnie zsumowane.
źródło
Aby obliczyć pole wielokąta
źródło
Lub wykonaj całkę konturową. Twierdzenie Stokesa pozwala wyrazić całkę powierzchniową jako całkę konturową. Trochę kwadratury Gaussa i Bob jest twoim wujem.
źródło
rozwiązanie niezależne od języka:
PODANE: wielokąt może ZAWSZE składać się z n-2 trójkątów, które nie zachodzą na siebie (n = liczba punktów LUB boków). 1 trójkąt = wielokąt trójstronny = 1 trójkąt; 1 kwadrat = wielokąt czteroboczny = 2 trójkąty; etc ad mdłości QED
dlatego też wielokąt można zmniejszyć przez „ucinanie” trójkątów, a całkowita powierzchnia będzie sumą powierzchni tych trójkątów. wypróbuj to za pomocą kartki papieru i nożyczek, najlepiej wizualizować proces przed wykonaniem.
jeśli weźmiesz dowolne 3 kolejne punkty na ścieżce wielokąta i utworzysz trójkąt z tymi punktami, będziesz mieć jeden i tylko jeden z trzech możliwych scenariuszy:
interesują nas tylko przypadki, które mieszczą się w pierwszej opcji (całkowicie zawarte).
za każdym razem, gdy znajdujemy jeden z nich, odcinamy go, obliczamy jego powierzchnię (łatwy peasy, nie wyjaśniam tutaj wzoru) i tworzymy nowy wielokąt z jednym bokiem mniej (odpowiednik wielokąta z odciętym trójkątem). dopóki nie zostanie nam tylko jeden trójkąt.
jak zaimplementować to programowo:
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 (po jednym naraz) z punktów x, x + 1 i x + 2. przekształć każdy trójkąt z kształtu w obszar i przetnij go z obszarem utworzonym z wielokąta. JEŻELI wynikowe przecięcie jest identyczne z oryginalnym trójkątem, wówczas wspomniany trójkąt jest całkowicie zawarty w wielokącie i można go odciąć. usuń x + 1 z tablicy i zacznij ponownie od x = 0. w przeciwnym razie (jeśli trójkąt jest na zewnątrz [częściowo lub całkowicie] wielokąta), przejdź do następnego punktu x + 1 w tablicy.
dodatkowo, jeśli chcesz zintegrować się z mapowaniem i zaczynasz od punktów geograficznych, najpierw musisz dokonać konwersji z punktów geograficznych na punkty ekranowe. wymaga to ustalenia modelu i wzoru na kształt ziemi (chociaż myślimy o ziemi jako kuli, w rzeczywistości jest to nieregularny jajo (kształt jajka) z wgnieceniami). istnieje wiele modeli, aby uzyskać więcej informacji na wiki. Ważną kwestią jest to, czy uznasz ten obszar za płaszczyznę, czy za zakrzywiony. Ogólnie rzecz biorąc, „małe” obszary, w których punkty są oddalone od siebie do kilku kilometrów, nie będą generować znaczącego błędu, jeśli uznamy je za płaskie, a nie wypukłe.
źródło
Jednym ze sposobów byłoby rozłożenie wielokąta na trójkąty , obliczenie powierzchni trójkątów i potraktowanie sumy jako powierzchni wielokąta.
źródło
źródło
Lepsze niż sumowanie trójkątów jest sumowanie trapezów w przestrzeni kartezjańskiej:
źródło
Implementację formuły Shoelace można było wykonać w Numpy. Zakładając te wierzchołki:
Aby znaleźć pole, możemy zdefiniować następującą funkcję:
I uzyskiwanie wyników:
Unikanie pętli sprawia, że ta funkcja jest ~ 50X szybsza niż
PolygonArea
:Uwaga: napisałem tę odpowiedź na inne pytanie , wspominam o tym tutaj, aby mieć pełną listę rozwiązań.
źródło
Wolałabym po prostu zacząć odcinać trójkąty. Nie widzę, jak cokolwiek innego mogłoby uniknąć okropnego owłosienia.
Weź trzy kolejne punkty, które składają się na wielokąt. Upewnij się, że kąt jest mniejszy niż 180. Masz teraz nowy trójkąt, którego obliczenie nie powinno stanowić problemu, usuń środkowy punkt z listy punktów wielokąta. Powtarzaj, aż pozostaną tylko trzy punkty.
źródło
C sposób na zrobienie tego:
źródło
Kod Pythona
Jak opisano tutaj: http://www.wikihow.com/Calculate-the-Area-of-a-Polygon
Z pandami
źródło
źródło
cp
przyjmuje dwa argumenty, a jednak wywołujesz to jednym.