Práctica No. 1

Descargar código de práctica 1

Debido a que no tengo mucho tiempo, y que los primeros dos problemas fueron resueltos satisfactoriamente en la práctica, he decidido mostrar acá solamente la resolución del tercer problema. El correspondiente enunciado dice lo siguiente:

Construya un programa que lea desde teclado las coordenadas reales de tres puntos del plano cartesiano, y las coordenadas de un cuarto punto, del mismo plano, que diga en pantalla si el cuarto punto está o no dentro del triángulo (si está sobre los lados o vértices, está adentro). Cada punto se ingresará mediante dos números reales que representan la coordenada X y la coordenada Y. Asuma que los puntos forman efectivamente un triángulo.

Del enunciado hay que notar lo siguiente:

  • Las coordenadas se leerán desde teclado. Es decir, será necesario pedirlos al usuario mediante un mensaje, y obtenerlos utilizando la función (read).
  • Las coordenadas son en dos dimensiones, en el plano que contiene los ejes X y Y. Por tanto, serán dos coordenadas por cada punto.
  • Las coordenadas pueden ser números reales.
  • Se ingresarán las coordenadas de cuatro puntos. Las primeras tres corresponderán a los vértices del triángulo.
  • Se asume que las coordenadas de los tres primeros puntos forman un triángulo. Por tanto, esto no se debe validar.
  • Se dirá en pantalla si el cuarto punto está o no dentro del triángulo. Es decir, la función no debe retornar un valor, sino mostrar el resultado mediante un mensaje en pantalla. Para ello se podría usar un (display “…”) o un (printf “…”)

Luego de haber contemplado los requerimientos de entrada, hay que decidir cómo se resolverá el problema. Para este caso, decidí utilizar el principio de región factible, que se refiere, en el caso de dos dimensiones, a aquella región formada por todos los puntos (x,y) que cumplen con una desigualdad dada F(x,y)<=G(x,y). Esto servirá para poder definir una frontera que delimite la región del triángulo, y así poder saber si el cuarto punto ingresado por el usuario está dentro o no de éste. Para ello nos basaremos primeramente en la ecuación “dos puntos” de la recta (si mal no recuerdo, así se llama), que es la ecuación de la recta que pasa por los puntos conocidos (x1, y1) y (x2, y2):

y – y1 = m * (x – x1)

y – y1 = ( (y2-y1)/(x2-x1) ) * (x – x1)

Hasta aquí, existe un problema: si la recta formada por (x1,y1) y (x2,y2) es vertical, se produce una división entre cero, ya que x2 = x1. Para evitar esto, es necesario efectuar el siguiente cambio:

(y-y1) * (x2-x1) = (y2-y1) * (x-x1)

Luego, para determinar de qué lado de la recta está el punto (x,y), transformamos esta ecuación en una desigualdad, sustituyendo el signo “=” por “>=”, o bien por “<=”. Retomando el problema del triángulo, lo que se busca es que tanto el tercer vértice (x3,y3) como el cuarto punto (x4,y4) (del cual se desea saber si está dentro del triángulo) estén del mismo lado de la recta que pasa por los dos vértices restantes (x1,y1) y (x2,y2). Esto se comprobará si, al sustituir (x,y) = (x3,y3) y (x,y) = (x4,y4), se cumple la misma desigualdad en la ecuación de la recta, es decir, se cumple:

(y3-y1) * (x2-x1) <= (y2-y1) * (x3-x1) y también (y4-y1) * (x2-x1) <= (y2-y1) * (x4-x1)

o bien

(y3-y1) * (x2-x1) >= (y2-y1) * (x3-x1) y también (y4-y1) * (x2-x1) >= (y2-y1) * (x4-x1)

Esta comprobación se verifica para cada una de las tres rectas que froman el triángulo. Si esta condición se cumple las tres veces, entonces el cuarto punto sí estará dentro del triángulo (incluyendo sus vértices y sus perímetro). Gráficamente:

Ilustración de región factible

En la figura A se muestra la ilustración del concepto de región factible, aplicado a la resolución del problema. Aquí podemos constatar que tanto el tercer vértice del triángulo, como el cuarto punto, están en la misma región factible (en el mismo lado de la recta que pasa por los puntos 1 y 2). En la figura B se observa que el cuarto punto está dentro del triángulo, y para las tres rectas se puede ver que se cumple la condición evaluada en la figura A. En la figura C se observa un caso en el que el cuarto punto está fuera del triángulo. Hay que notar que cuando se toma la recta entre los puntos 1 y 2, no se cumple la condición establecida, ya que el cuarto punto está en una región distinta a la del tercer vértice del triángulo. Sin embargo, dicha condición sí se cumple para las rectas entre los puntos 1-3, y 2-3

Ahora que ya se tiene el concepto o método que se utilizará para resolver el problema, es posible proceder a la programación. Primeramente se partirá creando una función encargada de la verificación de que los puntos (x3,y3) y (x4,y4) estén dentro de la misma región factible, es decir, del mismo lado de la recta formada por los vértices (x1,y1) y (x2,y2). Cabe señalar que, para evitar confusiones del cuarto punto con los vértices del triángulo, dentro del programa se hará referencia a este como (xp,yp). El código en scheme se muestra a continuación:

(define (estaDentroTriangulo? x1 y1 x2 y2 x3 y3 xp yp)
  (let* ((a3 (* (- y3 y1) (- x2 x1)))   ;; a3 = (y3-y1)*(x2-x1)
         (b3 (* (- y2 y1) (- x3 x1)))   ;; b3 = (y2-y1)*(x3-x1)
         (ap (* (- yp y1) (- x2 x1)))   ;; ap = (yp-y1)*(x2-x1)
         (bp (* (- y2 y1) (- xp x1))))  ;; bp = (y2-y1)*(xp-x1)
    (or (and (<= a3 b3) (<= ap bp))        ;;comparando que la misma desigualdad de
        (and (>= a3 b3) (>= ap bp)))))     ;;cumpla para ambos puntos (x3,y3) y (xp,yp)

Esta función efectúa la comparación solamente para un lado del triángulo. Es necesario ahora hacer una función principal, encargada de solicitar los datos al usuario, y, auxiliándose de la función anterior, realizar las verificaciones correspondientes a cada lado del triángulo. Es necesario recordar que el cuarto punto estará dentro del triángulo si la verificación es verdadera para cada uno de los 3 lados del triángulo (3 rectas). En este caso, también utilizaremos la función principal para desplegar los mensajes correspondientes al resultado.

;;-Función principal
(define (puntoEnTriangulo)
  (let-values (((x1 y1) (leerPunto "Ingrese el primer vértice del triángulo"))
               ((x2 y2) (leerPunto "Ingrese el segundo vértice del triángulo"))
               ((x3 y3) (leerPunto "Ingrese el tercer vértice del triángulo"))
               ((xp yp) (leerPunto "Ingrese un punto cualquiera")))
    (if (and (estaDentroTriangulo? x1 y1 x2 y2 x3 y3 xp yp)  ;se hace la verificación de
             (estaDentroTriangulo? x3 y3 x1 y1 x2 y2 xp yp)  ;región factible para cada par
             (estaDentroTriangulo? x2 y2 x3 y3 x1 y1 xp yp)) ;de vértices
        (display "El cuarto punto ingresado SÍ está dentro del triángulo")
        (display "El cuarto punto ingresado NO está dentro del triángulo"))
    (newline)))

Finalmente, para evitar que el código de la función principal resultara demasiado engorroso, se consideró apropiado crear un tercer módulo, encargado de la lectura del par de coordenadas de cada punto:

;;-Función auxiliar, encargada de la lectura de los puntos
(define (leerPunto msj)
  (display msj)
  (newline)
  (let* ((x (begin
              (display "Ingrese la coordenada X: ")
              (read)))      ;; OBSERVAR: La instrucción begin retorna lo
                            ;;           indicado en la última instrucción
         (y (begin
              (display "Ingrese la coordenada Y: ")
              (read)))
         )
    (newline)
    (values x y)))

De esta función auxiliar, cabe resaltar la forma en que se ha utilizado los bloques begin, ya que esto nos permite mostrar un mensaje en pantalla, luego efectuar la lectura desde teclado, y finalmente la correspondiente asignación a las variables x y y.

Creo que me extendí bastante con la explicación, pero espero que haya valido la pena, es decir,que esté lo suficientemente clara y comprensible. Pero de cualquier forma, si tienen dudas o comentarios, pueden enviármelos al correo, o preguntarme cuando me encuentren en la universidad. Por cierto, les dejo el código de la primera práctica, por si quieren darle una ojeada, haciendo clic aqui para descargarlo.

2 pensamientos en “Práctica No. 1

  1. Pingback: Práctica guiada No. 1 « PF - Souvenirs de drScheme

  2. Pingback: Práctica guiada No. 1 | Souvenirs de IT

Responder

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión / Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión / Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión / Cambiar )

Google+ photo

Estás comentando usando tu cuenta de Google+. Cerrar sesión / Cambiar )

Conectando a %s