algorithm - pentagono - poligonos concavos y convexos ejemplos

¿Cómo determino de manera eficiente si un polígono es convexo, no convexo o complejo? (10)

NOTA: calcular el casco convexo de un conjunto de puntos es completamente innecesario si solo desea determinar si una lista de puntos que representa un polígono representa un polígono convexo.

Suponiendo que todos sus polígonos estén en el sentido contrario a las agujas del reloj, en el momento en que su ángulo polar no inicial gire a la izquierda, sabrá que no es convexo.

Podrías ver si los segmentos de línea se cruzan entre sí para descubrir si el polígono es complejo (pero no estoy seguro de si esa es la manera más rápida).

Desde la página del XFillPolygon para XFillPolygon :

Si la shape es compleja , la ruta puede autointersecarse. Tenga en cuenta que los puntos contiguos coincidentes en la ruta no se tratan como autointersección.
Si la shape es convexa , por cada par de puntos dentro del polígono, el segmento de línea que los conecta no interseca la ruta. Si el cliente lo conoce, especificar Convex puede mejorar el rendimiento. Si especifica Convex para una ruta que no es convexa, los resultados de los gráficos no están definidos.
Si la forma es no convexa, la ruta no se interseca automáticamente, pero la forma no es totalmente convexa. Si el cliente lo conoce, especificar Nonconvex en lugar de Complex puede mejorar el rendimiento. Si especifica Nonconvex para una ruta autointersecante, los resultados gráficos no están definidos.

Tengo problemas de rendimiento con el relleno XFillPolygon 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 Complex 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?

Adaptado el código de Uri en matlab. Espero que esto pueda ayudar.

Tenga en cuenta que el algoritmo de Uri solo funciona para polígonos simples . Por lo tanto, ¡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

Aquí hay una prueba para verificar si un polígono es convexo .

Considera cada conjunto de tres puntos a lo largo del polígono. Si cada ángulo es de 180 grados o menos, tienes un polígono convexo. Cuando descubra cada ángulo, también mantenga un total acumulado de (180 - ángulo). Para un polígono convexo, este totalizará 360.

Esta prueba se ejecuta en el 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: la mayoría de las veces tiene un conjunto de polígonos para trabajar que no cambian todo el tiempo.

Esta pregunta ahora es el primer elemento en Bing o Google cuando busca "determinar polígono convexo". Sin embargo, ninguna de las respuestas es lo suficientemente buena.

La respuesta aceptada por @EugeneYokota funciona al verificar 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 determinado es convexo o no. (Un "polígono" en ciencias de la computación generalmente se define [como en la XFillPolygon ] como una matriz ordenada de puntos 2D, con puntos consecutivos unidos con un lado así como el último punto con respecto al primero.) Además, el algoritmo de envoltura de regalos en este caso tendría la complejidad de tiempo de O(n^2) para n puntos, que es mucho más grande de lo que realmente se necesita para resolver este problema, mientras que la pregunta requiere un algoritmo eficiente.

@ La respuesta de JasonS , junto con las otras respuestas que siguen a su idea, acepta polígonos estrella como un pentagram o uno en el comentario de @zena, pero los polígonos estrella no se consideran convexos. Como @plasmacel notas en un comentario, este es un buen enfoque para usar si tienes conocimiento previo de que el polígono no se interseca a sí mismo, pero puede fallar si no tienes ese conocimiento.

La respuesta de @Sekhat es correcta, pero también tiene la complejidad temporal de O(n^2) y, por lo tanto, es ineficiente.

La respuesta agregada de @LynPechtel después de 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 de tiempo de O(n) , comprueba 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, teniendo en cuenta la dirección de cada lado y el cambio de dirección firmado entre los lados consecutivos. "Firmado" aquí significa que la izquierda es positiva y la derecha es negativa (o lo contrario) y recta es cero. Esos ángulos están normalizados para estar entre minus-pi (exclusivo) y pi (inclusive). Sumar todos estos ángulos de cambio de dirección (también conocidos como ángulos de deflexión ) dará como resultado más o menos un giro (es decir, 360 grados) para un polígono convexo, mientras que un polígono tipo estrella (o un bucle autointersecante) tendrá una suma diferente ( n * 360 grados, para n giros en general, para polígonos donde todos los ángulos de desviación son del mismo signo). Entonces, 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 sean todos positivos o totalmente negativos y no reversos (pi radianes), todos los puntos son puntos 2D reales y que ningún vértice consecutivo es idéntico. (Este último punto es discutible: es posible que desee permitir vértices repetidos, pero prefiero prohibirlos). La combinación de esos controles captura 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 es debido a las líneas de comentarios y la contabilidad involucrada en evitar accesos de punto repetidos.

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

Este método funcionaría en polígonos simples (sin bordes autointersecantes) suponiendo que los vértices están ordenados (ya sea en el sentido de las agujas del reloj o en el contador)

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)

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 esa situación. Mis métodos también usan un índice base (que puede ser o no 0).

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

La respuesta de @RoryDaulton me parece la mejor, pero ¿y si uno de los ángulos es exactamente 0? Algunos pueden desear que dicho caso extremo devuelva True, en cuyo caso, cambie "<=" a "<" en la línea:

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

Aquí están mis casos de prueba que destacan 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 fuera así.

La siguiente función / método de 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 que los vértices estén ordenados (en el sentido de las agujas del reloj o en el sentido contrario a las agujas del reloj) y no tenga bordes autointersecables (es decir, solo funciona para polígonos simples ).

Para probar si un polígono es convexo, cada punto del polígono debe estar al nivel con o detrás de cada línea.

Aquí hay una imagen de ejemplo:

Puedes hacer las cosas mucho más fáciles que el algoritmo de envoltura de regalos ... esa es una buena respuesta cuando tienes un conjunto de puntos sin ningún límite particular y necesitas encontrar el casco convexo.

En contraste, considere el caso en el que el polígono no se interseca a sí mismo 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 determinar si un polígono es convexo o no (y tampoco tiene que calcular ningún ángulo):

Para cada par de aristas consecutivas del polígono (cada triplete de puntos), calcule el componente z del producto cruzado de los vectores definidos por los bordes 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 positivos o negativos. De lo contrario, el polígono no es convexo.

Si hay N puntos, asegúrese de calcular N productos cruzados, por ejemplo, asegúrese de utilizar los tríos (p [N-2], p [N-1], p [0]) y (p [N-1], p [0], p [1]).

Si el polígono se interseca automáticamente, 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.