Ejercicios

Enlace al paquete de este capítulo.

  1. Como mencionamos en la explicación del algoritmo de Cohen-Sutherland, podemos mejorarlo un poco para que no recalcule la pendiente de la intersección en cada iteración.

    1. Implemente el algoritmo original,

    2. Implemente otra versión del algoritmo con la mejora mencionada, y

    3. Escriba un programa para comparar el rendimiento de ambos algoritmos. Para el programa, cree aleatoriamente varios segmentos - decenas de millares - para pasarlos por los dos algoritmos de a) y b) para ser recortados. Cronometre los procesamientos de ambos algoritmos y muestre los resultados de la comparativa.

  2. Optimice el algoritmo de Nicholl-Lee-Nicholl para reusar multiplicaciones y restas y así no hay que invocar a Izquierda(), ni a Derecha(), ni tampoco a Intersección_Vertical() ni a Intersección_Horizontal(). Por ejemplo, en el algoritmo de Recortar_Interior(), podemos sustituir el comienzo con los siguientes pasos, para no tener que usar Izquierda():

    1. QPX ← Q.x - P.x
    2. QPY ← Q.y - P.y
    3. A ← R.xizq - P.x
    4. B ← R.ysup - P.y
    5. Si A*QPX + B*QPY > 0, entonces
  3. Implemente las mejoras mencionadas anteriormente para el algoritmo Weiler-Atherton. Cree otra lista de puntos, o referencias a los puntos, para guardar las intersecciones entrantes, que previamente hemos calculado. Esta lista contendrá menos puntos que la lista de los vértices originales y puntos de intersección. Ahora, sólo tendremos que consultar esta lista, en lugar de buscar las intersecciones entre todos los puntos, para conseguir aquellas intersecciones entrantes aún sin visitar.

  4. Como mencionamos anteriormente, podemos usar el algoritmo de Weiler-Atherton para el modelado. Con las operaciones básicas de conjuntos - unión, intersección, y diferencia - podemos construir nuevas figuras geométricas a partir de dos figuras básicas, como mínimo.

    [IMAGEN]: Ejercicio 4 - Polígonos A y B
    Ejercicio 4 - Polígonos A y B
    • A ∪ B. Para la unión, buscamos cualesquier intersecciones entre los dos polígonos A y B. Comenzamos con el recorrido de A, el polígono a recortar, o de B, el polígono de recorte. Cambiamos de polígono al encontrarnos con intersecciones.

      [IMAGEN]: Ejercicio 4 - Unión de A y B
      Ejercicio 4 - Unión de A y B
    • A ∩ B. La intersección es justamente el algoritmo original de recorte de Weiler-Atherton. Recorremos el polígono A al encontrarnos con las intersecciones entrantes y recorremos el polígono B al encontrarnos con las intersecciones salientes.

      [IMAGEN]: Ejercicio 4 - Intersección de A y B
      Ejercicio 4 - Intersección de A y B
    • A − B. Para la diferencia, comenzamos con el polígono A y eliminamos partes de ello con el polígono B. Usando el algoritmo de Weiler-Atherton, recorremos el polígono A al encontrarnos con las intersecciones salientes y recorremos el polígono B al encontrarnos con las intersecciones entrantes.

      [IMAGEN]: Ejercicio 4 - Diferencia de A y B
      Ejercicio 4 - Diferencia de A y B

    Cree un programa que permita al usuario generar polígonos con estas operaciones.