Mając listę punktów, jak znaleźć, czy są one w kolejności zgodnej z ruchem wskazówek zegara?
Na przykład:
point[0] = (5,0)
point[1] = (6,4)
point[2] = (4,5)
point[3] = (1,5)
point[4] = (1,0)
powiedziałby, że jest przeciwny do ruchu wskazówek zegara (lub w przypadku niektórych osób przeciwnie do ruchu wskazówek zegara).
Odpowiedzi:
Niektóre z sugerowanych metod zawiodą w przypadku wielokąta niewypukłego, takiego jak półksiężyc. Oto prosty, który będzie działał z wielokątami niewypukłymi (zadziała nawet z wielokątem przecinającym się jak ósemka, informując, czy jest to w większości zgodnie z ruchem wskazówek zegara).
Suma ponad krawędziami, (x 2 - x 1 ) (y 2 + y 1 ). Jeśli wynik jest dodatni, krzywa jest zgodna z ruchem wskazówek zegara, a jeśli jest ujemna, krzywa jest przeciwna do ruchu wskazówek zegara. (Wynikiem jest dwukrotność zamkniętego obszaru z konwencją +/-).
źródło
Sum( (x[(i+1) mod N] - x[i]) * (y[i] + y[(i+1) mod N]) )
dla i = 0 do N-1. Tzn. Musi mieć indeks Modulo N (N ≡ 0
) Formuła działa tylko dla zamkniętych wielokątów. Wieloboki nie mają wyimaginowanych krawędzi.Produkt przekroju mierzy stopień prostopadłej-ności dwóch wektorów. Wyobraź sobie, że każda krawędź twojego wielokąta jest wektorem w płaszczyźnie xy trójwymiarowej (3-D) przestrzeni xyz. Zatem iloczynem krzyżowym dwóch kolejnych krawędzi jest wektor w kierunku Z (dodatni kierunek Z, jeśli drugi segment jest zgodny z ruchem wskazówek zegara, minus kierunek Z, jeśli jest przeciwny do ruchu wskazówek zegara). Wielkość tego wektora jest proporcjonalna do sinusa kąta między dwiema oryginalnymi krawędziami, więc osiąga maksimum, gdy są one prostopadłe, i zwęża się, aby znikać, gdy krawędzie są współliniowe (równoległe).
Tak więc dla każdego wierzchołka (punktu) wielokąta oblicz wielkość iloczynu krzyżowego dwóch sąsiednich krawędzi:
Więc Wytwórnia krawędzie kolejno jak
edgeA
to segment odpoint0
dopoint1
iedgeB
pomiędzypoint1
dopoint2
...
edgeE
znajduje się pomiędzypoint4
ipoint0
.Zatem wierzchołek A (
point0
) znajduje się międzyedgeE
[Odpoint4
dopoint0
]edgeA
[Odpoint0
do `point1 'Te dwie krawędzie same są wektorami, których współrzędne xiy można określić, odejmując współrzędne ich punktów początkowego i końcowego:
edgeE
=point0
-point4
=(1, 0) - (5, 0)
=(-4, 0)
iedgeA
=point1
-point0
=(6, 4) - (1, 0)
=(5, 4)
iA iloczyn z tych dwóch przylegających krawędzi jest obliczana przy użyciu determinantę poniższej macierzy, która jest wykonana przez umieszczenie współrzędne dwóch wektorów poniżej symboli reprezentujących trzy oś współrzędnych (
i
,j
, ik
). Trzecia (zerowa) współrzędna wartościowana istnieje, ponieważ koncepcja produktu krzyżowego jest konstrukcją 3-D, dlatego rozszerzamy te wektory 2-D na 3-D, aby zastosować produkt krzyżowy:Biorąc pod uwagę, że wszystkie produkty krzyżowe wytwarzają wektor prostopadły do płaszczyzny dwóch wektorów, które są mnożone, wyznacznik powyższej macierzy ma tylko
k
składnik (lub oś Z).Wzór na obliczenie wielkości
k
składnika w osi Z wynosia1*b2 - a2*b1 = -4* 4 - 0* 1
=-16
Wielkość tej wartości (
-16
) jest miarą sinusoidy kąta między 2 oryginalnymi wektorami, pomnożonej przez iloczyn wielkości 2 wektorów.W rzeczywistości inna formuła dla jego wartości to
A X B (Cross Product) = |A| * |B| * sin(AB)
.Aby więc wrócić do miary kąta, należy podzielić tę wartość (
-16
) przez iloczyn wielkości dwóch wektorów.|A| * |B|
=4 * Sqrt(17)
=16.4924...
Więc miara grzechu (AB) =
-16 / 16.4924
=-.97014...
Jest to miara tego, czy następny segment po wierzchołku wygiął się w lewo lub w prawo i o ile. Nie ma potrzeby stosowania sinusoidy. Wszystko, na czym nam zależy, to jego wielkość i oczywiście jej znak (pozytywny lub negatywny)!
Zrób to dla każdego z pozostałych 4 punktów wokół zamkniętej ścieżki i dodaj wartości z tego obliczenia dla każdego wierzchołka.
Jeśli końcowa suma jest dodatnia, poszedłeś zgodnie z ruchem wskazówek zegara, ujemny, przeciwnie do ruchu wskazówek zegara.
źródło
Sądzę, że to dość stare pytanie, ale i tak zamierzam wyrzucić inne rozwiązanie, ponieważ jest proste i nie wymaga matematyki - używa tylko podstawowej algebry. Oblicz podpisany obszar wielokąta. Jeśli jest ujemny, punkty są w kolejności zgodnej z ruchem wskazówek zegara, a jeśli są dodatnie, są przeciwne do ruchu wskazówek zegara. (Jest to bardzo podobne do rozwiązania Beta.)
Oblicz podpisany obszar: A = 1/2 * (x 1 * y 2 - x 2 * y 1 + x 2 * y 3 - x 3 * y 2 + ... + x n * y 1 - x 1 * y n )
Lub w pseudokodzie:
Pamiętaj, że jeśli sprawdzasz tylko kolejność, nie musisz zawracać sobie głowy dzieleniem przez 2.
Źródła: http://mathworld.wolfram.com/PolygonArea.html
źródło
previousPoint
przy następnej iteracji. Przed uruchomieniem pętli ustawpreviousPoint
ostatni punkt tablicy. Kompromis to dodatkowa lokalna kopia zmiennych, ale mniejszy dostęp do tablicy. A co najważniejsze, nie musisz dotykać tablicy wejściowej.Znajdź wierzchołek o najmniejszym y (i największym x, jeśli istnieją powiązania). Niech wierzchołek będzie,
A
a poprzedni wierzchołek na liście będzie,B
a następny wierzchołek na liście będzieC
. Teraz obliczyć znak iloczynu krzyżowegoAB
iAC
.Bibliografia:
Jak znaleźć orientację prostego wielokąta? w często zadawanych pytaniach: comp.graphics.algorytmy .
Orientacja krzywej na Wikipedii.
źródło
O(1)
rozwiązanie. Wszystkie pozostałe odpowiedzi dająO(n)
rozwiązania dlan
liczby punktów wielokąta. Aby uzyskać jeszcze głębsze optymalizacje, zobacz podsekcję Rozważania praktyczne w fantastycznym artykule Wikipedii na temat krzywej .O(1)
tylko wtedy, gdy albo (A) ten wielokąt jest wypukły (w którym to przypadku dowolny dowolny wierzchołek znajduje się na wypukłym kadłubie, a zatem wystarczy) lub (B) znasz już wierzchołek o najmniejszej współrzędnej Y. Jeśli tak nie jest(tzn. Ten wielokąt nie jest wypukły i nic o nim nie wiesz),O(n)
wymagane jest wyszukiwanie. Ponieważ nie jest wymagane sumowanie, jest to jednak znacznie szybsze niż jakiekolwiek inne rozwiązanie dla prostych wielokątów.Oto prosta implementacja algorytmu C # na podstawie tej odpowiedzi .
Załóżmy, że mamy
Vector
typ mającyX
iY
właściwości typudouble
.%
jest operatorem modulo lub reszty wykonującym operację modulo, która ( według Wikipedii ) znajduje resztę po podzieleniu jednej liczby przez drugą.źródło
Zacznij od jednego z wierzchołków i obliczyć kąt z każdej strony.
Pierwszy i ostatni będzie wynosił zero (więc pomiń te); dla reszty, sinus kąta będzie podany przez iloczyn krzyżowy normalizacji do długości jednostkowej (punkt [n] -punkt [0]) i (punkt [n-1] -punkt [0]).
Jeśli suma wartości jest dodatnia, wówczas wielokąt jest rysowany w kierunku przeciwnym do ruchu wskazówek zegara.
źródło
Dla tego, co jest warte, użyłem tego miksu do obliczenia kolejności nawijania dla aplikacji Google Maps API v3.
Kod wykorzystuje efekt uboczny obszarów wielokątów: kolejność nawijania wierzchołków w kierunku zgodnym z ruchem wskazówek zegara daje obszar dodatni, natomiast kolejność nawijania w kierunku przeciwnym do ruchu wskazówek zegara tych samych wierzchołków daje ten sam obszar jako wartość ujemną. Kod korzysta również z pewnego rodzaju prywatnego interfejsu API w bibliotece geometrii Map Google. Czułem się komfortowo przy użyciu - używaj na własne ryzyko.
Przykładowe użycie:
Pełny przykład z testami jednostkowymi @ http://jsfiddle.net/stevejansen/bq2ec/
źródło
Implementacja odpowiedzi Seana w JavaScript:
Jestem pewien, że to prawda. Wygląda na to że działa :-)
Te wielokąty wyglądają tak, jeśli zastanawiasz się:
źródło
Jest to zaimplementowana funkcja dla OpenLayers 2 . Warunkiem posiadania wielokąta zgodnego z ruchem wskazówek zegara jest
area < 0
to potwierdzone przez to odniesienie .źródło
Jeśli używasz Matlaba, funkcja
ispolycw
zwraca true, jeśli wierzchołki wielokąta są w kolejności zgodnej z ruchem wskazówek zegara.źródło
Jak wyjaśniono również w tym artykule Wikipedia orientacji Curve , biorąc pod uwagę 3 punkty
p
,q
ar
na płaszczyźnie (tj z X i Y), można obliczyć znak następującym wyznacznikaJeśli wyznacznik jest ujemny (tj.
Orient(p, q, r) < 0
), Wówczas wielokąt jest zorientowany zgodnie z ruchem wskazówek zegara (CW). Jeśli wyznacznik jest dodatni (tj.Orient(p, q, r) > 0
), Wielokąt jest zorientowany przeciwnie do ruchu wskazówek zegara (CCW). Wyznacznik wynosi zero (tzn.Orient(p, q, r) == 0
Jeśli punktyp
)q
ir
są współliniowe .We wzorze powyżej, dołączana te przed współrzędnych
p
,q
ir
dlatego korzysta jednorodne współrzędnych .źródło
Myślę, że aby niektóre punkty były podawane zgodnie z ruchem wskazówek zegara, wszystkie krawędzie muszą być dodatnie, nie tylko suma krawędzi. Jeśli jedna krawędź jest ujemna, co najmniej 3 punkty zostaną podane przeciwnie do ruchu wskazówek zegara.
źródło
Moje rozwiązanie C # / LINQ opiera się na poradach dotyczących różnych produktów @charlesbretana poniżej. Możesz określić normalną wartość odniesienia dla uzwojenia. Powinno działać, dopóki krzywa znajduje się głównie w płaszczyźnie określonej przez wektor w górę.
z testem jednostkowym
źródło
Oto moje rozwiązanie, korzystając z wyjaśnień w innych odpowiedziach:
źródło
Znacznie prostsza obliczeniowo metoda, jeśli znasz już punkt wewnątrz wielokąta :
Wybierz dowolny segment linii z oryginalnego wielokąta, punktów i ich współrzędnych w tej kolejności.
Dodaj znany punkt „wewnętrzny” i utwórz trójkąt.
Oblicz CW lub CCW zgodnie z sugestią tutaj z tymi trzema punktami.
źródło
Po przetestowaniu kilku niewiarygodnych implementacji, algorytmem, który dostarczył zadowalające wyniki dotyczące orientacji CW / CCW po wyjęciu z pudełka, był ten opublikowany przez OP w tym wątku (
shoelace_formula_3
).Jak zawsze liczba dodatnia reprezentuje orientację CW, podczas gdy liczba ujemna CCW.
źródło
Oto szybkie rozwiązanie 3.0 oparte na powyższych odpowiedziach:
źródło
Kolejne rozwiązanie tego;
Weź wszystkie wierzchołki jako tablicę taką jak ta;
źródło
Rozwiązanie dla R, aby określić kierunek i odwrócić, jeśli jest zgodny z ruchem wskazówek zegara (uznał to za konieczne dla owin obiektów):
źródło
Chociaż te odpowiedzi są poprawne, są bardziej matematycznie intensywne niż to konieczne. Załóżmy współrzędne mapy, gdzie najbardziej wysunięty na północ punkt jest najwyższym punktem na mapie. Znajdź punkt na północy, a jeśli 2 punkty wiążą się, to jest to najbardziej na północ, a następnie na wschód (jest to punkt, który lhf używa w swojej odpowiedzi). W twoich punktach
punkt [0] = (5,0)
punkt [1] = (6,4)
punkt [2] = (4,5)
punkt [3] = (1,5)
punkt [4] = (1,0)
Jeśli założymy, że P2 jest najbardziej na północ, a następnie na wschód, to poprzedni lub następny punkt określ zgodnie z ruchem wskazówek zegara, CW lub CCW. Ponieważ najbardziej wysunięty na północ punkt znajduje się na północnej ścianie, jeśli P1 (poprzedni) do P2 przesuwa się na wschód, kierunek to CW. W tym przypadku porusza się na zachód, więc zgodnie z przyjętą odpowiedzią kierunek to CCW. Jeśli poprzedni punkt nie ma ruchu poziomego, wówczas ten sam system dotyczy następnego punktu, P3. Jeśli P3 jest na zachód od P2, to znaczy, że ruch jest w kierunku przeciwnym do ruchu wskazówek zegara. Jeśli ruch P2 do P3 odbywa się na wschód, w tym przypadku na zachód, ruch jest CW. Załóżmy, że nte, P2 w twoich danych, jest najbardziej na północ niż wschodni punkt, a prv to poprzedni punkt, P1 w twoich danych, a nxt to następny punkt, P3 w twoich danych, a [0] jest poziomy lub wschodni / zachód, gdzie zachód jest mniejszy niż wschód, a [1] jest pionowy.
źródło
.x
i.y
struktury, zamiast[0]
i[1]
. Nie wiedziałem, co mówi twój kod, po raz pierwszy na niego spojrzałem.)Kod C # do implementacji odpowiedzi lhf :
źródło
Oto prosta implementacja języka Python 3 oparta na tej odpowiedzi (która z kolei oparta jest na rozwiązaniu zaproponowanym w zaakceptowanej odpowiedzi )
źródło
znajdź środek masy tych punktów.
załóżmy, że są linie od tego punktu do twoich punktów.
znajdź kąt między dwiema liniami dla linii 0 linia1
niż zrób to dla linii 1 i linii 2
...
...
jeśli kąt ten rośnie monotonicznie niż w kierunku przeciwnym do ruchu wskazówek zegara,
w przeciwnym razie monotonicznie zmniejsza się zgodnie z ruchem wskazówek zegara
inaczej (to nie jest monotonne)
nie możesz zdecydować, więc nie jest to mądre
źródło