{"id":7001,"date":"2022-05-05T12:42:49","date_gmt":"2022-05-05T10:42:49","guid":{"rendered":"http:\/\/www.glc.us.es\/~jalonso\/exercitium\/?p=7001"},"modified":"2022-05-05T14:16:16","modified_gmt":"2022-05-05T12:16:16","slug":"puntos-en-regiones-rectangulares","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/puntos-en-regiones-rectangulares\/","title":{"rendered":"Puntos en regiones rectangulares"},"content":{"rendered":"<p>Los puntos se puede representar mediante pares de n\u00fameros<\/p>\n<pre lang=\"text\">\n   type Punto = (Int,Int)\n<\/pre>\n<p>y las regiones rectangulares mediante el siguiente tipo de dato<\/p>\n<pre lang=\"text\">\n   data Region = Rectangulo Punto  Punto\n               | Union      Region Region\n               | Diferencia Region Region\n     deriving (Eq, Show)\n<\/pre>\n<p>donde<\/p>\n<ul>\n<li><code>(Rectangulo p1 p2)<\/code> es la regi\u00f3n formada por un rect\u00e1ngulo cuyo v\u00e9rtice superior izquierdo es <code>p1<\/code> y su v\u00e9rtice inferior derecho es <code>p2<\/code>.<\/li>\n<li><code>(Union r1 r2)<\/code> es la regi\u00f3n cuyos puntos pertenecen a alguna de las regiones <code>r1<\/code> y <code>r2<\/code>.<\/li>\n<li><code>(Diferencia r1 r2)<\/code> es la regi\u00f3n cuyos puntos pertenecen a la regi\u00f3n <code>r1<\/code> pero no pertenecen a la <code>r2<\/code>.<\/li>\n<\/ul>\n<p>Definir la funci\u00f3n<\/p>\n<pre lang=\"text\">\n   enRegion :: Punto -> Region -> Bool\n<\/pre>\n<p>tal que <code>(enRegion p r)<\/code> se verifica si el punto <code>p<\/code> pertenece a la regi\u00f3n <code>r<\/code>. Por ejemplo, usando las regiones definidas por<\/p>\n<pre lang=\"text\">\n   r0021, r3051, r4162 :: Region\n   r0021 = Rectangulo (0,0) (2,1)\n   r3051 = Rectangulo (3,0) (5,1)\n   r4162 = Rectangulo (4,1) (6,2)\n<\/pre>\n<p>se tiene<\/p>\n<pre lang=\"text\">\n   enRegion (1,0) r0021                                   ==  True\n   enRegion (3,0) r0021                                   ==  False\n   enRegion (1,1) (Union r0021 r3051)                     ==  True\n   enRegion (4,0) (Union r0021 r3051)                     ==  True\n   enRegion (4,2) (Union r0021 r3051)                     ==  False\n   enRegion (3,1) (Diferencia r3051 r4162)                ==  True\n   enRegion (4,1) (Diferencia r3051 r4162)                ==  False\n   enRegion (4,2) (Diferencia r3051 r4162)                ==  False\n   enRegion (4,2) (Union (Diferencia r3051 r4162) r4162)  ==  True\n<\/pre>\n<p>Comprobar con QuickCheck que si el punto <code>p<\/code> est\u00e1 en la regi\u00f3n <code>r1<\/code>, entonces, para cualquier regi\u00f3n <code>r2<\/code>, <code>p<\/code> est\u00e1 en <code>(Union  r1 r2)<\/code> y en <code>(Union  r2 r1)<\/code>, pero no est\u00e1 en <code>(Diferencia r2 r1)<\/code>.<\/p>\n<h4>Soluciones<\/h4>\n<pre lang=\"haskell\">\nmodule Puntos_en_regiones_rectangulares where\n\nimport Test.QuickCheck (Arbitrary, Gen, Property, (==>), arbitrary, oneof,\n                        sized, generate, quickCheck, quickCheckWith, stdArgs,\n                        Args(maxDiscardRatio))\n\ntype Punto = (Int,Int)\n\ndata Region = Rectangulo Punto  Punto\n            | Union      Region Region\n            | Diferencia Region Region\n  deriving (Eq, Show)\n\nr0021, r3051, r4162 :: Region\nr0021 = Rectangulo (0,0) (2,1)\nr3051 = Rectangulo (3,0) (5,1)\nr4162 = Rectangulo (4,1) (6,2)\n\nenRegion :: Punto -> Region -> Bool\nenRegion (x,y) (Rectangulo (x1,y1) (x2,y2)) =\n  x1 <= x &#038;&#038; x <= x2 &#038;&#038;\n  y1 <= y &#038;&#038; y <= y2\nenRegion p (Union  r1 r2) =\n  enRegion p r1 || enRegion p r2\nenRegion p (Diferencia r1 r2) =\n  enRegion p r1 &#038;&#038; not (enRegion p r2)\n\n-- (regionArbitraria n) es un generador de regiones arbitrarias de orden\n-- n. Por ejemplo,\n--    \u03bb> generate (regionArbitraria 2)\n--    Rectangulo (30,-26) (-2,-8)\n--    \u03bb> generate (regionArbitraria 2)\n--    Union (Union (Rectangulo (-2,-5) (6,1)) (Rectangulo(3,7) (11,15)))\n--          (Diferencia (Rectangulo (9,8) (-2,6)) (Rectangulo (-2,2) (7,8)))\nregionArbitraria :: Int -> Gen Region\nregionArbitraria 0 =\n  Rectangulo <$> arbitrary <*> arbitrary\nregionArbitraria n =\n  oneof [Rectangulo <$> arbitrary <*> arbitrary,\n         Union <$> subregion <*> subregion,\n         Diferencia <$> subregion <*> subregion]\n  where subregion = regionArbitraria (n `div` 2)\n\n-- Region est\u00e1 contenida en Arbitrary\ninstance Arbitrary Region where\n  arbitrary = sized regionArbitraria\n\n-- La propiedad es\nprop_enRegion :: Punto -> Region -> Region -> Property\nprop_enRegion p r1 r2 =\n  enRegion p r1 ==>\n  (enRegion p (Union  r1 r2) &&\n   enRegion p (Union  r2 r1) &&\n   not (enRegion p (Diferencia r2 r1)))\n\n-- La comprobaci\u00f3n es\n--    \u03bb> quickCheck prop_enRegion\n--    *** Gave up! Passed only 78 tests; 1000 discarded tests.\n--\n--    \u03bb> quickCheckWith (stdArgs {maxDiscardRatio=20}) prop_enRegion\n--    +++ OK, passed 100 tests.\n<\/pre>\n<p>El c\u00f3digo se encuentra en <a href=\"https:\/\/github.com\/jaalonso\/Exercitium\/blob\/main\/src\/Puntos_en_regiones_rectangulares.hs\">GitHub<\/a>.<\/p>\n<p>La elaboraci\u00f3n de las soluciones se describe en el siguiente v\u00eddeo<\/p>\n<p><iframe loading=\"lazy\" width=\"560\" height=\"315\" src=\"https:\/\/www.youtube.com\/embed\/HOAi213vF4g\" title=\"YouTube video player\" frameborder=\"0\" allow=\"accelerometer; autoplay; clipboard-write; encrypted-media; gyroscope; picture-in-picture\" allowfullscreen><\/iframe><\/p>\n","protected":false},"excerpt":{"rendered":"<p>Los puntos se puede representar mediante pares de n\u00fameros type Punto = (Int,Int) 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\u00f3n formada por un rect\u00e1ngulo cuyo v\u00e9rtice superior izquierdo&#8230;<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"jetpack_post_was_ever_published":false,"_kad_post_transparent":"","_kad_post_title":"","_kad_post_layout":"","_kad_post_sidebar_id":"","_kad_post_content_style":"","_kad_post_vertical_padding":"","_kad_post_feature":"","_kad_post_feature_position":"","_kad_post_header":false,"_kad_post_footer":false,"_jetpack_newsletter_access":"","_jetpack_dont_email_post_to_subs":false,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"footnotes":"","_jetpack_memberships_contains_paid_content":false},"categories":[2],"tags":[483,567,550,568,523,564,553,565,6,518,566,146,133],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/7001"}],"collection":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/comments?post=7001"}],"version-history":[{"count":2,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/7001\/revisions"}],"predecessor-version":[{"id":7003,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/7001\/revisions\/7003"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/media?parent=7001"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/categories?post=7001"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/tags?post=7001"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}