¿Cómo determino eficientemente si un polígono es convexo, no convexo o complejo?
https://stackoverflow.com/questions/471962
-
19-08-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianPregunta
Desde la página de manual para XFillPolygon :
Si
shapees Complejo , la ruta puede auto-intersectarse. Tenga en cuenta que los puntos coincidentes contiguos en la ruta no se tratan como auto-intersección.Si <=> es Convexo , por cada par de puntos dentro del polígono, el segmento de línea que los conecta no intersecta la ruta. Si el cliente lo conoce, especificar Convexo puede mejorar el rendimiento. Si especifica Convexo para una ruta que no es convexa, los resultados gráficos no están definidos.
Si <=> es No convexo , la ruta no se auto intersecta, pero la forma no es totalmente convexa. Si el cliente lo conoce, especificar No convexo en lugar de Complejo puede mejorar el rendimiento. Si especifica No convexo para una ruta de intersección automática, los resultados gráficos no están definidos.
Tengo problemas de rendimiento con el relleno <=> y, como sugiere la página del manual, el primer paso que quiero dar es especificar la forma correcta del polígono. Actualmente estoy usando Complejo para estar seguro.
¿Existe un algoritmo eficiente para determinar si un polígono (definido por una serie de coordenadas) es convexo, no convexo o complejo?
Solución
Stackoverflow no me deja eliminar una respuesta aceptada, pero diría que revise Respuesta de Rory Daulton .
Otros consejos
Puede hacer las cosas mucho más fáciles que el Algoritmo de envoltura de regalos ... esa es una buena respuesta cuando tiene un conjunto de puntos sin ningún límite en particular y necesita encontrar el casco convexo.
En contraste, considere el caso donde el polígono no se auto-intersecta, y consiste en un conjunto de puntos en una lista donde los puntos consecutivos forman el límite. En este caso, es mucho más fácil averiguar si un polígono es convexo o no (y tampoco tiene que calcular ningún ángulo):
Para cada par consecutivo de aristas del polígono (cada triplete de puntos), calcule el componente z del producto cruzado de los vectores definidos por las aristas que apuntan hacia los puntos en orden creciente. Tome el producto cruzado de estos vectores:
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
El polígono es convexo si los componentes z de los productos cruzados son todos positivos o todos negativos. De lo contrario, el polígono no es convexo.
Si hay N puntos, asegúrese de calcular N productos cruzados, p. asegúrese de usar los tripletes (p [N-2], p [N-1], p [0]) y (p [N-1], p [0], p [1]).
Si el polígono se auto-intersecta, entonces falla la definición técnica de convexidad incluso si sus ángulos dirigidos están todos en la misma dirección, en cuyo caso el enfoque anterior no produciría el resultado correcto.
Esta pregunta ahora es el primer elemento en Bing o Google cuando busca " determine el polígono convexo. " Sin embargo, ninguna de las respuestas es lo suficientemente buena.
El aceptado la respuesta de @EugeneYokota funciona comprobando si un conjunto desordenado de puntos puede convertirse en un polígono convexo, pero eso no es lo que solicitó el OP. Pidió un método para verificar si un polígono dado es convexo o no. (A & Quot; polygon & Quot; en informática generalmente se define [como en documentación de XFillPolygon ] como una matriz ordenada de puntos 2D, con puntos consecutivos unidos con un lado y el último punto con el primero.) Además, el algoritmo de envoltura de regalos en este caso tendría la complejidad temporal de O(n^2) para n puntos, que es mucho mayor de lo que realmente se necesita para resolver este problema, mientras que la pregunta solicita un algoritmo eficiente.
@ JasonS's answer , junto con las otras respuestas que siguen su idea, acepta polígonos en estrella como un pentagrama o el del comentario de @ zenna, pero no se considera que los polígonos de estrella ser convexo Como @plasmacel señala en un comentario, este es un buen enfoque para usar si tiene conocimiento previo de que el polígono no se auto intersecta, pero puede fallar si no tiene ese conocimiento.
@ Sekhat's la respuesta es correcta pero también tiene la complejidad temporal de O(n) y, por lo tanto, es ineficiente.
@ LorenPechtel's respuesta agregada después de que su edición es la mejor aquí pero es vaga.
Un algoritmo correcto con una complejidad óptima
El algoritmo que presento aquí tiene la complejidad temporal de <=>, prueba correctamente si un polígono es convexo o no, y pasa todas las pruebas que le he lanzado. La idea es atravesar los lados del polígono, observando la dirección de cada lado y el cambio de dirección firmado entre lados consecutivos. " Firmado " aquí significa que left-ward es positivo y right-ward es negativo (o al revés) y todo derecho es cero. Esos ángulos están normalizados para estar entre menos-pi (exclusivo) y pi (inclusive). Sumar todos estos ángulos de cambio de dirección (también conocidos como los ángulos de deflexión ) juntos resultarán en más o menos una vuelta (es decir, 360 grados) para un polígono convexo, mientras que un polígono con forma de estrella (o un bucle de auto-intersección) tendrá una suma diferente ( n * 360 grados, para n gira en general, para polígonos donde todos los ángulos de desviación son del mismo signo). Por lo tanto, debemos verificar que la suma de los ángulos de cambio de dirección sea más o menos un giro. También verificamos que los ángulos de cambio de dirección son todos positivos o todos negativos y no reversos (pi radianes), todos los puntos son puntos 2D reales y que no hay vértices consecutivos idénticos. (Ese último punto es discutible; es posible que desee permitir vértices repetidos, pero prefiero prohibirlos). La combinación de esas comprobaciones atrapa todos los polígonos convexos y no convexos.
Aquí hay un código para Python 3 que implementa el algoritmo e incluye algunas eficiencias menores. El código parece más largo de lo que realmente se debe al comentariolíneas y la contabilidad involucrada en evitar accesos repetidos a puntos.
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 siguiente función / método Java es una implementación del algoritmo descrito en esta respuesta .
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;
}
Se garantiza que el algoritmo funcionará siempre y cuando los vértices estén ordenados (en sentido horario o antihorario), y no tenga bordes auto intersectantes (es decir, solo funciona para polígonos simples ).
Aquí hay una prueba para verificar si un polígono es convexo .
Considere cada conjunto de tres puntos a lo largo del polígono. Si cada ángulo es de 180 grados o menos, tiene un polígono convexo. Cuando calcule cada ángulo, también mantenga un total acumulado de (ángulo de 180). Para un polígono convexo, esto totalizará 360.
Esta prueba se ejecuta en tiempo O (n).
Tenga en cuenta también que, en la mayoría de los casos, este cálculo es algo que puede hacer una vez y guardar & # 8212; la mayoría de las veces tiene un conjunto de polígonos para trabajar que no cambian todo el tiempo.
Para probar si un polígono es convexo, cada punto del polígono debe estar nivelado con o detrás de cada línea.
Aquí hay una imagen de ejemplo:
La respuesta de @RoryDaulton me parece lo mejor, pero ¿y si uno de los ángulos es exactamente 0? Algunos pueden querer que dicho caso de borde devuelva True, en cuyo caso, cambie & Quot; & Lt; = & Quot; a " < " en la línea:
if orientation * angle < 0.0: # not both pos. or both neg.
Aquí están mis casos de prueba que resaltan el problema:
# 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 segunda afirmación falla en la respuesta original. ¿Deberia? Para mi caso de uso, preferiría que no lo hiciera.
Implementé ambos algoritmos: el publicado por @UriGoren (con una pequeña mejora, solo matemática entera) y el de @RoryDaulton, en Java. Tuve algunos problemas porque mi polígono está cerrado, por lo que ambos algoritmos consideraban el segundo como cóncavo, cuando era convexo. Así que lo cambié para evitar tal situación. Mis métodos también usan un índice base (que puede ser 0 o no).
Estos son mis vértices de prueba:
// 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};
Y ahora los algoritmos:
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;
}
Y ahora 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;
}
Este método funcionaría en polígonos simples (sin bordes auto intersectantes) suponiendo que los vértices están ordenados (en sentido horario o en sentido contrario)
Para una matriz de vértices:
vertices = [(0,0),(1,0),(1,1),(0,1)]
La siguiente implementación de python verifica si el componente z de todos los productos cruzados tiene el mismo signo
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)
Código de Uri adaptado en matlab. Espero que esto pueda ayudar.
¡Tenga en cuenta que el algoritmo de Uri solo funciona para polígonos simples ! ¡Entonces, asegúrese de probar si el polígono es simple primero!
% 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
