# Find Convex Hull with Graham Scan & Swift

## 简单粗暴的想法

`func calculatePoint(pointP:CGPoint,onLine line:(pointA:CGPoint,pointB:CGPoint)) -> CGFloat {    return (pointP.y - line.pointA.y) * (line.pointB.x - line.pointA.x) - (line.pointB.y - line.pointA.y) * (pointP.x - line.pointA.x)}func checkPoint(P:CGPoint,inTriangle triangle:(A:CGPoint,B:CGPoint,C:CGPoint)) -> Bool {    var Pp = calculatePoint(P, onLine: (triangle.A,triangle.B))    let AB = Pp == 0||Pp * calculatePoint(triangle.C, onLine: (triangle.A,triangle.B)) > 0    if !AB{        return AB    }    Pp = calculatePoint(P, onLine: (triangle.A,triangle.C))    let AC = Pp == 0||Pp * calculatePoint(triangle.B, onLine: (triangle.A,triangle.C)) > 0    if !AC{        return AC    }    Pp = calculatePoint(P, onLine: (triangle.C,triangle.B))    let BC = Pp == 0||Pp * calculatePoint(triangle.A, onLine: (triangle.C,triangle.B)) > 0    return AB && AC && BC}`

`calculatePoint: onLine:` 函数的作用是将点坐标代入直线方程式并返回计算结果； `checkPoint: inTriangle:` 函数的作用是判断某点是否在三角形上或内部。

PS：这里注意我们想要的结果仅仅是 凸包顶点 ，有些点可能位于两个相邻的凸包顶点连线上，这样的点只能算作 凸包上的点 ，它们与 凸包内的点 一样需要被剔除。

1. `A` 点为中心，向量 `DA` 方向做射线逆时针扫描，按照扫描到点的顺序输出即可，直至 360° 扫描完毕。
2. 将直线 `AD` 上方的点集 `Su` 按照 X 值从大到小排列，下方的点集 `Sd` 按照 X 值从小到大排列，最后输出顺序为： `A，Sd，D，Su`

`func generateConvexHull(inout points:[PointView]){   for point in points {       point.isConvexHullNode = true   }      if points.count <= 3 {       return   }      var minXPoint = points[0]   var maxXPoint = points[0]   for point in points {       minXPoint = point.position.x < minXPoint.position.x ? point : minXPoint       maxXPoint = point.position.x > maxXPoint.position.x ? point : maxXPoint   }      let point1 = minXPoint;   for point2 in points {       if !point2.isConvexHullNode || point2 == point1 {           continue       }       for point3 in points {           if !point3.isConvexHullNode || point3 == point1 || point3 == point2 {               continue           }           for point4 in points {               if !point4.isConvexHullNode || point4 == point1 || point4 == point2 || point4 == point3 {                   continue               }               if checkPoint(point4.position, inTriangle: (point2.position,point3.position,point1.position)) {                   point4.isConvexHullNode = false                   continue               }           }       }   }      var su = points.filter {       calculatePoint(\$0.position, onLine: (minXPoint.position,maxXPoint.position)) > 0   }   var sl = points.filter {       calculatePoint(\$0.position, onLine: (minXPoint.position,maxXPoint.position)) < 0   }   su = su.sort {       return (\$0.position as CGPoint).x > (\$1.position as CGPoint).x   }   sl = sl.sort {       return (\$0.position as CGPoint).x < (\$1.position as CGPoint).x   }   var result = [minXPoint]   result += sl   result.append(maxXPoint)   result += su   points = result}`

`PointView` 是算法演示程序中用于绘制和存储二维点坐标信息的类，它不仅存储坐标，还维护了状态 `isConvexHullNode` ，并根据状态值是否为凸包顶点来改变 UI（红色的点为凸包顶点，紫色为非凸包顶点）。此外 `PointView` 还需要处理鼠标拖拽事件。这部分比较简单，就不上代码了。

## Graham Scan

PS:判断 `P1P2P3``P2` 拐弯方向公式： `(p2.x - p1.x) * (p3.y - p1.y) - (p2.y - p1.y) * (p3.x - p1.x)` ，如果其结果为 `0` ，这三个点是共线的，如果其结果为正，这三个点是向左拐的，否则，它是向右拐的。

`P` 为原点的极坐标下按照极角大小构造顺时针排序的数组： `[A,B,C,D]` ，计算极角的函数实现如下：

`func calculatePolarAngle(origin:CGPoint, target:CGPoint) -> Double {    let trans = (x: target.x - origin.x, y: target.y - origin.y)    let angle = atan(Double(trans.y) / Double(trans.x))    switch trans {    case let (x,y) where x >= 0 && y >= 0:        return angle    case let (x,y) where x < 0 && y >= 0:        return angle + M_PI    case let (x,y) where x <= 0 && y < 0:        return angle + M_PI    case let (x,y) where x > 0 && y < 0:        return angle + 2 * M_PI    default:        return 0    }}`

`func generateConvexHull(inout points: [PointView]) {   for point in points {       point.isConvexHullNode = true   }      if points.count <= 3 {       return   }      var minYPoint = points[0]   var minIndex = 0   for (index,point) in points.enumerate() {       (minIndex,minYPoint) = point.position.y < minYPoint.position.y ? (index,point) : (minIndex,minYPoint)   }   points.removeAtIndex(minIndex)   points.sortInPlace {       return calculatePolarAngle(minYPoint.position, target: \$0.position) < calculatePolarAngle(minYPoint.position, target: \$1.position)   }   var stack = [minYPoint]   var restPoints = [PointView]()   stack.append(points[0])      for point in points[1..<points.count] {              func checkTurnsRight() -> Bool {           let p1 = stack[stack.count-2].position           let p2 = stack.last!.position           let p3 = point.position           return (p2.x - p1.x) * (p3.y - p1.y) - (p2.y - p1.y) * (p3.x - p1.x) <= 0       }              while checkTurnsRight() {           stack.last?.isConvexHullNode = false           restPoints.append(stack.last!)           stack.removeLast()           if stack.count < 3 {               break           }       }       stack.append(point)   }   points = stack + restPoints}`

Graham Scan 的时间复杂度是 `O(nlogn)` ，而且只适用于二维平面。算法导论上也讲到了包裹法（Jarvis步进法）和分治法，时间复杂度都是 `O(nlogn)` 。我的 那个工程 里也有 分治法的 Swift 实现 。如果拓展到多维空间，我觉得使用 Swift 并不是一个很好的实现语言，Matlab 再适合不过了。