Ir al contenido principal

Puntos en regiones rectangulares

Los puntos se puede representar mediante pares de números

type Punto = (Float,Float)

y las regiones rectangulares mediante el siguiente tipo de dato

   data Region = Rectangulo Punto  Punto
               | Union      Region Region
               | Diferencia Region Region
               deriving (Eq, Show)

donde

  • (Rectangulo p1 p2) es la región formada por un rectángulo cuyo vértice superior izquierdo es p1 y su vértice inferior derecho es p2.
  • (Union r1 r2) es la región cuyos puntos pertenecen a alguna de las regiones r1 y r2.
  • (Diferencia r1 r2) es la región cuyos puntos pertenecen a la región r1 pero no pertenecen a la r2.

Definir la función

enRegion :: Punto -> Region -> Bool

tal que (enRegion p r) se verifica si el punto p pertenece a la región r. Por ejemplo, usando las regiones definidas por

r0021, r3051, r4162 :: Region
r0021 = Rectangulo (0,0) (2,1)
r3051 = Rectangulo (3,0) (5,1)
r4162 = Rectangulo (4,1) (6,2)

se tiene

enRegion (1.6,0.7) r0021                               ==  True
enRegion (3.6,0.7) r0021                               ==  False
enRegion (1,1) (Union r0021 r3051)                     ==  True
enRegion (4,0) (Union r0021 r3051)                     ==  True
enRegion (4,2) (Union r0021 r3051)                     ==  False
enRegion (3,1) (Diferencia r3051 r4162)                ==  True
enRegion (4,1) (Diferencia r3051 r4162)                ==  False
enRegion (4,2) (Diferencia r3051 r4162)                ==  False
enRegion (4,2) (Union (Diferencia r3051 r4162) r4162)  ==  True

Comprobar con QuickCheck que si el punto p está en la región r1, entonces, para cualquier región r2, p está en (Union r1 r2) y en (Union r2 r1), pero no está en (Diferencia r2 r1).

Nota: Escribir las soluciones usando la siguiente plantilla que contiene un generador de regiones

import Test.QuickCheck
import Control.Monad

type Punto = (Float,Float)

data Region = Rectangulo Punto  Punto
            | Union      Region Region
            | Diferencia Region Region
            deriving (Eq, Show)

r0021, r3051, r4162 :: Region
r0021 = Rectangulo (0,0) (2,1)
r3051 = Rectangulo (3,0) (5,1)
r4162 = Rectangulo (4,1) (6,2)

enRegion :: Punto -> Region -> Bool
enRegion = undefined

-- La propiedad es
prop_enRegion p r1 r2 = undefined

-- La comprobación es
--    λ> quickCheckWith (stdArgs {maxDiscardRatio=20}) prop_enRegion
--    +++ OK, passed 100 tests.

-- Generador de regiones:
instance Arbitrary Region where
    arbitrary = sized arb where
        arb 0         = liftM2 Rectangulo arbitrary arbitrary
        arb n | n > 0 = oneof [liftM2 Rectangulo arbitrary arbitrary,
                               liftM2 Union sub sub,
                               liftM2 Diferencia sub sub]
              where sub = arb (n `div` 2)

Soluciones

import Test.QuickCheck
import Control.Monad

type Punto = (Float,Float)

data Region = Rectangulo Punto  Punto
            | Union      Region Region
            | Diferencia Region Region
            deriving (Eq, Show)

r0021, r3051, r4162 :: Region
r0021 = Rectangulo (0,0) (2,1)
r3051 = Rectangulo (3,0) (5,1)
r4162 = Rectangulo (4,1) (6,2)

enRegion :: Punto -> Region -> Bool
enRegion (x,y) (Rectangulo (x1,y1) (x2,y2)) =
    x1 <= x && x <= x2 && y1 <= y && y <= y2
enRegion p (Union  r1 r2) = enRegion p r1 || enRegion p r2
enRegion p (Diferencia r1 r2) = enRegion p r1 && not (enRegion p r2)

-- La propiedad es
prop_enRegion p r1 r2 =
    enRegion p r1 ==>
    (enRegion p (Union  r1 r2) &&
     enRegion p (Union  r2 r1) &&
     not (enRegion p (Diferencia r2 r1)))

-- La comprobación es
--    λ> quickCheckWith (stdArgs {maxDiscardRatio=20}) prop_enRegion
--    +++ OK, passed 100 tests.

-- Generador de regiones:
instance Arbitrary Region where
    arbitrary = sized arb where
        arb 0         = liftM2 Rectangulo arbitrary arbitrary
        arb n | n > 0 = oneof [liftM2 Rectangulo arbitrary arbitrary,
                               liftM2 Union sub sub,
                               liftM2 Diferencia sub sub]
              where sub = arb (n `div` 2)
...