# Difference between revisions of "Graham Scan Implementation"

Descriptions of this problem can be found in Real World Haskell, Chapter 3

```import Data.List (sortBy)
import Data.Function (on)

-- define data `Direction`
data Direction = GoLeft | GoRight | GoStraight
deriving (Show, Eq)

-- determine direction change via point a->b->c
-- -- define 2D point
data Pt = Pt (Double, Double) deriving (Show, Eq, Ord)
isTurned :: Pt -> Pt -> Pt -> Direction
isTurned (Pt (ax, ay)) (Pt (bx, by)) (Pt (cx, cy)) = case sign of
EQ -> GoStraight
LT -> GoRight
GT -> GoLeft
where sign = compare ((bx - ax) * (cy - ay))
((cx - ax) * (by - ay))

-- implement Graham scan algorithm

-- -- Helper functions
-- -- Find the most button left point
buttonLeft :: [Pt] -> Pt
buttonLeft [] = Pt (1/0, 1/0)
buttonLeft [pt] = pt
buttonLeft (pt:pts) = minY pt (buttonLeft pts) where
minY (Pt (ax, ay)) (Pt (bx, by))
| ay > by = Pt (bx, by)
| ay < by = Pt (ax, ay)
| ax < bx = Pt (ax, ay)
| otherwise = Pt (bx, by)

-- -- Main
convex :: [Pt] -> [Pt]
convex []   = []
convex [pt] = [pt]
convex [pt0, pt1] = [pt0, pt1]
convex pts = scan [pt0] spts where
-- Find the most buttonleft point pt0
pt0 = buttonLeft pts

-- Sort other points `ptx` based on angle <pt0->ptx>
spts = tail (sortBy (compare `on` compkey pt0) pts) where
compkey (Pt (ax, ay)) (Pt (bx, by)) = (atan2 (by - ay) (bx - ax),
{-the secondary key make sure collinear points in order-}
abs (bx - ax))

-- Scan the points to find out convex
-- -- handle the case that all points are collinear
scan [p0] (p1:ps)
| isTurned pz p0 p1 == GoStraight = [pz, p0]
where pz = last ps

scan (x:xs) (y:z:rsts) = case isTurned x y z of
GoRight    -> scan xs (x:z:rsts)
GoStraight -> scan (x:xs) (z:rsts) -- I choose to skip the collinear points
GoLeft     -> scan (y:x:xs) (z:rsts)
scan xs [z] =  z : xs

-- Test data
pts1 = [Pt (0,0), Pt (1,0), Pt (2,1), Pt (3,1), Pt (2.5,1), Pt (2.5,0), Pt (2,0)]
--                           (2,1)--(2.5,1)<>(3,1)
--                         ->          |
--                     ----            v
-- (0,0)------->(1,0)--      (2,0)<-(2.5,0)
pts2 = [Pt (1,-2), Pt (-1, 2), Pt (-3, 6), Pt (-7, 3)]
-- -- This case demonstrate a collinear points across the button-left point
--                |-----(-3,6)
--           |-----         ^__
--      <-----                |---
--  (-7,3)                       |
--     |--                      (-1,2)
--       |----                       <--
--           |-------------            |--|
--                        |------------>(1,-2)
pts3 = [Pt (6,0), Pt (5.5,2), Pt (5,2), Pt (0,4), Pt (1,4), Pt (6,4), Pt (0,0)]
-- -- This case demonstrates a consecutive inner points
-- (0,4)<-(1,4)<--------------------(6,4)
--   |                    |-----------^
--   v                  (5,2)<(5.5,2)<-|
-- (0,0)--------------------------->(6,0)

pts4 = [Pt (0,0), Pt (0,4), Pt (1,4), Pt (2,3), Pt (6,5), Pt (6,0)]
-- -- This case demonstrates a consecutive inner points

-- collinear points
pts5 = [Pt (5,5), Pt (4,4), Pt (3,3), Pt (2,2), Pt (1,1)]
pts6 = reverse pts5
```
{"ft_lang_label":"__label__en","ft_lang_prob":0.5872176,"math_prob":0.9972426,"size":9891,"snap":"2020-24-2020-29","text_gpt3_token_len":3867,"char_repetition_ratio":0.16364923,"word_repetition_ratio":0.2746594,"special_character_ratio":0.54200786,"punctuation_ratio":0.22611465,"nsfw_num_words":0,"has_unicode_error":false,"math_prob_llama3":0.999605,"pos_list":[0],"im_url_duplicate_count":[null],"WARC_HEADER":"{\"WARC-Type\":\"response\",\"WARC-Date\":\"2020-05-26T08:03:12Z\",\"WARC-Record-ID\":\"<urn:uuid:a5b6b484-8550-46b1-a0ee-e7abea19cff0>\",\"Content-Length\":\"69811\",\"Content-Type\":\"application/http; msgtype=response\",\"WARC-Warcinfo-ID\":\"<urn:uuid:70ead2b8-9b28-43bf-9aeb-a17532ab9142>\",\"WARC-Concurrent-To\":\"<urn:uuid:372e5d6c-d7bc-49fc-975f-df9574de5cc1>\",\"WARC-IP-Address\":\"199.232.65.175\",\"WARC-Target-URI\":\"https://wiki.haskell.org/index.php?title=Graham_Scan_Implementation&diff=57856&oldid=56458\",\"WARC-Payload-Digest\":\"sha1:34AGTBDCT7RKJR7VHOWEPMWUFPAPEEWU\",\"WARC-Block-Digest\":\"sha1:A7OTXBDBWDGTNPU6452WTNELUTLSP4OY\",\"WARC-Identified-Payload-Type\":\"text/html\",\"warc_filename\":\"/cc_download/warc_2020/CC-MAIN-2020-24/CC-MAIN-2020-24_segments_1590347390448.11_warc_CC-MAIN-20200526050333-20200526080333-00476.warc.gz\"}"}