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)和本声明。

分享到