Jak ustalić, czy lista punktów wielokąta jest zgodna z ruchem wskazówek zegara?

259

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).

Stécy
źródło
4
UWAGA: Akceptowana odpowiedź i wiele odpowiedzi po niej wymaga wielu dodatków i mnożenia (są oparte na obliczeniach powierzchni, które kończą się ujemnie lub dodatnio; np. „Formuła sznurowadła”). Przed wdrożeniem jednego z nich rozważ odpowiedź lhf , która jest prostsza / szybsza - w oparciu o wiki - orientacja prostego wielokąta .
ToolmakerSteve
Zawsze myślę o tym w kategoriach iloczynu krzyżowego dwóch sąsiednich wektorów. Gdy przechodzę po obwodzie wielokąta, moja głowa wskazuje na płaszczyznę. Przecinam wektor poza płaszczyzną do mojego wektora kierunku chodzenia, aby uzyskać trzeci kierunek w moim układzie współrzędnych. Jeśli ten wektor wskazuje tak, że wnętrze jest po mojej lewej stronie, jest przeciwny do ruchu wskazówek zegara; jeśli wnętrze jest po mojej prawej stronie, to zgodnie z ruchem wskazówek zegara.
duffymo

Odpowiedzi:

416

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ą +/-).

point[0] = (5,0)   edge[0]: (6-5)(4+0) =   4
point[1] = (6,4)   edge[1]: (4-6)(5+4) = -18
point[2] = (4,5)   edge[2]: (1-4)(5+5) = -30
point[3] = (1,5)   edge[3]: (1-1)(0+5) =   0
point[4] = (1,0)   edge[4]: (5-1)(0+0) =   0
                                         ---
                                         -44  counter-clockwise
Beta
źródło
28
Rachunek różniczkowy stosuje się do prostego przypadku. (Nie mam umiejętności publikowania grafiki.) Obszar pod segmentem linii jest równy jego średniej wysokości (y2 + y1) / 2-krotności jego długości poziomej (x2-x1). Zwróć uwagę na konwencję znaków w x. Wypróbuj to z kilkoma trójkątami, a wkrótce zobaczysz, jak to działa.
Beta
72
Drobne zastrzeżenie: ta odpowiedź zakłada normalny kartezjański układ współrzędnych. Powodem, o którym warto wspomnieć, jest to, że niektóre typowe konteksty, takie jak płótno HTML5, używają odwróconej osi Y. Następnie reguła musi zostać odwrócona: jeśli obszar jest ujemny , krzywa jest zgodna z ruchem wskazówek zegara.
LarsH
8
@ Mr.Qbs: Więc moja metoda działa, ale jeśli pominiesz istotną część , to nie zadziała. To nie jest wiadomość.
Beta
11
@ Mr.Qbs: Zawsze musisz połączyć ostatni punkt z pierwszym. Jeśli masz N punktów ponumerowanych od 0 do N-1, musisz obliczyć: 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.
Olivier Jacot-Descombes
4
Ten blog.element84.com/polygon-winding.html wyjaśnia w prostym języku angielskim, dlaczego to rozwiązanie działa.
David Zorychta
49

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:

Using your data:
point[0] = (5, 0)
point[1] = (6, 4)
point[2] = (4, 5)
point[3] = (1, 5)
point[4] = (1, 0)

Więc Wytwórnia krawędzie kolejno jak
edgeAto segment od point0do point1i
edgeBpomiędzy point1do point2
...
edgeEznajduje się pomiędzy point4i point0.

Zatem wierzchołek A ( point0) znajduje się między
edgeE[Od point4do point0]
edgeA[Od point0do `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) i
edgeA= point1- point0= (6, 4) - (1, 0)= (5, 4) i

A 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, i k). 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:

 i    j    k 
-4    0    0
 1    4    0    

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 kskładnik (lub oś Z).
Wzór na obliczenie wielkości kskładnika w osi Z wynosi
a1*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.

Charles Bretana
źródło
3
W rzeczywistości to rozwiązanie jest inne niż rozwiązanie przyjęte. Czy są one równoważne, czy nie, to pytanie, które badam, ale podejrzewam, że nie są ... Przyjęta odpowiedź oblicza obszar wielokąta, biorąc różnicę między obszarem pod górną krawędzią wielokąta a obszarem pod dolna krawędź wielokąta. Jeden będzie negatywny (ten, w którym przechodzisz od lewej do prawej), a drugi będzie ujemny. Podczas ruchu w prawo górna krawędź jest przesuwana od lewej do prawej i jest większa, więc suma jest dodatnia.
Charles Bretana,
1
Moje rozwiązanie mierzy sumę sinusów zmian kątów krawędzi na każdym wierzchołku. Będzie to miało wartość dodatnią podczas ruchu w kierunku zgodnym z ruchem wskazówek zegara, a ujemne podczas ruchu w kierunku przeciwnym do ruchu wskazówek zegara.
Charles Bretana,
2
Wydaje się, że przy takim podejściu musisz wziąć arcsin, chyba że przyjmiesz wypukłość (w takim przypadku potrzebujesz tylko jednego wierzchołka)
agentp
2
Musisz wziąć arcsin. Wypróbuj kilka losowych, niewypukłych wielokątów, a przekonasz się, że test zakończy się niepowodzeniem dla niektórych wielokątów, jeśli nie weźmiesz arcsin.
Luke Hutchison
1
@CharlesBretana - chociaż nie przeprowadziłem testu Luke'a, uważam, że ma rację. Taka jest natura sumowania w połączeniu ze skalą nieliniową [bez arcsin vs. arcsin]. Zastanów się, co sugerował marsbear, że poprawnie odrzuciłeś. Zasugerował, że „po prostu liczyć”, i wskazałeś, że garść dużych wartości może przeważyć dużą liczbę małych wartości. Teraz rozważ arcsin dla każdej wartości vs nie. Czy nadal nie jest tak, że nieprzyjmowanie arcsin przypisuje niewłaściwą wagę każdej wartości, dlatego ma tę samą wadę (choć znacznie mniejszą)?
ToolmakerSteve
47

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:

signedArea = 0
for each point in points:
    x1 = point[0]
    y1 = point[1]
    if point is last point
        x2 = firstPoint[0]
        y2 = firstPoint[1]
    else
        x2 = nextPoint[0]
        y2 = nextPoint[1]
    end if

    signedArea += (x1 * y2 - x2 * y1)
end for
return signedArea / 2

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

Sean the Bean
źródło
Czy to była literówka w powyższej formule podpisanego obszaru? Kończy się na „xn * y1 - x1 * yn”; kiedy uważam, że powinno to być „x_n y_ {n + 1} - y_n x_ {n-1}” (przynajmniej w LaTeX). Z drugiej strony minęło dziesięć lat, odkąd wziąłem lekcje algebry liniowej.
Michael Eric Oberlin,
Nie. Jeśli sprawdzisz źródło , zobaczysz, że formuła faktycznie odwołuje się do pierwszego punktu w ostatnim terminie (y1 i x1). (Przepraszam, nie znam się na LaTeX-ie, ale sformatowałem indeksy, aby były bardziej czytelne.)
Sean the Bean
Użyłem tego rozwiązania i działało idealnie na mój użytek. Zauważ, że jeśli możesz planować z wyprzedzeniem i rezerwować i dodawać dwa wektory w swojej tablicy, możesz pozbyć się porównania (lub%), dodając pierwszy wektor na końcu tablicy. W ten sposób po prostu zapętlasz wszystkie elementy, z wyjątkiem ostatniego (długość-2 zamiast długości-1).
Eric Fortier
2
@EricFortier - FWIW, zamiast zmieniać rozmiar możliwie dużej tablicy, skuteczną alternatywą jest zapisywanie punktu dla każdej iteracji jak previousPointprzy następnej iteracji. Przed uruchomieniem pętli ustaw previousPointostatni punkt tablicy. Kompromis to dodatkowa lokalna kopia zmiennych, ale mniejszy dostęp do tablicy. A co najważniejsze, nie musisz dotykać tablicy wejściowej.
ToolmakerSteve
2
@MichaelEricOberlin - konieczne jest zamknięcie wielokąta poprzez włączenie segmentu linii od ostatniego punktu do pierwszego punktu. (Prawidłowe obliczenia będą takie same, bez względu na to, który punkt rozpoczyna zamknięty wielokąt).
ToolmakerSteve
36

Znajdź wierzchołek o najmniejszym y (i największym x, jeśli istnieją powiązania). Niech wierzchołek będzie, Aa poprzedni wierzchołek na liście będzie, Ba następny wierzchołek na liście będzie C. Teraz obliczyć znak iloczynu krzyżowego ABi AC.


Bibliografia:

lhf
źródło
7
Jest to również wyjaśnione w en.wikipedia.org/wiki/Curve_orientation . Chodzi o to, że znaleziony punkt musi znajdować się na wypukłym kadłubie i wystarczy spojrzeć lokalnie na pojedynczy punkt na wypukłym kadłubie (i jego bezpośrednich sąsiadach), aby określić orientację całego wielokąta.
M Katz
1
Zszokowany i zachwycony nie otrzymał więcej głosów poparcia. W przypadku prostych wielokątów ( które w większości pól są najbardziej wielokątami ) ta odpowiedź daje O(1)rozwiązanie. Wszystkie pozostałe odpowiedzi dają O(n)rozwiązania dla nliczby punktów wielokąta. Aby uzyskać jeszcze głębsze optymalizacje, zobacz podsekcję Rozważania praktyczne w fantastycznym artykule Wikipedii na temat krzywej .
Cecil Curry
8
Wyjaśnienie: to rozwiązanie występujeO(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.
Cecil Curry
1
@CecilCurry Myślę, że Twój drugi komentarz wyjaśnia, dlaczego nie otrzymał więcej głosów pozytywnych. Daje błędne odpowiedzi w niektórych scenariuszach, bez wzmianki o tych ograniczeniach.
LarsH
23

Oto prosta implementacja algorytmu C # na podstawie tej odpowiedzi .

Załóżmy, że mamy Vectortyp mający Xi Ywłaściwości typu double.

public bool IsClockwise(IList<Vector> vertices)
{
    double sum = 0.0;
    for (int i = 0; i < vertices.Count; i++) {
        Vector v1 = vertices[i];
        Vector v2 = vertices[(i + 1) % vertices.Count];
        sum += (v2.X - v1.X) * (v2.Y + v1.Y);
    }
    return sum > 0.0;
}

%jest operatorem modulo lub reszty wykonującym operację modulo, która ( według Wikipedii ) znajduje resztę po podzieleniu jednej liczby przez drugą.

Olivier Jacot-Descombes
źródło
6

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.

Steve Gilham
źródło
Zważywszy na to, że iloczyn krzyżowy sprowadza się do dodatniego współczynnika skalowania pomnożonego przez sinus kąta, prawdopodobnie lepiej jest po prostu zrobić iloczyn krzyżowy. Będzie to szybsze i mniej skomplikowane.
ReaperUnreal
4

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:

var myPolygon = new google.maps.Polygon({/*options*/});
var isCW = myPolygon.isPathClockwise();

Pełny przykład z testami jednostkowymi @ http://jsfiddle.net/stevejansen/bq2ec/

/** Mixin to extend the behavior of the Google Maps JS API Polygon type
 *  to determine if a polygon path has clockwise of counter-clockwise winding order.
 *  
 *  Tested against v3.14 of the GMaps API.
 *
 *  @author  [email protected]
 *
 *  @license http://opensource.org/licenses/MIT
 *
 *  @version 1.0
 *
 *  @mixin
 *  
 *  @param {(number|Array|google.maps.MVCArray)} [path] - an optional polygon path; defaults to the first path of the polygon
 *  @returns {boolean} true if the path is clockwise; false if the path is counter-clockwise
 */
(function() {
  var category = 'google.maps.Polygon.isPathClockwise';
     // check that the GMaps API was already loaded
  if (null == google || null == google.maps || null == google.maps.Polygon) {
    console.error(category, 'Google Maps API not found');
    return;
  }
  if (typeof(google.maps.geometry.spherical.computeArea) !== 'function') {
    console.error(category, 'Google Maps geometry library not found');
    return;
  }

  if (typeof(google.maps.geometry.spherical.computeSignedArea) !== 'function') {
    console.error(category, 'Google Maps geometry library private function computeSignedArea() is missing; this may break this mixin');
  }

  function isPathClockwise(path) {
    var self = this,
        isCounterClockwise;

    if (null === path)
      throw new Error('Path is optional, but cannot be null');

    // default to the first path
    if (arguments.length === 0)
        path = self.getPath();

    // support for passing an index number to a path
    if (typeof(path) === 'number')
        path = self.getPaths().getAt(path);

    if (!path instanceof Array && !path instanceof google.maps.MVCArray)
      throw new Error('Path must be an Array or MVCArray');

    // negative polygon areas have counter-clockwise paths
    isCounterClockwise = (google.maps.geometry.spherical.computeSignedArea(path) < 0);

    return (!isCounterClockwise);
  }

  if (typeof(google.maps.Polygon.prototype.isPathClockwise) !== 'function') {
    google.maps.Polygon.prototype.isPathClockwise = isPathClockwise;
  }
})();
Steve Jansen
źródło
Próbując tego, otrzymuję dokładnie odwrotny wynik: wielokąt narysowany w kolejności zgodnej z ruchem wskazówek zegara daje pole ujemne, a jeden narysowany w kierunku przeciwnym daje dodatnie. W obu przypadkach ten fragment jest nadal bardzo przydatny po 5 latach, dziękuję.
Cameron Roberts,
@CameronRoberts Normą (patrz IETF w szczególności dla geoJson) jest przestrzeganie „reguły prawej ręki”. Myślę, że Google narzeka. W takim przypadku pierścień zewnętrzny musi być skierowany przeciwnie do ruchu wskazówek zegara (aby uzyskać dodatni obszar), a pierścienie wewnętrzne (otwory) nawijają się zgodnie z ruchem wskazówek zegara (obszar ujemny należy usunąć z głównego obszaru).
allez l'OM
4

Implementacja odpowiedzi Seana w JavaScript:

function calcArea(poly) {
    if(!poly || poly.length < 3) return null;
    let end = poly.length - 1;
    let sum = poly[end][0]*poly[0][1] - poly[0][0]*poly[end][1];
    for(let i=0; i<end; ++i) {
        const n=i+1;
        sum += poly[i][0]*poly[n][1] - poly[n][0]*poly[i][1];
    }
    return sum;
}

function isClockwise(poly) {
    return calcArea(poly) > 0;
}

let poly = [[352,168],[305,208],[312,256],[366,287],[434,248],[416,186]];

console.log(isClockwise(poly));

let poly2 = [[618,186],[650,170],[701,179],[716,207],[708,247],[666,259],[637,246],[615,219]];

console.log(isClockwise(poly2));

Jestem pewien, że to prawda. Wygląda na to że działa :-)

Te wielokąty wyglądają tak, jeśli zastanawiasz się:

mpen
źródło
3

Jest to zaimplementowana funkcja dla OpenLayers 2 . Warunkiem posiadania wielokąta zgodnego z ruchem wskazówek zegara jest area < 0to potwierdzone przez to odniesienie .

function IsClockwise(feature)
{
    if(feature.geometry == null)
        return -1;

    var vertices = feature.geometry.getVertices();
    var area = 0;

    for (var i = 0; i < (vertices.length); i++) {
        j = (i + 1) % vertices.length;

        area += vertices[i].x * vertices[j].y;
        area -= vertices[j].x * vertices[i].y;
        // console.log(area);
    }

    return (area < 0);
}
MSS
źródło
Openlayers jest biblioteką do zarządzania mapami opartą na javascript, taką jak googlemaps, i jest napisana i używana w openlayers 2.
MSS
Czy możesz wyjaśnić trochę, co robi Twój kod i dlaczego to robisz?
nbro
@nbro ten kod implementuje odpowiedź LHF . Łatwo jest zachować część nie OpenLayer w czystej funkcji javascript, mając wierzchołki bezpośrednio jako parametr. Działa dobrze i można go dostosować do przypadku multiPolygon .
allez l'OM
2

Jeśli używasz Matlaba, funkcja ispolycwzwraca true, jeśli wierzchołki wielokąta są w kolejności zgodnej z ruchem wskazówek zegara.

Frederick
źródło
1

Jak wyjaśniono również w tym artykule Wikipedia orientacji Curve , biorąc pod uwagę 3 punkty p, qa rna płaszczyźnie (tj z X i Y), można obliczyć znak następującym wyznacznika

wprowadź opis zdjęcia tutaj

Jeś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) == 0Jeśli punkty p) qi rwspółliniowe .

We wzorze powyżej, dołączana te przed współrzędnych p, q i rdlatego korzysta jednorodne współrzędnych .

Ian
źródło
@tibetty Czy możesz wyjaśnić, dlaczego ta metoda nie zadziała w wielu sytuacjach, jeśli wielokąt jest wklęsły?
nbro
1
Proszę spojrzeć na ostatnią tabelę w referencji pozycji wiki w swoim poście. Łatwo jest mi podać fałszywy przykład, ale trudno to udowodnić.
tybet
1
Proszę spojrzeć na ostatnią tabelę w referencji pozycji wiki w swoim poście. Łatwo jest mi podać fałszywy przykład, ale trudno to udowodnić.
tybet
1
@tibetty jest poprawny. Nie można po prostu wziąć trzech punktów wzdłuż wielokąta; możesz znajdować się w obszarze wypukłym lub wklęsłym tego wielokąta. Uważnie czytając wiki, należy wziąć trzy punkty wzdłuż wypukłego kadłuba otaczającego wielokąt . Z „rozważań praktycznych”: „Nie trzeba budować wypukłego kadłuba wielokąta, aby znaleźć odpowiedni wierzchołek. Powszechnym wyborem jest wierzchołek wielokąta o najmniejszej współrzędnej X. Jeśli jest ich kilka, ten jeden z najmniejszą współrzędną Y jest wybierana. Gwarantuje to, że jest to [a] wierzchołek wypukłego kadłuba wielokąta. "
ToolmakerSteve
1
Stąd wcześniejsza odpowiedź lhf , która jest podobna i odwołuje się do tego samego artykułu wiki, ale określa taki punkt. [Najwyraźniej nie ma znaczenia, czy bierze się najmniejszą, czy największą, x lub y, o ile unika się bycia w środku; efektywnie pracujemy od jednej krawędzi obwiedni wokół wielokąta, aby zagwarantować w regionie wklęsłym.]
ToolmakerSteve
0

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.

Daniel
źródło
To prawda, ale źle rozumiesz pojęcie kolejności uzwojenia wielokąta (zgodnie z ruchem wskazówek zegara lub przeciwnie do ruchu wskazówek zegara). W całkowicie wypukłym wielokącie kąt we wszystkich punktach będzie zgodny z ruchem wskazówek zegara lub wszystkie będą przeciwne do ruchu wskazówek zegara [jak w pierwszym zdaniu]. W wielokącie z wklęsłym obszarem (regionami) „jaskinie” będą w przeciwnym kierunku, ale wielokąt jako całość nadal ma dobrze zdefiniowane wnętrze i jest odpowiednio rozpatrywany zgodnie z ruchem wskazówek zegara lub przeciwnie do ruchu wskazówek zegara. Zobacz en.wikipedia.org/wiki/…
ToolmakerSteve
0

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ę.

using System.Collections.Generic;
using System.Linq;
using System.Numerics;

namespace SolidworksAddinFramework.Geometry
{
    public static class PlanePolygon
    {
        /// <summary>
        /// Assumes that polygon is closed, ie first and last points are the same
        /// </summary>
       public static bool Orientation
           (this IEnumerable<Vector3> polygon, Vector3 up)
        {
            var sum = polygon
                .Buffer(2, 1) // from Interactive Extensions Nuget Pkg
                .Where(b => b.Count == 2)
                .Aggregate
                  ( Vector3.Zero
                  , (p, b) => p + Vector3.Cross(b[0], b[1])
                                  /b[0].Length()/b[1].Length());

            return Vector3.Dot(up, sum) > 0;

        } 

    }
}

z testem jednostkowym

namespace SolidworksAddinFramework.Spec.Geometry
{
    public class PlanePolygonSpec
    {
        [Fact]
        public void OrientationShouldWork()
        {

            var points = Sequences.LinSpace(0, Math.PI*2, 100)
                .Select(t => new Vector3((float) Math.Cos(t), (float) Math.Sin(t), 0))
                .ToList();

            points.Orientation(Vector3.UnitZ).Should().BeTrue();
            points.Reverse();
            points.Orientation(Vector3.UnitZ).Should().BeFalse();



        } 
    }
}
bradgonesurfing
źródło
0

Oto moje rozwiązanie, korzystając z wyjaśnień w innych odpowiedziach:

def segments(poly):
    """A sequence of (x,y) numeric coordinates pairs """
    return zip(poly, poly[1:] + [poly[0]])

def check_clockwise(poly):
    clockwise = False
    if (sum(x0*y1 - x1*y0 for ((x0, y0), (x1, y1)) in segments(poly))) < 0:
        clockwise = not clockwise
    return clockwise

poly = [(2,2),(6,2),(6,6),(2,6)]
check_clockwise(poly)
False

poly = [(2, 6), (6, 6), (6, 2), (2, 2)]
check_clockwise(poly)
True
Włócznia Gianni
źródło
1
Czy możesz określić, na jakich innych odpowiedziach opiera się dokładnie ta odpowiedź?
nbro
0

Znacznie prostsza obliczeniowo metoda, jeśli znasz już punkt wewnątrz wielokąta :

  1. Wybierz dowolny segment linii z oryginalnego wielokąta, punktów i ich współrzędnych w tej kolejności.

  2. Dodaj znany punkt „wewnętrzny” i utwórz trójkąt.

  3. Oblicz CW lub CCW zgodnie z sugestią tutaj z tymi trzema punktami.

Venkata Goli
źródło
Może to działa, jeśli wielokąt jest całkowicie wypukły. Zdecydowanie nie jest wiarygodny, jeśli istnieją jakieś wklęsłe regiony - łatwo jest wybrać punkt, który znajduje się po „złej” stronie jednej z krawędzi jaskini, a następnie połączyć go z tą krawędzią. Dostanie złą odpowiedź.
ToolmakerSteve
Działa, nawet jeśli wielokąt jest wklęsły. Punkt musi znajdować się w tym wklęsłym wielokącie. Nie jestem jednak pewien złożonego wielokąta (nie testowałem.)
Venkata Goli
„Działa, nawet jeśli wielokąt jest wklęsły”. - Przeciwprzykład: poli (0,0), (1,1), (0,2), (2,2), (2,0). Segment linii (1,1), (0, 2). Jeśli wybierzesz punkt wewnętrzny w (1,1), (0,2), (1,2), aby utworzyć trójkąt -> (1,1), (0,2), (0,5,1,5)), otrzymasz przeciwne uzwojenie niż w przypadku wybrania punktu wewnętrznego w granicach (0,0), (1,1), (1,0)> (1,1), (0,2), (0,5,0,5). Oba są wewnętrzne względem pierwotnego wielokąta, ale mają przeciwne uzwojenia. Dlatego jeden z nich podaje złą odpowiedź.
ToolmakerSteve
Zasadniczo, jeśli wielokąt ma dowolny region wklęsły, wybierz segment w regionie wklęsłym. Ponieważ jest wklęsły, możesz znaleźć dwa „wewnętrzne” punkty, które znajdują się po przeciwnych stronach tej linii. Ponieważ są one po przeciwnych stronach tej linii, uformowane trójkąty mają przeciwne uzwojenia. Koniec dowodu.
ToolmakerSteve,
0

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.

Marjan Moderc
źródło
0

Oto szybkie rozwiązanie 3.0 oparte na powyższych odpowiedziach:

    for (i, point) in allPoints.enumerated() {
        let nextPoint = i == allPoints.count - 1 ? allPoints[0] : allPoints[i+1]
        signedArea += (point.x * nextPoint.y - nextPoint.x * point.y)
    }

    let clockwise  = signedArea < 0
Toby Evetts
źródło
0

Kolejne rozwiązanie tego;

const isClockwise = (vertices=[]) => {
    const len = vertices.length;
    const sum = vertices.map(({x, y}, index) => {
        let nextIndex = index + 1;
        if (nextIndex === len) nextIndex = 0;

        return {
            x1: x,
            x2: vertices[nextIndex].x,
            y1: x,
            y2: vertices[nextIndex].x
        }
    }).map(({ x1, x2, y1, y2}) => ((x2 - x1) * (y1 + y2))).reduce((a, b) => a + b);

    if (sum > -1) return true;
    if (sum < 0) return false;
}

Weź wszystkie wierzchołki jako tablicę taką jak ta;

const vertices = [{x: 5, y: 0}, {x: 6, y: 4}, {x: 4, y: 5}, {x: 1, y: 5}, {x: 1, y: 0}];
isClockwise(vertices);
Ind
źródło
0

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):

coords <- cbind(x = c(5,6,4,1,1),y = c(0,4,5,5,0))
a <- numeric()
for (i in 1:dim(coords)[1]){
  #print(i)
  q <- i + 1
  if (i == (dim(coords)[1])) q <- 1
  out <- ((coords[q,1]) - (coords[i,1])) * ((coords[q,2]) + (coords[i,2]))
  a[q] <- out
  rm(q,out)
} #end i loop

rm(i)

a <- sum(a) #-ve is anti-clockwise

b <- cbind(x = rev(coords[,1]), y = rev(coords[,2]))

if (a>0) coords <- b #reverses coords if polygon not traced in anti-clockwise direction
dez
źródło
0

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.

if (nte[0] >= prv[0] && nxt[0] >= nte[0]) return(CW);
if (nte[0] <= prv[0] && nxt[0] <= nte[0]) return(CCW);
// Okay, it's not easy-peasy, so now, do the math
if (nte[0] * nxt[1] - nte[1] * nxt[0] - prv[0] * (nxt[1] - crt[1]) + prv[1] * (nxt[0] - nte[0]) >= 0) return(CCW); // For quadrant 3 return(CW)
return(CW) // For quadrant 3 return (CCW)
VectorVortec
źródło
IMHO, bezpieczniej byłoby trzymać się podstawowej matematyki pokazanej w odpowiedzi LHF - dziękuję, że o nim wspomniałeś. Wyzwaniem w zmniejszeniu go do ćwiartek jest to, że sporo pracy wymaga udowodnienia, że twoja formuła jest poprawna we wszystkich przypadkach. Czy poprawnie obliczyłeś „więcej zachodu”? Czy w wklęsłym wielokącie, gdzie zarówno [1], jak i [3] znajdują się „na zachód i południe” od [2]? Czy w tej sytuacji prawidłowo obsługiwałeś różne długości [1] i [3]? Nie mam pojęcia, ale jeśli bezpośrednio obliczę ten kąt (lub jego wyznacznik), używam dobrze znanych wzorów.
ToolmakerSteve
@Toolmaker Steruj instrukcjami if zawsze działają, jeśli 3 punkty są wypukłe. Instrukcje if zostaną zwrócone, a następnie otrzymasz prawidłową odpowiedź. Instrukcje if nie powrócą, jeśli kształt będzie wklęsły i skrajny. To wtedy musisz wykonać matematykę. Większość obrazów ma jeden kwadrant, więc ta część jest łatwa. Ponad 99% moich wywołań podprogramów jest obsługiwanych przez instrukcje if.
VectorVortec,
To nie dotyczy mojej obawy. Co to za formuła? Czy to determinant orientacji podany w linku wiki z odpowiedzi lhf? Jeśli tak, to powiedz tak. Wyjaśnij, że robisz szybkie kontrole, które obsługują większość przypadków, aby uniknąć standardowej matematyki. Jeśli tak, to twoja odpowiedź ma dla mnie sens. (Drobna nit: byłby łatwiejszy do odczytania, gdybyś używał .xi .ystruktury, zamiast [0]i [1]. Nie wiedziałem, co mówi twój kod, po raz pierwszy na niego spojrzałem.)
ToolmakerSteve
Ponieważ nie miałem zaufania do twojego podejścia, wdrożyłem podejście LHF ; formuła z jego linku. Część wolna znajduje odpowiednie wyszukiwanie wierzchołków - O (N). Po znalezieniu wyznacznikiem jest operacja O (1), wykorzystująca 6 mnożeń z 5 dodaniami. Ta ostatnia część jest tym, co zoptymalizowałeś; ale zrobiliście to, dodając dodatkowe testy wstępne. Nie mogę osobiście uzasadnić przyjęcia niestandardowego podejścia - musiałbym sprawdzić, czy każdy krok jest prawidłowy - Ale dziękuję za ciekawą analizę kwadrantów!
ToolmakerSteve
0

Kod C # do implementacji odpowiedzi lhf :

// https://en.wikipedia.org/wiki/Curve_orientation#Orientation_of_a_simple_polygon
public static WindingOrder DetermineWindingOrder(IList<Vector2> vertices)
{
    int nVerts = vertices.Count;
    // If vertices duplicates first as last to represent closed polygon,
    // skip last.
    Vector2 lastV = vertices[nVerts - 1];
    if (lastV.Equals(vertices[0]))
        nVerts -= 1;
    int iMinVertex = FindCornerVertex(vertices);
    // Orientation matrix:
    //     [ 1  xa  ya ]
    // O = | 1  xb  yb |
    //     [ 1  xc  yc ]
    Vector2 a = vertices[WrapAt(iMinVertex - 1, nVerts)];
    Vector2 b = vertices[iMinVertex];
    Vector2 c = vertices[WrapAt(iMinVertex + 1, nVerts)];
    // determinant(O) = (xb*yc + xa*yb + ya*xc) - (ya*xb + yb*xc + xa*yc)
    double detOrient = (b.X * c.Y + a.X * b.Y + a.Y * c.X) - (a.Y * b.X + b.Y * c.X + a.X * c.Y);

    // TBD: check for "==0", in which case is not defined?
    // Can that happen?  Do we need to check other vertices / eliminate duplicate vertices?
    WindingOrder result = detOrient > 0
            ? WindingOrder.Clockwise
            : WindingOrder.CounterClockwise;
    return result;
}

public enum WindingOrder
{
    Clockwise,
    CounterClockwise
}

// Find vertex along one edge of bounding box.
// In this case, we find smallest y; in case of tie also smallest x.
private static int FindCornerVertex(IList<Vector2> vertices)
{
    int iMinVertex = -1;
    float minY = float.MaxValue;
    float minXAtMinY = float.MaxValue;
    for (int i = 0; i < vertices.Count; i++)
    {
        Vector2 vert = vertices[i];
        float y = vert.Y;
        if (y > minY)
            continue;
        if (y == minY)
            if (vert.X >= minXAtMinY)
                continue;

        // Minimum so far.
        iMinVertex = i;
        minY = y;
        minXAtMinY = vert.X;
    }

    return iMinVertex;
}

// Return value in (0..n-1).
// Works for i in (-n..+infinity).
// If need to allow more negative values, need more complex formula.
private static int WrapAt(int i, int n)
{
    // "+n": Moves (-n..) up to (0..).
    return (i + n) % n;
}
ToolmakerSteve
źródło
1
Wydaje się, że dotyczy to współrzędnych Y w dół. Odwróć CW / CCW dla standardowych współrzędnych.
Warwick Allison
0

Oto prosta implementacja języka Python 3 oparta na tej odpowiedzi (która z kolei oparta jest na rozwiązaniu zaproponowanym w zaakceptowanej odpowiedzi )

def is_clockwise(points):
    # points is your list (or array) of 2d points.
    assert len(points) > 0
    s = 0.0
    for p1, p2 in zip(points, points[1:] + [points[0]]):
        s += (p2[0] - p1[0]) * (p2[1] + p1[1])
    return s > 0.0
nbro
źródło
-4

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

ufukgun
źródło
przez „środek masy” Myślę, że masz na myśli „centroid”?
Vicky Chijwani,
Prawdopodobnie działa, jeśli wielokąt jest całkowicie wypukły. Ale lepiej zamiast tego użyć odpowiedzi, która zadziała dla wielokątów niewypukłych.
ToolmakerSteve