<html><head></head><body style="word-wrap: break-word; -webkit-nbsp-mode: space; -webkit-line-break: after-white-space; ">I copy the Quick Hull snippet from&nbsp;<a href="http://darcs.haskell.org/packages/dph/examples/quickhull/QuickHull.hs">http://darcs.haskell.org/packages/dph/examples/quickhull/QuickHull.hs</a><br><div apple-content-edited="true">
<div>The "packed" expression in "hsplitList" is much confusing to me. Why does it have to zip points with cross? Is&nbsp;[ p | (c, p) &lt;- cross, c &gt; 0.0 ] not enough? Thanks.</div><div><div><br></div><div>data Point = Point !Double !Double</div><div>data Line &nbsp;= Line &nbsp;Point Point</div><div><br></div><div>instance Show Point where</div><div>&nbsp; show (Point x y) = show (x, y)</div><div><br></div><div>distance :: Point -&gt; Line -&gt; Double</div><div>distance (Point xo yo) (Line (Point x1 y1) (Point x2 y2))</div><div>&nbsp; = (x1 - xo) * (y2 - yo) - (y1 - yo) * (x2 - xo)</div><div>&nbsp;&nbsp;</div><div>upper :: (a -&gt; a -&gt; Bool) -&gt; [(a, b)] -&gt; b</div><div>upper above = snd . foldl1 pick</div><div>&nbsp; where</div><div>&nbsp; &nbsp; pick left@(kl, _) right@(kr, _) | kl `above` kr = left</div><div>&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; | otherwise &nbsp; &nbsp; = right</div><div><br></div><div>hsplitList :: [Point] -&gt; Line -&gt; [Point]</div><div>hsplitList points line@(Line p1 p2)</div><div>&nbsp; | length packed &lt; 2 = p1:packed</div><div>&nbsp; | otherwise &nbsp; &nbsp; &nbsp; &nbsp; = hsplitList packed (Line p1 pm) ++ hsplitList packed (Line pm p2)</div><div>&nbsp; where</div><div>&nbsp; &nbsp; cross &nbsp;= [ (distance p line, p) | p &lt;- points ]</div><div>&nbsp; &nbsp; packed = [ p | (p, (c, _)) &lt;- zip points cross, c &gt; 0.0 ]</div><div><br></div><div>&nbsp; &nbsp; pm &nbsp; &nbsp; = upper (&gt;) cross</div><div><br></div><div>quickHullList :: [Point] -&gt; [Point]</div><div>quickHullList [] = []</div><div>quickHullList points</div><div>&nbsp; = hsplitList points (Line minx maxx) ++ hsplitList points (Line maxx minx)</div><div>&nbsp; where</div><div>&nbsp; &nbsp; xs &nbsp; = [ (x, p) | p@(Point x y) &lt;- points ]</div><div>&nbsp; &nbsp; minx = upper (&lt;) xs</div><div>&nbsp; &nbsp; maxx = upper (&gt;) xs</div><div><br></div>Best regards,<br class="Apple-interchange-newline">Zhi-Qiang Lei</div><div><a href="mailto:zhiqiang.lei@gmail.com">zhiqiang.lei@gmail.com</a></div>
</div>
<br></body></html>