0votos

El rectángulo más grande en Haskell

por josejuan hace 5 años

Aquí encaja perfectamente el uso de scanlines, permite computar como secuencia toda la imagen.

Dada una imagen de tamaño fijo y de fondo siempre blanco con una cantidad variable de rectángulos de color negro de diferentes tamaños Calcular el rectángulo más grande (mayor altura y anchura) y diferenciarlo visualmente (con cualquier otro color) de los demás.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
import Graphics.GD 
import System.Environment 
import Data.Maybe 
import Data.List 
import Control.Monad 
 
-- Convierte cada ···11111····111······111··· en [(a,b,y),(a,b,y),...] 
imageToScanLines = map (\(y, xs) -> map (\g -> (minimum g, maximum g, y)) $ 
                                    map (map fst) $ groupBy (\_(_,a)->a==1) $ zip xs $ 1:zipWith(-)(tail xs)xs) 
 
-- Obtiene los rectángulos reduciendo los scanlines 
searchBoxes = foldl f [] . concat . imageToScanLines 
  where f [] (ax,bx,y) = [((ax,y),(bx,y))] 
        f (u@(a@(ax,_),(bx,y)):us) p@(pax, pbx, yp) = if ax == pax && bx == pbx && y+1 == yp 
                                                        then (a,(bx,yp)):us 
                                                        else u: f us p 
 
-- El de más área (si hay alguno) 
searchBigBox = listToMaybe . sortBy (\a b -> (boxSize b) `compare` (boxSize a)) . searchBoxes 
 
boxSize ((ax, ay), (bx, by)) = (bx - ax + 1) * (by - ay + 1) 
 
main = do 
  (fin:fout:_) <- getArgs 
  img <- loadPngFile fin 
  (w, h) <- imageSize img 
  pin <- forM [0..h-1] $ \y -> do 
           xs <- forM [0..w-1] $ \x -> do 
                   c <- getPixel (x, y) img 
                   return (x, c == 0) 
           return (y, map fst $ filter snd xs) 
  case searchBigBox pin of 
    Nothing -> putStrLn "Box not found!" 
    Just (a, b) -> drawFilledRectangle a b (rgb 255 50 50) img >> 
                   savePngFile fout img 

Comenta la solución

Tienes que identificarte para poder publicar tu comentario.