[Haskell-beginners] A strange expression in Quick Hull example

24 Apr 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@gmail.com