Code

Haskell 的葛立恒扫描法

使用 Haskell 实现凸包葛立恒扫描法。最近在重温 Haskell，准备学习 Haskell 的并行编程。

相关链接

实现

  • 计算折线 <a, b, c> 方向时，使用有向面积判断：(px b-px a)*(py c-py a)-(py b-py a)*(px c-px a)，若该面积大于 0 则为左转，等于 0 则为直线，否则右转。
  • 将顶点列表按与初始顶点 P0 的夹角排序时，可能遇到 Px 刚好与 P0 垂直，因此斜率无法计算。但可直接计算折线方向，根据方向判断出栈/入栈。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
data Direction = TurnLeft | TurnRight | Straight deriving (Show, Eq)
data Point = Point{
    px :: Int,
    py :: Int
    } deriving (Show)

calcTurn :: Point -> Point -> Point -> Direction
calcTurn a b c = 
    if area == 0 then Straight
    else if area > 0 then TurnLeft
         else TurnRight
    where
        area = (px b-px a)*(py c-py a)-(py b-py a)*(px c-px a)

p1 = Point 1 1
p2 = Point 3 1
p3 = Point 4 3
p4 = Point 3 4
p5 = Point (-1) 3
p6 = Point 2 2
p7 = Point 2 3

points = [p1, p2, p3, p4, p5, p6, p7]

graham :: [Point] -> [Point]
graham graph = foldl makeStack [head . tail $ pList, p0] (tail . tail $ pList)
    where
        p0 = head . sortBy yco $ graph
        yco p1 p2 = if y1 == y2 then
                        if x1 < x2 then LT
                        else GT
                    else 
                        if y1 < y2 then LT
                        else GT
            where
                x1 = px p1
                x2 = px p2
                y1 = py p1
                y2 = py p2
        pList = sortBy angle $ graph
            where
                angle p1 p2 = if dir == TurnLeft || dir == Straight then LT else GT
                    where dir = calcTurn p0 p1 p2
        makeStack [pa] pn = pn : [pa]
        makeStack acc@(pa:pb:ps) pn@(Point x y) = if dir == TurnLeft || dir == Straight
                                                  then pn:acc
                                                  else makeStack (tail acc) pn
                                                  where
                                                        dir = calcTurn pb pa pn

原创作品，允许转载，转载时无需告知，但请务必以超链接形式标明文章原始出处(http://blog.forec.cn/2016/11/17/haskell-graham/) 、作者信息（Forec）和本声明。

分享到