Comment déterminer efficacement si un polygone est convexe, non convexe ou complexe?
https://stackoverflow.com/questions/471962
-
19-08-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianQuestion
A partir de la page de manuel relative à XFillPolygon :
Si
shapeest Complex , le chemin peut s'auto-intersecter. Notez que les points coïncidents contigus du tracé ne sont pas traités comme des auto-intersections.Si <=> est Convexe , pour chaque paire de points à l'intérieur du polygone, le segment de ligne les reliant ne coupe pas le tracé. Si le client le sait, spécifier Convex peut améliorer les performances. Si vous spécifiez Convexe pour un chemin non convexe, les résultats graphiques ne sont pas définis.
Si <=> est Nonconvex , le chemin ne se croise pas automatiquement, mais sa forme n'est pas entièrement convexe. Si le client le sait, spécifier Nonconvex au lieu de Complex peut améliorer les performances. Si vous spécifiez Nonconvex pour un chemin à intersection automatique, les résultats graphiques ne sont pas définis.
Je rencontre des problèmes de performances lors du remplissage <=> et, comme le suggère la page de manuel, la première étape que je souhaite franchir consiste à spécifier la forme correcte du polygone. J'utilise actuellement le complexe pour plus de sécurité.
Existe-t-il un algorithme efficace pour déterminer si un polygone (défini par une série de coordonnées) est convexe, non convexe ou complexe?
La solution
Stackoverflow ne me laissera pas supprimer une réponse acceptée, mais je dirais de vérifier La réponse de Rory Daulton .
Autres conseils
Vous pouvez rendre les choses beaucoup plus faciles que l’algorithme d’emballage cadeau ... c’est une bonne réponse lorsque vous avez un ensemble de points sans limite particulière et que vous avez besoin de trouver la coque convexe.
En revanche, considérons le cas où le polygone ne se croise pas automatiquement et consiste en un ensemble de points dans une liste où les points consécutifs forment la limite. Dans ce cas, il est beaucoup plus facile de déterminer si un polygone est convexe ou non (et vous n'avez pas à calculer d'angles non plus):
Pour chaque paire d’arêtes consécutives du polygone (chaque triplet de points), calculez la composante z du produit croisé des vecteurs définis par les arêtes 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 non convexe.
S'il y a N points, assurez-vous de calculer N produits croisés, par exemple. veillez à utiliser les triplets (p [N-2], p [N-1], p [0]) et (p [N-1], p [0], p [1]).
Si le polygone se croise automatiquement, la définition technique de la convexité est manquante même si ses angles dirigés vont tous dans la même direction, auquel cas l'approche ci-dessus ne produirait pas le résultat correct.
Cette question est désormais le premier élément de Bing ou de Google lorsque vous recherchez & "Déterminer un polygone convexe. &"; Cependant, aucune des réponses ne suffit.
Le accepté answer byEugeneYokota : vérifie si un ensemble non ordonné de points peut être transformé en un polygone convexe, mais ce n'est pas ce que le PO a demandé. Il a demandé une méthode pour vérifier si un polygone donné est convexe ou non. (Un & Quot; polygone & Quot; en informatique est généralement défini [comme dans le documentation XFillPolygon ] en tant que tableau ordonné de points 2D, avec des points consécutifs reliés à un côté et au dernier point du premier.) En outre, dans ce cas, l'algorithme d'habillage des cadeaux aurait la complexité temporelle de O(n^2) points pour n points - ce qui est beaucoup plus grand que ce qui est réellement nécessaire pour résoudre ce problème, alors que la question demande un algorithme efficace.
@ JasonS's answer , ainsi que les autres réponses qui suivent son idée, accepte les polygones en étoile tel qu'un pentagramme ou celui dans le commentaire de @ zenna, mais les polygones en étoile ne sont pas considérés être convexe. Comme @ Plasmacel note dans un commentaire: c’est une bonne approche à utiliser si vous savez déjà que le polygone ne se croise pas automatiquement, mais il peut échouer si vous n’avez pas cette connaissance.
@ Sekhat's La réponse est correcte, mais elle a aussi la complexité temporelle de O(n) et est donc inefficace.
@ LorenPechtel's La réponse ajoutée après sa modification est la meilleure, mais reste vague.
Un algorithme correct avec une complexité optimale
L’algorithme que je présente ici a la complexité temporelle de <=>, teste correctement si un polygone est convexe ou non, et réussit tous les tests que j’ai testés. L'idée est de parcourir 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é " ici signifie que la gauche est positive et que la droite est négative (ou l'inverse) et que le droit devant est égal à zéro. Ces angles sont normalisés pour être compris entre moins-pi (exclusif) et pi (inclusif). Résumant tous ces angles de changement de direction (autrement dit les angles de déviation ) ensemble donnera un tour plus ou moins (c.-à-d. 360 degrés) pour un polygone convexe, alors qu’un polygone en étoile (ou une boucle auto-sécante) aura une somme différente ( n * 360 degrés, pour n tourne globalement, pour les polygones où tous les angles de déviation sont du même signe). Nous devons donc vérifier que la somme des angles de changement de direction est de 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 inversés (pi radians), tous les points sont des points 2D réels et qu’aucun sommet consécutif n’est identique. (Ce dernier point est discutable - vous pouvez autoriser les sommets répétés mais je préfère les interdire.) La combinaison de ces vérifications capture 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 a l'air plus long qu'il ne l'est vraiment à cause du commentairedes lignes et de la comptabilité 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
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;
}
Il est garanti que l’algorithme fonctionne tant que les sommets sont ordonnés (dans le sens des aiguilles d’une montre ou dans le sens inverse des aiguilles d’une montre), et que vous n’avez pas d’arêtes auto-sécantes (c’est-à-dire qu’il ne fonctionne que pour polygones simples ).
Voici un test pour vérifier si un polygone est convexe .
Considérons chaque ensemble de trois points le long du polygone. Si chaque angle est inférieur ou égal à 180 degrés, vous avez un polygone convexe. Lorsque vous déterminez chaque angle, conservez également un total cumulé de (angle 180). Pour un polygone convexe, le total sera de 360.
Ce test s'exécute dans le temps O (n).
Notez également que dans la plupart des cas, ce calcul est une chose que vous pouvez faire une fois et enregistrer & # 8212; la plupart du temps, vous avez un ensemble de polygones à utiliser qui ne changent pas tout le temps.
Pour vérifier si un polygone est convexe, chaque point du polygone doit être de niveau avec ou derrière chaque ligne.
Voici un exemple d'image:
Le réponse de @RoryDaulton Cela me semble préférable, mais que se passe-t-il si l’un des angles est exactement égal à 0? Certains voudront peut-être qu'un tel cas d'extrémité retourne True, auquel cas changer & "; & Lt; = &"; à " < " dans la ligne:
if orientation * angle < 0.0: # not both pos. or both neg.
Voici mes cas de test mettant en évidence le problème:
# 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 assertion échoue dans la réponse d'origine. Devrait-il? Pour mon cas d'utilisation, je préférerais que ce ne soit pas le cas.
J'ai mis en œuvre les deux algorithmes: celui publié par @UriGoren (avec une petite amélioration - calcul mathématique entier) 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. Alors je l'ai changé pour éviter une telle situation. Mes méthodes utilisent également un index de base (qui peut être ou non 0).
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 d'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 (sans arêtes auto-sécantes) en supposant que les sommets sont ordonnés (dans le sens des aiguilles d'une montre ou contre)
Pour un tableau de sommets:
vertices = [(0,0),(1,0),(1,1),(0,1)]
L’implémentation python suivante vérifie si les composants z de tous les produits croisés ont 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)
Adapté le code d'Uri dans Matlab. J'espère que cela peut aider.
Sachez que l'algorithme d'Uri ne fonctionne que pour les polygones simples ! Veillez donc à vérifier si le polygone est simple en premier!
% 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
