Simple

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

Un polígono es simple siempre y cuando el grado de cada vértice del grafo inducido por los segmentos del borde del polígono sea igual a dos.

Dicho grafo se obtiene así:

1. Se calcula todos los puntos de intersección entre dos segementos del borde (entonces todas las esquinas estarán entre ellos).
2. Estos puntos representan los vértices del grafo.
3. Se añade al grafo una arista entre dos nodos siempre y cuando los puntos correspondientes estén unidos directamente por un trozo de segmento.

En consecuencia, si permitiésemos que un punto sólo forme un polígono, no formaría un polígono simple.

Una explicación intuitiva de simple es:

• imagínate el borde del polígono como una cuerda colocada encima de la mesa (o vete a buscar una ...)
• pincha con un clavo (o un bolí) en un punto interior del polígono
• tira a la cuerda y observa cuantas veces le da la vuelta al clavo (bolí)
• si independientemente de la selección del punto interior siempre observas solo una vuelta, entonces, el polígono es simple.

Para comprobar si un polígono es simple o no, podemos aplicar p.e. el siguiente algoritmo sencillo:

1. Calculamos todos los puntos de intersección entre todas las parejas posibles de dos segmentos.
2. Construímos el grafo inducido.
3. Comprobamos si cada vértice tiene grado igual a dos.

Debido al paso uno, dicho algoritmo tendría un tiempo de ejecución inevitablemente cuadrático en el número de esquinas del polígono.

Existen algoritmos (basados en el paradigma de ``barrer el plano'') que realizan el test en un tiempo de ejecución del orden n log n, siendo n el número de esquinas del polígono. (Para recordar: si el algoritmo sencillo necesitaría una hora para comprobar un polígono con un millon de puntos, el algoritmo avanzado lo haría en menos de una décima de segundo.)

Como veremos en breve, no necesitamos ninguno de ellos...