Jak ustalić, czy lista punktów wielokąta jest w kolejności zgodnej z ruchem wskazówek zegara?

Iloczyn krzyżowymierzy stopień prostopadłości dwóch wektorów. Wyobraź sobie, że każda krawędź twojego wielokąta jest wektorem w płaszczyźnie X-y trójwymiarowej (3-D) przestrzeni xyz. Wtedy iloczyn krzyżowy dwóch kolejnych krawędzi jest wektorem w kierunku z, (dodatni z-kierunek, jeśli drugi segment jest zgodny z ruchem wskazówek zegara, minus z-kierunek, jeśli jest przeciwny do ruchu wskazówek zegara). Wielkość tego wektora jest proporcjonalna do sinusa kąta między dwoma oryginalnymi krawędziami, więc osiąga maksimum, gdy są prostopadłe, i zwęża się, aby zniknąć, gdy krawędzie są kolinearne (równoległe).

Więc dla każdego wierzchołka (punktu) wielokąta Oblicz wielkość iloczynu krzyżowego dwóch przylegających 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 Oznacz krawędzie kolejno jako
edgeA jest segmentem od point0 do point1 oraz
edgeB od point1 do point2
...
edgeE jest pomiędzy point4 A point0.

Wtedy wierzchołek a (point0) jest pomiędzy
edgeE [od point4 to point0]
edgeA [od point0 do 'point1'

Te dwie krawędzie są same w sobie wektorami, których współrzędne X i y można wyznaczyć odejmując współrzędne ich punktów początkowych i końcowych:

edgeE = point0 - point4 = (1, 0) - (5, 0) = (-4, 0) oraz
edgeA = point1 - point0 = (6, 4) - (1, 0) = (5, 4) oraz

I iloczyn poprzeczny tych dwóch przylegających krawędzi oblicza się za pomocą wyznacznika poniższej macierzy, którą konstruuje się poprzez umieszczenie współrzędnych dwa wektory poniżej symboli reprezentujących trzy osi współrzędnych(i, j, & k). W związku z tym, że pojęcie iloczynu krzyżowego jest trójwymiarową konstrukcją, rozszerzamy te wektory 2-D na trójwymiarową współrzędną, aby zastosować iloczyn 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 mnożonych, wyznacznik powyższej macierzy ma tylko k, (lub oś z) składową.
Na wzór na obliczenie wielkości k lub elementu osi z wynosi
a1*b2 - a2*b1 = -4* 4 - 0* 1 = -16

Wielkość tej wartości (-16) jest miarą sinusa kąta między 2 oryginalnymi wektorami, pomnożoną przez iloczyn wielkości 2 wektorów.
Właściwie inną formułą jej wartości jest
A X B (Cross Product) = |A| * |B| * sin(AB).

Więc, aby wrócić do tylko miary kąta trzeba podzielić tę wartość, (-16), przez iloczyn wielkości dwóch wektory.

|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 jest wygięty w lewo lub w prawo, i o ile. Nie ma potrzeby, aby wziąć Arc-sinus. 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 na każdym wierzchołku..

Jeśli ostateczna suma jest dodatnia, poszedłeś zgodnie z ruchem wskazówek zegara, ujemnie, przeciwnie do ruchu wskazówek zegara.

Myślę, że to dość stare pytanie, ale i tak wyrzucę inne rozwiązanie, ponieważ jest proste i nie matematycznie intensywne - wykorzystuje tylko podstawową algebrę. Oblicz podpisaną powierzchnię wielokąta. Jeśli jest ujemne, punkty są w porządku zgodnym z ruchem wskazówek zegara, jeśli jest dodatnie, są przeciwnie do ruchu wskazówek zegara. (Jest to bardzo podobne do rozwiązania Beta.)

Oblicz obszar podpisany: A = 1/2 * (x₁*y₂ - x₂*y₁ + x₂*y₃ - x₃*y₂ + ... + x _n * y₁ - x₁*y _n )

Lub w pseudo-kodzie:

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

Zauważ, że jeśli sprawdzasz tylko zamówienie, nie musisz się martwić dzieleniem przez 2.

Źródła: http://mathworld.wolfram.com/PolygonArea.html

Oto prosta implementacja algorytmu w C# oparta na tej odpowiedzi .

Załóżmy, że mamy typ Vector mający X i Y wł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]; // % is the modulo operator
        sum += (v2.X - v1.X) * (v2.Y + v1.Y);
    }
    return sum > 0.0;
}

Znajdź wierzchołek z najmniejszym y (i największym x, jeśli istnieją powiązania). Niech wierzchołek będzie A, a kolejne wierzchołki na liście będą B i C. Teraz Oblicz znak iloczynu krzyżowego AB i AC.

Bibliografia:

• Jak znaleźć orientację prostego wielokąta? w Często zadawane pytania: comp.grafika.algorytmy .

• Curve orientation w Wikipedii.

Zacznij od jednego z wierzchołków i Oblicz kąt nachylenia każdej strony.

Pierwszy i ostatni będą równe zeru (więc pomiń je); dla reszty sinus kąta będzie podany przez iloczyn krzyżowy normalizacji na jednostkę długości (punkt[n]-Punkt[0]) i (punkt[n-1]-punkt [0]).

Jeśli suma wartości jest dodatnia, to Twój wielokąt jest rysowany w sensie przeciwnym do ruchu wskazówek zegara.

Jeśli to coś warte, użyłem tego mixinu do obliczenia krętej kolejności dla aplikacji Google Maps API v3.

Kod wykorzystuje efekt uboczny obszarów wielokątów: zgodnie z ruchem wskazówek zegara kolejność nawijania wierzchołków daje pole dodatnie, podczas gdy kolejność nawijania w kierunku przeciwnym do ruchu wskazówek zegara tych samych wierzchołków wytwarza ten sam obszar jako wartość ujemną. Kod używa również swego rodzaju prywatnego API w bibliotece geometrii Map Google. Czułem się komfortowo używając go-używaj na własne ryzyko.

Próbka sposób użycia:

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

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

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

Jeśli używasz Matlab, Funkcja ispolycw zwraca true, jeśli wierzchołki wielokątów są w kolejności zgodnej z ruchem wskazówek zegara.

Jak wyjaśniono również w tym artykule Wikipedii orientacja krzywej, podano 3 punkty p, q i r na płaszczyźnie (tj. ze współrzędnymi x i y) można obliczyć znak następującego wyznacznika

Jeśli wyznacznik jest ujemny (tj. Orient(p, q, r) < 0), to 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 jest zerowy (tzn. Orient(p, q, r) == 0), Jeśli punkty p, q and r are collinear .

W powyższym wzorze poprzedzamy te przed współrzędnymi p, q i r ponieważ używamy współrzędnych jednorodnych.

Jest to zaimplementowana funkcja dla OpenLayers 2 . Warunkiem posiadania wielokąta zgodnego z ruchem wskazówek zegara jest area < 0, co potwierdza 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);
}

Myślę, że aby niektóre punkty były podane zgodnie z ruchem wskazówek zegara, wszystkie krawędzie muszą być dodatnie, a nie tylko suma krawędzi. Jeśli jedna krawędź jest ujemna, to co najmniej 3 punkty są podane w kierunku przeciwnym do ruchu wskazówek zegara.

Moje rozwiązanie C # / LINQ jest oparte na poradach cross product @ charlesbretana poniżej. Można określić normę odniesienia dla uzwojenia. Powinien działać tak długo, jak długo krzywa znajduje się głównie w płaszczyźnie określonej przez wektor up.

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();



        } 
    }
}

To jest moje rozwiązanie, używając 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

O wiele prostsza metoda obliczeniowa, jeśli znasz już punkt wewnątrz wielokąta:

1. Wybierz dowolny odcinek linii z oryginalnego wielokąta, punkty i ich współrzędne w tej kolejności.

2. Dodaj znany punkt "wewnątrz" i uformuj Trójkąt.

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

Po przetestowaniu kilku nierzetelnych implementacji, algorytm, który dostarczył zadowalające wyniki dotyczące orientacji CW / CCW po wyjęciu z pudełka, został opublikowany przez OP w this thread (shoelace_formula_3).

Jak zawsze, liczba dodatnia reprezentuje orientację CW, podczas gdy liczba ujemna CCW.

Oto rozwiązanie swift 3.0 na podstawie powyższych odpowiedzi:

    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

Inne 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);

Rozwiązanie dla R do określenia kierunku i do tyłu, jeśli zgodnie z ruchem wskazówek zegara (okazało się konieczne dla obiektów owin):

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

Znajdź środek masy tych punktów.

Załóżmy, że są linie od tego punktu do Twoich punktów.

Znajdź kąt między dwoma liniami dla line0 line1

Than do it for line1 and line2

...

...

Jeśli kąt ten jest monotonicznie zwiększający się niż jest przeciwnie do ruchu wskazówek zegara,

Else jeśli monotonicznie maleje to zgodnie z ruchem wskazówek zegara

Else (nie jest monotoniczny)

Nie możesz zdecydować, więc to nie jest mądre