Wie kann man feststellen, ob eine Liste von Polygonpunkten im Uhrzeigersinn angeordnet ist?

Einige der vorgeschlagenen Methoden werden fehlschlagen, in dem Fall einer nicht-konvexen polygon, wie ein Halbmond. Hier ist eine einfache, nicht-konvexe Polygone (es werden auch arbeiten mit einer sich selbst schneidenden polygon, wie eine Abbildung-acht, sagen Sie, ob es meistens im Uhrzeigersinn).

Summe über die Kanten (x₂ − x₁)(y₂ + y₁). Wenn das Ergebnis positiv ist die Kurve wird im Uhrzeigersinn, wenn es negativ wird die Kurve gegen den Uhrzeigersinn. (Das Ergebnis ist das doppelte der geschlossenen Fläche, mit einer +/- übereinkommens.)

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

InformationsquelleAutor der Antwort Beta

Ich denke, das ist eine ziemlich alte Frage, aber ich werde werfen eine andere Lösung trotzdem zu, weil es unkompliziert und mathematisch nicht intensiv - es werden einfache algebra. Die Berechnung der signierten Fläche des Polygons. Wenn es negativ ist, werden die Punkte im Uhrzeigersinn angeordnet, wenn Sie positiv sind Sie gegen den Uhrzeigersinn. (Dies ist sehr ähnlich zur Beta-Lösung.)

Berechnung der signierten Fläche:
A = 1/2 * (x₁*y₂ - x₂*y₁ + x₂*y₃ - x₃*y₂ + ... + x_n*y₁ - x₁*y_n)

Oder in pseudo-code:

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

Beachten Sie, dass wenn Sie nur die überprüfung der Bestellung, Sie brauchen nicht zu stören, geteilt durch 2.

Quellen: http://mathworld.wolfram.com/PolygonArea.html

InformationsquelleAutor der Antwort Sean the Bean

Finden, der vertex mit der kleinsten y (und größten x, wenn es Unentschieden). Lassen Sie den Scheitelpunkt sein A und die nächsten vertices in der Liste werden B und C. Nun berechnen Sie die Unterschreiben der das Kreuzprodukt von AB und AC.

Referenzen:

• Wie finde ich die Ausrichtung eines einfachen Polygons? in
  Häufig Gestellte Fragen: comp.Grafik.algorithmen.

• Kurvenausrichtung bei Wikipedia.

InformationsquelleAutor der Antwort lhf

Für was es Wert ist, habe ich dieses mixin zu berechnen, die Wicklung um für die Google Maps API v3-apps.

Den code nutzt die Nebenwirkung von polygon-Flächen: eine im Uhrzeigersinn gewundene Reihenfolge der Eckpunkte ergibt einen positiven Bereich, während eine Zähler-im Uhrzeigersinn-Wicklung, um die gleichen Ecken produziert auf der gleichen Fläche wie einen negativen Wert. Der code verwendet auch eine Art private-API in der Google-Maps-geometrie-Bibliothek. Ich fühlte mich bequem, es zu benutzen - Verwendung auf eigene Gefahr.

Beispiel für die Nutzung:

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

Vollständiges Beispiel mit unit-tests @ 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;
  }
})();

InformationsquelleAutor der Antwort Steve Jansen

Als auch erläutert in diesem Wikipedia-Artikel Kurvenausrichtungdie 3 Punkte pq und r auf der Ebene (also mit x-und y-Koordinaten), können Sie berechnen Sie das Vorzeichen der folgenden Determinante

Wenn die Determinante negativ ist (d.h. Orient(p, q, r) < 0), dann das polygon orientiert sich im Uhrzeigersinn (CW). Wenn die Determinante positiv ist (d.h. Orient(p, q, r) > 0), die polygon-orientiert gegen den Uhrzeigersinn (CCW). Die Determinante ist null (D. H. Orient(p, q, r) == 0) wenn die Punkte pq und r sind kollinear.

In der Formel oben, wir stellen diejenigen vor, die die Koordinaten der pq und r weil wir mit homogene Koordinaten.

InformationsquelleAutor der Antwort Ian

Denke ich in Ordnung für ein paar Punkte, die gegeben werden, im Uhrzeigersinn alle Kanten müssen positiv sein, nicht nur die Summe der Kanten. Wenn eine Kante ist negativ als mindestens 3 Punkte werden gegen den Uhrzeigersinn.

InformationsquelleAutor der Antwort daniel

Dies ist meine Lösung mit den Erklärungen in den anderen Antworten:

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

InformationsquelleAutor der Antwort Gianni Spear

Nach der Prüfung mehrere unzuverlässig Implementierungen des Algorithmus zufriedenstellende Ergebnisse in Bezug auf das CW - /CCW-Orientierung aus der box war das eine, geschrieben von OP in diese thread (shoelace_formula_3).

Wie immer, eine positive Zahl steht für einen CW-Orientierung, in der Erwägung, dass eine negative Zahl nach Links.

InformationsquelleAutor der Antwort Marjan Moderc

Andere Lösung für dieses;

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

Nehmen alle Eckpunkte als ein array wie dieses;

const vertices = [{x: 5, y: 0}, {x: 6, y: 4}, {x: 4, y: 5}, {x: 1, y: 5}, {x: 1, y: 0}];
isClockwise(vertices);

InformationsquelleAutor der Antwort Ind

finden Sie die Mitte der Masse diese Punkte.

nehme an, es sind die Linien von diesem Punkt um Ihre Punkte.

finden Sie den Winkel zwischen zwei Linien, die für line0 line1

als es für line1 und line2

...

...

wenn dieser Winkel ist streng monoton Steigend, als es gegen den Uhrzeigersinn ,

else if monoton abnehmend, es ist im Uhrzeigersinn

anderen (es ist nicht monotonical)

you cant entscheiden, so ist es nicht klug,

InformationsquelleAutor der Antwort ufukgun