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