Wie kann ich effizient feststellen, ob ein Polygon konvex, nicht konvex oder komplex ist?

Können Sie die Dinge viel einfacher, als das Gift-Wrapping-Algorithmus... das ist eine gute Antwort, wenn Sie eine Reihe von Punkten, w/o jede bestimmte Grenze und müssen feststellen, dass die konvexe Hülle.

Im Gegensatz dazu betrachten wir den Fall, wo das polygon nicht selbst schneidet, und es besteht aus einem Satz von Punkten in einer Liste, wo die aufeinander folgenden Punkte bilden die Grenze. In diesem Fall ist es viel einfacher, um herauszufinden, ob ein polygon konvex ist oder nicht (und du musst Sie nicht berechnen Sie alle Winkel, entweder):

Für jedes aufeinander folgende paar von Kanten des Polygons (jedes Tripel der Punkte) berechnen Sie die z-Komponente des Kreuzprodukt der Vektoren definiert durch die Kanten gerichtet sein, die Punkte in aufsteigender Reihenfolge. Nehmen Sie das Kreuzprodukt dieser Vektoren:

 given p[k], p[k+1], p[k+2] each with coordinates x, y:
 dx1 = x[k+1]-x[k]
 dy1 = y[k+1]-y[k]
 dx2 = x[k+2]-x[k+1]
 dy2 = y[k+2]-y[k+1]
 zcrossproduct = dx1*dy2 - dy1*dx2

Polygon ist konvex, wenn die z-Komponenten der cross Produkte sind entweder alle positiv oder alle negativ. Ansonsten ist das polygon nonconvex.

Wenn es N Punkte, stellen Sie sicher, Sie berechnen N cross-Produkte, z.B. werden Sie sicher, dass die Drillinge (p[N-2],p[N-1],p[0]) und (p[N-1],p[0],p[1]).

Wenn das polygon selbst schneidet, dann scheitert es bei der technischen definition der Konvexität auch wenn seine gerichtete Winkel sind alle in die gleiche Richtung, dann ist die obige Ansatz nicht zum richtigen Ergebnis.

InformationsquelleAutor der Antwort Jason S

Diese Frage wird jetzt das erste Element in entweder Bing oder Google, bei der Suche nach "bestimmen, konvexen polygon." Jedoch, keiner der Antworten, die gut genug sind.

Die akzeptiert die Antwort von @EugeneYokota funktioniert, indem Sie prüfen, ob eine unsortierte Punkte, die gemacht werden können in ein konvexes polygon, aber das ist nicht das, was der OP gefragt. Er fragte nach einer Methode, um zu überprüfen, ob ein gegebenes polygon ist konvex oder nicht. (Ein "polygon" in der informatik ist in der Regel definiert als [in der XFillPolygon Dokumentation] als geordnetes array von 2D-Punkte, wobei aufeinanderfolgende Punkte verbunden mit einem Seite, als auch den letzten Punkt auf den ersten.) Auch die Geschenkverpackung Algorithmus würde in diesem Fall die Zeit-Komplexität von O(n^2) für n Punkte - das ist viel größer, als tatsächlich benötigt wird, um dieses problem zu lösen, während die Frage fragt nach einer effizienten Algorithmus.

@JasonS Antwort, zusammen mit den anderen Antworten, die Folgen seiner Idee akzeptiert Sterne Polygone wie ein Pentagramm oder in @zenna Kommentar, aber Sterne Polygone nicht als konvex. Als
@plasmacel Hinweise in einem Kommentar, dies ist ein guter Ansatz zu verwenden, wenn Sie die Vorherige Kenntnis, dass das polygon nicht selbst schneiden, aber es kann fehlschlagen, wenn Sie nicht das wissen haben,.

@Sekhat Antwort ist richtig, aber es hat auch die Zeit-Komplexität von O(n^2) und damit ineffizient ist.

@LorenPechtel ' s Antwort Hinzugefügt nach Ihr Bearbeiten ist das beste hier, aber es ist vage.

Einen korrekten Algorithmus mit der optimalen Komplexität

Den Algorithmus, den ich hier präsentieren, hat die Zeit-Komplexität von O(n) richtig testet, ob ein polygon konvex ist oder nicht, und übergibt alle tests, die ich geworfen haben. Die Idee ist, Durchlaufen Sie die Seiten des Polygons, wobei die Richtung jeder Seite und die unterschriebene änderung der Richtung zwischen zwei aufeinander folgenden Seiten. "Unterzeichnet" bedeutet hier Links-Gemeinde positiv ist, und rechts-die Gemeinde ist negativ (oder Umgekehrt) und straight ahead ist null. Die Winkel sind normalisiert zu sein, zwischen minus-pi (exklusive) und pi (inklusive). Fazit alle diese Richtung-ändern Sie die Winkel (ein.k.eine der Durchbiegung Winkel) zusammen Folge im plus-oder-minus eine umdrehung (d.h. 360 Grad) für ein konvexes polygon, während eine sternförmige polygon (oder eine selbst-schneidende Schleife) wird eine andere Summe ( n * 360 Grad, für n stellt sich insgesamt für die Polygone, wo alle die Durchbiegung Winkel sind von der gleichen Vorzeichen). Also müssen wir schauen, dass die Summe der Richtung-ändern der Winkel ist plus-oder-minus eine umdrehung. Wir prüfen auch, dass die Richtung-ändern-Winkel alle positiv oder alle negativ und nicht umkehrt (pi Bogenmaß), alle Punkte sind tatsächliche 2D-Punkte, und dass nicht aufeinander folgende Eckpunkte sind identisch. (Dieser Letzte Punkt ist umstritten-Sie können zulassen möchten wiederholt Eckpunkte, aber ich bevorzuge diese verbieten.) Die Kombination dieser Prüfungen fängt alle konvexen und nicht-konvexen Polygonen.

Hier ist der code für Python 3 implementiert den Algorithmus und enthält einige kleinere Wirkungsgrade. Der code sieht mehr aus als es wirklich ist aufgrund der die Kommentarzeilen und die Buchführung, die beteiligten bei der Vermeidung von wiederholten point zugreift.

TWO_PI = 2 * pi

def is_convex_polygon(polygon):
    """Return True if the polynomial defined by the sequence of 2D
    points is 'strictly convex': points are valid, side lengths non-
    zero, interior angles are strictly between zero and a straight
    angle, and the polygon does not intersect itself.

    NOTES:  1.  Algorithm: the signed changes of the direction angles
                from one side to the next side must be all positive or
                all negative, and their sum must equal plus-or-minus
                one full turn (2 pi radians). Also check for too few,
                invalid, or repeated points.
            2.  No check is explicitly done for zero internal angles
                (180 degree direction-change angle) as this is covered
                in other ways, including the `n < 3` check.
    """
    try:  # needed for any bad points or direction changes
        # Check for too few points
        if len(polygon) < 3:
            return False
        # Get starting information
        old_x, old_y = polygon[-2]
        new_x, new_y = polygon[-1]
        new_direction = atan2(new_y - old_y, new_x - old_x)
        angle_sum = 0.0
        # Check each point (the side ending there, its angle) and accum. angles
        for ndx, newpoint in enumerate(polygon):
            # Update point coordinates and side directions, check side length
            old_x, old_y, old_direction = new_x, new_y, new_direction
            new_x, new_y = newpoint
            new_direction = atan2(new_y - old_y, new_x - old_x)
            if old_x == new_x and old_y == new_y:
                return False  # repeated consecutive points
            # Calculate & check the normalized direction-change angle
            angle = new_direction - old_direction
            if angle <= -pi:
                angle += TWO_PI  # make it in half-open interval (-Pi, Pi]
            elif angle > pi:
                angle -= TWO_PI
            if ndx == 0:  # if first time through loop, initialize orientation
                if angle == 0.0:
                    return False
                orientation = 1.0 if angle > 0.0 else -1.0
            else:  # if other time through loop, check orientation is stable
                if orientation * angle <= 0.0:  # not both pos. or both neg.
                    return False
            # Accumulate the direction-change angle
            angle_sum += angle
        # Check that the total number of full turns is plus-or-minus 1
        return abs(round(angle_sum /TWO_PI)) == 1
    except (ArithmeticError, TypeError, ValueError):
        return False  # any exception means not a proper convex polygon

InformationsquelleAutor der Antwort Rory Daulton

Um zu testen, ob ein polygon ist konvex, jeden Punkt des Polygons sollte auf einer Ebene mit oder hinter jeder Zeile.

Hier ein Beispiel Bild:

InformationsquelleAutor der Antwort Sekhat

Ich implementierte algorithmen: die eine, gepostet von @UriGoren (mit einer kleinen Verbesserung - nur integer-math), und der von @RoryDaulton, in Java. Ich hatte einige Probleme, weil meine polygon geschlossen ist, so dass beide algorithmen wurden unter Berücksichtigung der zweiten als konkav, wenn konvex ist. Also änderte ich es zu verhindern, dass solche situation. Meine Methoden auch verwendet eine base index (der kann oder nicht 0 ist).

Diese sind meiner test-vertices:

//concave
int []x = {0,100,200,200,100,0,0};
int []y = {50,0,50,200,50,200,50};

//convex
int []x = {0,100,200,100,0,0};
int []y = {50,0,50,200,200,50};

Und nun die algorithmen:

private boolean isConvex1(int[] x, int[] y, int base, int n) //Rory Daulton
{
  final double TWO_PI = 2 * Math.PI;

  //points is 'strictly convex': points are valid, side lengths non-zero, interior angles are strictly between zero and a straight
  //angle, and the polygon does not intersect itself.
  //NOTES:  1.  Algorithm: the signed changes of the direction angles from one side to the next side must be all positive or
  //all negative, and their sum must equal plus-or-minus one full turn (2 pi radians). Also check for too few,
  //invalid, or repeated points.
  //     2.  No check is explicitly done for zero internal angles(180 degree direction-change angle) as this is covered
  //in other ways, including the `n < 3` check.

  //needed for any bad points or direction changes
  //Check for too few points
  if (n <= 3) return true;
  if (x[base] == x[n-1] && y[base] == y[n-1]) //if its a closed polygon, ignore last vertex
     n--;
  //Get starting information
  int old_x = x[n-2], old_y = y[n-2];
  int new_x = x[n-1], new_y = y[n-1];
  double new_direction = Math.atan2(new_y - old_y, new_x - old_x), old_direction;
  double angle_sum = 0.0, orientation=0;
  //Check each point (the side ending there, its angle) and accum. angles for ndx, newpoint in enumerate(polygon):
  for (int i = 0; i < n; i++)
  {
     //Update point coordinates and side directions, check side length
     old_x = new_x; old_y = new_y; old_direction = new_direction;
     int p = base++;
     new_x = x[p]; new_y = y[p];
     new_direction = Math.atan2(new_y - old_y, new_x - old_x);
     if (old_x == new_x && old_y == new_y)
        return false; //repeated consecutive points
     //Calculate & check the normalized direction-change angle
     double angle = new_direction - old_direction;
     if (angle <= -Math.PI)
        angle += TWO_PI;  //make it in half-open interval (-Pi, Pi]
     else if (angle > Math.PI)
        angle -= TWO_PI;
     if (i == 0)  //if first time through loop, initialize orientation
     {
        if (angle == 0.0) return false;
        orientation = angle > 0 ? 1 : -1;
     }
     else  //if other time through loop, check orientation is stable
     if (orientation * angle <= 0)  //not both pos. or both neg.
        return false;
     //Accumulate the direction-change angle
     angle_sum += angle;
     //Check that the total number of full turns is plus-or-minus 1
  }
  return Math.abs(Math.round(angle_sum /TWO_PI)) == 1;
}

Und nun von Uri Goren

private boolean isConvex2(int[] x, int[] y, int base, int n)
{
  if (n < 4)
     return true;
  boolean sign = false;
  if (x[base] == x[n-1] && y[base] == y[n-1]) //if its a closed polygon, ignore last vertex
     n--;
  for(int p=0; p < n; p++)
  {
     int i = base++;
     int i1 = i+1; if (i1 >= n) i1 = base + i1-n;
     int i2 = i+2; if (i2 >= n) i2 = base + i2-n;
     int dx1 = x[i1] - x[i];
     int dy1 = y[i1] - y[i];
     int dx2 = x[i2] - x[i1];
     int dy2 = y[i2] - y[i1];
     int crossproduct = dx1*dy2 - dy1*dx2;
     if (i == base)
        sign = crossproduct > 0;
     else
     if (sign != (crossproduct > 0))
        return false;
  }
  return true;
}

InformationsquelleAutor der Antwort Guilherme Campos Hazan

Angepasst Uri ' s code in matlab. Hoffe das kann helfen.

Sich bewusst sein, dass Uri ' s Algorithmus funktioniert nur für einfache Polygone! So, sicher sein, um zu testen, ob das polygon ist einfach die erste!

% M [ x1 x2 x3 ...
%     y1 y2 y3 ...]
% test if a polygon is convex

function ret = isConvex(M)
    N = size(M,2);
    if (N<4)
        ret = 1;
        return;
    end

    x0 = M(1, 1:end);
    x1 = [x0(2:end), x0(1)];
    x2 = [x0(3:end), x0(1:2)];
    y0 = M(2, 1:end);
    y1 = [y0(2:end), y0(1)];
    y2 = [y0(3:end), y0(1:2)];
    dx1 = x2 - x1;
    dy1 = y2 - y1;
    dx2 = x0 - x1;
    dy2 = y0 - y1;
    zcrossproduct = dx1 .* dy2 - dy1 .* dx2;

    % equality allows two consecutive edges to be parallel
    t1 = sum(zcrossproduct >= 0);  
    t2 = sum(zcrossproduct <= 0);  
    ret = t1 == N || t2 == N;

end

InformationsquelleAutor der Antwort Peter K.T. Yu