Wyobraź sobie, że masz wielokąt zdefiniowany przez zestaw współrzędnych a jego środek masy wynosi . Można traktować wielokąt jako rozkład równomierny z granicą wielokąta.
Poszukuję metody, która znajdzie macierz kowariancji wielokąta .
Podejrzewam, że macierz kowariancji wielokąta jest ściśle związana z drugim momentem pola , ale nie jestem pewien, czy są one równoważne. Wzory znajdujące się w artykule w Wikipedii, który połączyłem, wydają się (przypuszczam, że nie jest to dla mnie szczególnie jasne z artykułu) odwoływać się do bezwładności obrotowej wokół osi x, y zamiast z głównych osi wielokąta.
(Nawiasem mówiąc, jeśli ktoś może wskazać mi, jak obliczyć główne osie wielokąta, byłoby to również przydatne)
Kuszące jest po prostu wykonanie PCA na współrzędnych , ale powoduje to, że współrzędne niekoniecznie są równomiernie rozmieszczone wokół wielokąta, a zatem nie są reprezentatywne dla gęstości wielokąta. Skrajnym przykładem jest zarys Północnej Dakoty, której wielokąt jest zdefiniowany przez dużą liczbę punktów wzdłuż rzeki Czerwonej, a także tylko dwa kolejne punkty określające zachodnią krawędź stanu.
źródło
Odpowiedzi:
Najpierw zróbmy analizę.
Załóżmy, że w obrębie wielokąta jego gęstość prawdopodobieństwa jest funkcją proporcjonalną Zatem stała proporcjonalności jest odwrotnością całki nad wielokątem,P p(x,y). p
Środka ciężkości wielokąta jest punktem średnich współrzędnych, obliczony jako pierwszych chwil. Pierwszy to
Bezwładnościowy napinacz może być przedstawiony jako symetryczny tablicy drugich momentów obliczane po przeliczeniu wielokąta umieścić jej środka ciężkości w punkcie początkowym, to znaczy w matrycy centralnych drugich momentów
gdzie wynoszą od do do Sam tensor - inaczej macierz kowariancji - jest(k,l) (2,0) (1,1) (0,2).
PCA od otrzymuje się główne osie z są to wektory jednostkowe skalowane przez ich wartości własnych.I(P) P:
Następnie sprawdźmy, jak wykonać obliczenia. Ponieważ wielokąt jest przedstawiany jako sekwencja wierzchołków opisujących jego zorientowaną granicę naturalne jest wywoływanie∂P,
Na przykład, z i stałą ( tj. Jednolitą) gęstością możemy (przez inspekcję) wybrać jedną z wielu rozwiązania, takie jakdω=xkyldxdy p, ω(x,y)=−1l+1xkyl+1dx.
Chodzi o to, że całka konturu podąża za segmentami linii wyznaczonymi przez sekwencję wierzchołków. Każdy segment linii od wierzchołka do wierzchołka można sparametryzować za pomocą zmiennej rzeczywistej w postaciu v t
gdzie to normalny kierunek jednostki od doWartości wahają się zatem od do Pod tą parametryzacją i są liniowymi funkcjami i a są liniowymi funkcjami Tak więc podcałkową całki konturu na każdej krawędzi zostaje funkcja wielomianowa od , która jest łatwo ocenione dla małych iw∝v−u u v. t 0 |v−u|. x y t dx dy dt. t, k l.
Wdrożenie tej analizy jest tak proste, jak kodowanie jej komponentów. Na najniższym poziomie potrzebujemy funkcji do zintegrowania wielomianowej formy jednoczęściowej na segmencie linii. Funkcje wyższego poziomu agregują je, aby obliczyć momenty surowe i centralne w celu uzyskania barycentrum i tensora bezwładnościowego, a na koniec możemy działać na tym tensorze, aby znaleźć główne osie (które są jego skalowanymi wektorami własnymi). Poniższy
R
kod wykonuje tę pracę. Nie ma żadnych pretensji do wydajności: ma on jedynie zilustrować praktyczne zastosowanie powyższej analizy. Każda funkcja jest prosta, a konwencje nazewnictwa są zbieżne z konwencjami analizy.Kod zawiera procedurę generowania prawidłowych zamkniętych, po prostu połączonych, nie przecinających się wielokątów (przez losowe deformowanie punktów wzdłuż koła i dołączenie początkowego wierzchołka jako jego ostatniego punktu w celu utworzenia zamkniętej pętli). Poniżej znajduje się kilka instrukcji do wykreślenia wielokąta, wyświetlenia jego wierzchołków, przylegania do centrum środka i wykreślenia głównych osi w kolorze czerwonym (największym) i niebieskim (najmniejszym), tworząc układ współrzędnych zorientowany dodatnio na wielokąt.
źródło
Edycja: Nie zauważyłem, że whuber już odpowiedział. Zostawię to jako przykład innego (być może mniej eleganckiego) podejścia do problemu.
Macierz kowariancji
Niech za losową z rozkładu równomiernego na wieloboku z obszaru . Macierz kowariancji to:(X,Y) P A
gdzie to wariancja , to wariancja , a to kowariancja między i . Zakłada to średnią zerową, ponieważ środek masy wielokąta znajduje się na początku. Rozkład równomierny przypisuje stałą gęstość prawdopodobieństwa do każdego punktu w , więc:CXX=E[X2] X CYY=E[Y2] Y CXY=E[XY] X Y 1A P
Triangulacja
Zamiast próbować bezpośrednio zintegrować skomplikowany region, taki jak , możemy uprościć problem, dzieląc na trójkątnych podregionów:P P n
W twoim przykładzie jeden z możliwych partycjonowania wygląda następująco:
Istnieją różne sposoby uzyskania triangulacji (patrz tutaj ). Na przykład, możesz obliczyć triangulację wierzchołków Delaunaya , a następnie odrzucić krawędzie, które wypadają poza (ponieważ może nie być wypukłe jak w przykładzie).P
Całki powyżej można następnie podzielić na sumy całek w trójkątach:P
Trójkąt ma ładne, proste granice, więc te całki są łatwiejsze do oceny.
Całkowanie przez trójkąty
Istnieją różne sposoby integracji nad trójkątami. W tym przypadku zastosowałem lewę, która polega na odwzorowaniu trójkąta na kwadrat jednostki. Przekształcenie w barycentryczne współrzędne może być lepszym rozwiązaniem.
Oto rozwiązania dla całek powyżej, dla dowolnego trójkąta zdefiniowanego przez wierzchołki . Pozwolić:T (x1,y1),(x2,y2),(x3,y3)
Następnie:
Składając wszystko w całość
Niech i zawierają X / Y współrzędne wierzchołków każdego trójkąta , jak opisano powyżej. Podłącz do dla każdego trójkąta, zwracając uwagę, że warunki obszaru anulują się. To daje rozwiązanie:vix viy Ti (3) (2)
Główne osie
Główne osie podane są przez wektory własne macierzy kowariancji , podobnie jak w PCA. W przeciwieństwie do PCA, mamy analityczne wyrażenie dla , zamiast konieczności szacowania go z próbkowanych punktów danych. Zauważ, że same wierzchołki nie są reprezentatywną próbką z jednorodnego rozkładu na , więc nie można po prostu pobrać przykładowej macierzy kowariancji wierzchołków. Ale * jest * stosunkowo prostą funkcją wierzchołków, jak widać w .C C P C (4)
źródło