Ir al contenido principal

Puntos en regiones rectangulares

(actualizado )

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 o 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).

Soluciones

import Test.Hspec (Spec, describe, hspec, it, shouldBe)
import Test.QuickCheck (Arbitrary, Gen, Property, (==>), arbitrary, oneof,
                        sized, generate, quickCheck, quickCheckWith, stdArgs,
                        Args(maxDiscardRatio))

type Punto = (Int,Int)

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)

-- 1ª solución
-- ===========

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

-- 2ª solución
-- ===========

enRegion2 :: Punto -> Region -> Bool
enRegion2 (x, y) (Rectangulo (x1, y1) (x2, y2)) =
  and [x1 <= x, x <= x2, y1 <= y, y <= y2]
enRegion2 p (Union r1 r2) =
  or [enRegion2 p r1, enRegion2 p r2]
enRegion2 p (Diferencia r1 r2) =
  and [enRegion2 p r1, not (enRegion2 p r2)]

-- 3ª solución
-- ===========

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

-- Verificación
-- ============

verifica :: IO ()
verifica = hspec spec

specG :: (Punto -> Region -> Bool) -> Spec
specG enRegion = do
  it "e1" $
    enRegion (1,0) r0021                                   `shouldBe`  True
  it "e2" $
    enRegion (3,0) r0021                                   `shouldBe`  False
  it "e3" $
    enRegion (1,1) (Union r0021 r3051)                     `shouldBe`  True
  it "e4" $
    enRegion (4,0) (Union r0021 r3051)                     `shouldBe`  True
  it "e5" $
    enRegion (4,2) (Union r0021 r3051)                     `shouldBe`  False
  it "e6" $
    enRegion (3,1) (Diferencia r3051 r4162)                `shouldBe`  True
  it "e7" $
    enRegion (4,1) (Diferencia r3051 r4162)                `shouldBe`  False
  it "e8" $
    enRegion (4,2) (Diferencia r3051 r4162)                `shouldBe`  False
  it "e9" $
    enRegion (4,2) (Union (Diferencia r3051 r4162) r4162)  `shouldBe`  True

spec :: Spec
spec = do
  describe "def. 1" $ specG enRegion1
  describe "def. 2" $ specG enRegion2
  describe "def. 3" $ specG enRegion3

-- La verificación es
--    λ> verifica
--    27 examples, 0 failures

-- Comprobación de equivalencia
-- ============================

-- (regionArbitraria n) es un generador de regiones arbitrarias de orden
-- n. Por ejemplo,
--    λ> generate (regionArbitraria 2)
--    Rectangulo (30,-26) (-2,-8)
--    λ> generate (regionArbitraria 2)
--    Union (Union (Rectangulo (-2,-5) (6,1)) (Rectangulo(3,7) (11,15)))
--          (Diferencia (Rectangulo (9,8) (-2,6)) (Rectangulo (-2,2) (7,8)))
regionArbitraria :: Int -> Gen Region
regionArbitraria 0 =
  Rectangulo <$> arbitrary <*> arbitrary
regionArbitraria n =
  oneof [Rectangulo <$> arbitrary <*> arbitrary,
         Union <$> subregion <*> subregion,
         Diferencia <$> subregion <*> subregion]
  where subregion = regionArbitraria (n `div` 2)

-- Region está contenida en Arbitrary
instance Arbitrary Region where
  arbitrary = sized regionArbitraria

-- La propiedad es
prop_equivalencia :: Punto -> Region -> Bool
prop_equivalencia p r =
  all (== enRegion1 p r)
      [enRegion2 p r,
       enRegion3 p r]

-- La comprobación es
--    λ> quickCheck prop_equivalencia
--    +++ OK, passed 100 tests.

-- Comparación de eficiencia
-- =========================

ejRegion:: Region
ejRegion = foldl1 Union [Rectangulo (i, 0) (i + 5, 1) | i <- [0..5000]]

ejPuntos :: [Punto]
ejPuntos = [(x, y) | x <- [0..500], y <- [0, 5]]

-- La comparación es
--    λ> length (filter (\p -> enRegion1 p ejRegion) ejPuntos)
--    501
--    (2.21 secs, 1,666,408,488 bytes)
--    λ> length (filter (\p -> enRegion2 p ejRegion) ejPuntos)
--    501
--    (3.55 secs, 3,852,610,152 bytes)
--    λ> length (filter (\p -> enRegion3 p ejRegion) ejPuntos)
--    501
--    (2.12 secs, 1,856,975,528 bytes)

-- Propiedades
-- ===========

-- La propiedad es
prop_enRegion :: Punto -> Region -> Region -> Property
prop_enRegion p r1 r2 =
  enRegion1 p r1 ==>
  (enRegion1 p (Union  r1 r2) &&
   enRegion1 p (Union  r2 r1) &&
   not (enRegion1 p (Diferencia r2 r1)))

-- La comprobación es
--    λ> quickCheck prop_enRegion
--    *** Gave up! Passed only 78 tests; 1000 discarded tests.
--
--    λ> quickCheckWith (stdArgs {maxDiscardRatio=20}) prop_enRegion
--    +++ OK, passed 100 tests.