Detectando… paralelepípedos

(Continuación de Detectando los cubos.)

En esta primera parte veremos como detectar configuraciones de puntos que pueden formar la proyección paralela de los vértices de un paralelelepípedo, resolviendo parte del problema planteado anteriormente. Analizaremos como determinar si corresponden a un cubo en un posterior post.

La idea básica detrás del algoritmo de detección es observar que las caras de un paralelepípedo son paralelogramos y que estos preservan el paralelismo de sus lados al ser proyectados en forma paralela.

Puede dividirse a este algoritmo en cinco pasos:

  1. Buscar el punto que se encuentre más a la izquierda (menor valor de X) y, dentro de ellos más arriba (menor valor de Y, en nuestro caso). Ese punto será denominado p0 y será tomado como referencia.
  2. Imaginando un semieje en dirección +X partiendo desde p0, se eligen los dos puntos que posean el mayor y el menor ángulo (teniendo en cuenta el signo!) respecto a ese eje. Estos puntos son denominados p1 y p2 y formarán la base para identificar la primera cara del paralelepípedo.
  3. Se busca un punto p12 que cierre el paralelogramo formado por p0, p1 y p2. Estos puntos formarán la que podemos denominar “cara -X” del paralelepípedo.
  4. Opuesta a la “cara -X” debe existir una “cara +X”, que además debe poseer vértices “análogos” a cada uno de los hallados anteriormente, solo que trasladados en forma paralela. Podemos buscar el análogo de p0 repitiendo el procedimiento utilizado para hallar p0 pero omitiendo los puntos p0, p1, p2 y p12.
  5. Una vez hallado p3, conocemos el desplazamiento relativo entre ambas caras (-X y +X). Por lo tanto podemos buscar los “análogos” a p1, p2 y p12: p13, p23 y p123. Si todos estos puntos pueden ser hallados, entonces la serie de puntos puede ser la proyección paralela de un paralelepípedo.

En la siguiente figura podemos ver el funcionamiento del algoritmo:

Funcionamiento normal del algoritmo (detección exitosa).

Los únicos pasos donde el algoritmo puede fallar, detectando que no estamos trabajando con la proyección de un paralelepípedo, son los pasos 3 y 5:

Funcionamiento con fallo en la detección del algoritmo (paso 3).

Funcionamiento con fallo en la detección del algoritmo (paso 5).

El código correspondiente en Python, que es una traducción casi directa de los pasos mencionados anteriormente, puede encontrarse en el repositorio SVN de este blog. La única diferencia digna de mención es la adición de un “paso 0” que comprueba la cantidad de vértices.

Para probarlo basta con ejecutar el generador de casos de prueba (que creará dos archivos: input.txt y key.txt), luego el detector de paralelepípedos (que creará un archivo de salida output.txt) y, por último, el comparador (que comparará el archivo output.txt y el archivo key.txt, indicando la cantidad de falsos negativos y falsos positivos).

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s