Comment puis-je déterminer efficacement si un polygone est convexe, non-convexe ou complexe?

vous pouvez rendre les choses beaucoup plus faciles que L'algorithme D'emballage des cadeaux... c'est une bonne réponse quand vous avez un ensemble de points avec n'importe quelle limite particulière et avez besoin de trouver la coque convexe.

En revanche, considérons le cas où le polygone n'est pas auto-intersection, et il se compose d'un ensemble de points dans une liste où les points consécutifs forme la frontière. Dans ce cas, il est beaucoup plus facile de déterminer si un polygone est convexe ou pas (et vous n'avez pas à calculer tout angle, soit):

Pour chaque consécutives paire d'arêtes du polygone (chaque triplet de points), calculer la composante z du produit vectoriel des vecteurs définis par les bords pointant vers les points dans l'ordre croissant. Prenez le produit croisé de ces vecteurs:

 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

le polygone est convexe si les composantes z des produits croisés sont toutes positives ou toutes négatives. Sinon, le polygone est nonconvex.

S'il y a N points, assurez-vous de calculer N de la croix-produits, par exemple, assurez-vous d'utiliser les triplets (p[N-2],p[N-1],p[0]) et (p[N-1],p[0],p[1]).

si le polygone se croise de lui-même, alors il ne répond pas à la définition technique de convexité même si ses angles orientés sont tous dans la même direction, auquel cas l'approche ci-dessus ne produirait pas le résultat correct.

la fonction/méthode Java suivante est une implémentation de l'algorithme décrit dans cette réponse .

public boolean isConvex()
{
    if (_vertices.size() < 4)
        return true;

    boolean sign = false;
    int n = _vertices.size();

    for(int i = 0; i < n; i++)
    {
        double dx1 = _vertices.get((i + 2) % n).X - _vertices.get((i + 1) % n).X;
        double dy1 = _vertices.get((i + 2) % n).Y - _vertices.get((i + 1) % n).Y;
        double dx2 = _vertices.get(i).X - _vertices.get((i + 1) % n).X;
        double dy2 = _vertices.get(i).Y - _vertices.get((i + 1) % n).Y;
        double zcrossproduct = dx1 * dy2 - dy1 * dx2;

        if (i == 0)
            sign = zcrossproduct > 0;
        else if (sign != (zcrossproduct > 0))
            return false;
    }

    return true;
}

l'algorithme est garanti de fonctionner aussi longtemps que les sommets sont ordonnés (soit dans le sens des aiguilles d'une montre ou dans le sens contraire des aiguilles d'une montre), et vous n'avez pas d'arêtes qui se croisent d'elles-mêmes (i.e. il ne fonctionne que pour polygones simples ).

cette question est maintenant le premier élément dans Bing ou Google lorsque vous recherchez" déterminer polygone convexe."Cependant, aucune des réponses n'est suffisante.

la réponse acceptée par @EugeneYokota fonctionne en vérifiant si un ensemble de points non ordonnés peut être transformé en polygone convexe, mais ce n'est pas ce que l'OP a demandé. Il a demandé une méthode pour vérifier si un polygone est convexe ou non. (Polygone" en informatique est généralement défini [comme dans la xfillpolygon documentation ] comme un tableau ordonné de points 2D, avec des points consécutifs joints à un côté ainsi que le dernier point à la première.) De plus, l'algorithme d'enrubannage du cadeau dans ce cas aurait la complexité temporelle de O(n^2) pour n points-qui est beaucoup plus grande que nécessaire pour résoudre ce problème, alors que la question demande un algorithme efficace.

la réponse de @JasonS , ainsi que les autres réponses qui suivent son idée, accepte polygones stellaires tel qu'un pentagramme ou celui dans le commentaire de @zenna, mais les polygones stellaires ne sont pas considérés comme convexes. Comme @plasmacel notes dans un commentaire, c'est une bonne méthode à utiliser si vous avez connaissance préalable que le polygone n'est pas auto-intersection, mais il peut échouer si vous n'avez pas les connaissances.

@la réponse de Sekhat est correcte, mais elle a aussi la complexité temporelle de O(n^2) et est donc inefficace.

@LorenPechtel a ajouté la réponse après son édition est la meilleure ici, mais il est vague.

Un algorithme correct avec optimale de la complexité

l'algorithme que je présente voici la complexité temporelle de O(n) , teste correctement si un polygone est convexe ou non, et passe tous les tests que je lui ai lancés. L'idée est de traverser les côtés du polygone, en notant la direction de chaque côté et le changement de direction signé entre les côtés consécutifs. "Signé" signifie ici que l'aile gauche est positive et que l'aile droite est négative (ou l'inverse) et que l'aile droite est nulle. Ces angles sont normalisés pour être entre moins-pi (exclusive) et pi (inclusive). Summing tous ces angles de changement de direction (A. K. a le déviation angles) ensemble résultera en plus ou moins un tour (i.e. 360 degrés) pour un polygone convexe, tandis qu'un polygone de type étoile (ou une boucle AUTO-se croisant) aura une somme différente ( n * 360 degrés, pour n tours hors-tout, pour les polygones où tous les angles de déviation sont de la même enseigne). Nous devons donc vérifier que la somme des angles de changement de direction est plus ou moins un tour. Nous vérifions également que les angles de changement de direction sont tous positifs ou tous négatifs et non inverses (Pi radians), que tous les points sont des points 2D réels et qu'aucun Vertex consécutif n'est identique. (Ce dernier point est discutable--vous pouvez autoriser répété les sommets mais je préfère pour l'interdire.) La combinaison de ces contrôles concerne tous les polygones convexes et non convexes.

voici le code pour Python 3 qui implémente l'algorithme et inclut quelques efficacités mineures. Le code semble plus long qu'il ne l'est en réalité en raison des lignes de commentaire et de la tenue de livres nécessaires pour éviter les accès ponctuels répétés.

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

pour vérifier si un polygone est convexe, chaque point du polygone doit être à niveau avec ou derrière chaque ligne.

voici un exemple d'image:

Voici un test pour vérifier si un polygone est convexe .

considère chaque ensemble de trois points le long du polygone. Si chaque angle est de 180 degrés ou moins, vous avez un polygone convexe. Lorsque vous calculez chaque angle, garder également un total de marche de (180 - angle). Pour un polygone convexe, le total sera de 360.

cet essai est effectué en O(n) temps.

Notez aussi que dans la plupart des cas ce calcul est quelque chose vous pouvez faire une fois et économiser - la plupart du temps, vous avez un ensemble de polygones à travailler avec qui ne vont pas changer tout le temps.

Le réponse par @RoryDaulton ça me semble le meilleur, mais si l'un des angles est exactement 0? Certains peuvent vouloir qu'un tel cas de bord retourne True, auquel cas, changer "< = " en " < "dans la ligne:

if orientation * angle < 0.0:  # not both pos. or both neg.

Voici mes cas types qui mettent en évidence la question:

# A square    
assert is_convex_polygon( ((0,0), (1,0), (1,1), (0,1)) )

# This LOOKS like a square, but it has an extra point on one of the edges.
assert is_convex_polygon( ((0,0), (0.5,0), (1,0), (1,1), (0,1)) )

La 2ème affirmer échoue dans la réponse originale à cette question. Devrait-il? Pour mon cas d'utilisation, je préférerais que ce ne soit pas le cas.

j'ai implémenté les deux algorithmes: celui posté par @UriGoren (avec une petite amélioration - seulement des maths entières) et celui de @RoryDaulton, en Java. J'ai eu quelques problèmes parce que mon polygone est fermé, donc les deux algorithmes considéraient le second comme concave, quand il était convexe. Donc je l'ai changé pour éviter une telle situation. Mes méthodes utilisent également un indice de base (qui peut être 0 ou non).

ce sont mes sommets de test:

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

et maintenant les algorithmes:

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

et maintenant de 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;
}

cette méthode fonctionnerait sur des polygones simples (pas d'arêtes auto-entrecroisées) en supposant que les sommets sont ordonnés (soit dans le sens des aiguilles d'une montre ou contre)

pour un réseau de Sommets:

vertices = [(0,0),(1,0),(1,1),(0,1)]

la mise en œuvre suivante python vérifie si le composant z de tous les produits croisés porte le même signe

def zCrossProduct(a,b,c):
   return (a[0]-b[0])*(b[1]-c[1])-(a[1]-b[1])*(b[0]-c[0])

def isConvex(vertices):
    if len(vertices)<4:
        return True
    signs= [zCrossProduct(a,b,c)>0 for a,b,c in zip(vertices[2:],vertices[1:],vertices)]
    return all(signs) or not any(signs)

a adapté le code D'Uri en matlab. Espérant que cela puisse aider.

sachez que L'algorithme D'Uri ne fonctionne que pour polygones simples ! Donc, assurez-vous de tester si le polygone est simple, d'abord!

% 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