[Haskell-beginners] A strange expression in Quick Hull example
Zhi-Qiang Lei
zhiqiang.lei at gmail.com
Tue Apr 24 22:36:32 CEST 2012
I copy the Quick Hull snippet from http://darcs.haskell.org/packages/dph/examples/quickhull/QuickHull.hs
The "packed" expression in "hsplitList" is much confusing to me. Why does it have to zip points with cross? Is [ p | (c, p) <- cross, c > 0.0 ] not enough? Thanks.
data Point = Point !Double !Double
data Line = Line Point Point
instance Show Point where
show (Point x y) = show (x, y)
distance :: Point -> Line -> Double
distance (Point xo yo) (Line (Point x1 y1) (Point x2 y2))
= (x1 - xo) * (y2 - yo) - (y1 - yo) * (x2 - xo)
upper :: (a -> a -> Bool) -> [(a, b)] -> b
upper above = snd . foldl1 pick
where
pick left@(kl, _) right@(kr, _) | kl `above` kr = left
| otherwise = right
hsplitList :: [Point] -> Line -> [Point]
hsplitList points line@(Line p1 p2)
| length packed < 2 = p1:packed
| otherwise = hsplitList packed (Line p1 pm) ++ hsplitList packed (Line pm p2)
where
cross = [ (distance p line, p) | p <- points ]
packed = [ p | (p, (c, _)) <- zip points cross, c > 0.0 ]
pm = upper (>) cross
quickHullList :: [Point] -> [Point]
quickHullList [] = []
quickHullList points
= hsplitList points (Line minx maxx) ++ hsplitList points (Line maxx minx)
where
xs = [ (x, p) | p@(Point x y) <- points ]
minx = upper (<) xs
maxx = upper (>) xs
Best regards,
Zhi-Qiang Lei
zhiqiang.lei at gmail.com
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.haskell.org/pipermail/beginners/attachments/20120425/919d9fea/attachment.htm>
More information about the Beginners
mailing list