Convexo

Asumimos un polígono bidimensional sin puntos múltiples consecutivos.

Un polígono es convexo siempre y cuando cumpla una de las siguientes condiciones:

• Para cualesquiera dos puntos del interior del polígono, todos los puntos del segmento definido por los dos puntos también se encuentren en el interior.
• Para cualquier segmento del borde del polígono, todas las esquinas qué no son aquellas que definen el segmento están siempre a la derecha (o siempre a la izquierda) de la recta definida por el segmento.
• El polígono es simple y todos los ángulos entre dos segmentos adyacentes del borde del polígono son menor o igual (o son mayor o igual) de 180 grados (es decir, pi si medimos en radianes).

Se puede comprobar formalmente que las tres condiciones son equivalentes.

La primera condición es difícil de comprobar programando, porque hay un número infinito de puntos en el interior de un polígono. La condición sirve más bién en comprobaciones matemáticas.

La segunda condición sí se puede programar. Resultaría en un algoritmo con tiempo de ejecución cuadrático en el número de esquinas, porque hay que hacer comprobaciones para cada segmento con casi todas las demás esquinas.

La tercera condición también se puede programar. La comprobación de los ángulos nos llevaría un tiempo lineal en el número n de esquinas. Sin embargo, necesitamos un tiempo en el orden n log n para comprobar si el polígono adicionalmente es simple (o cuadrático si nos conformamos con el algoritmo simple) como vimos arriba.

Pues, ¿hay algo mejor? (¿e incluso más sencillo de programar?)