iOS地图上已知多个坐标画多边形

背景：已知多个商家的坐标，在地图上画一个区域。
问题：把所有的坐标放进去画的多边形非常难看。

我们把已知的点都放在地图上，找到这些点组成的区域最外层的点，画出来的区域就好看多了，最后了解到有一个凸包算法。

GrahamScanDemo.gif

图片来源：https://en.wikipedia.org/wiki/Graham_scan

使用ChatGPT写一个凸包算法，代码如下：

struct Point {
    let x: Double
    let y: Double
}

func orientation(p: Point, q: Point, r: Point) -> Double {
    let value = (q.y - p.y) * (r.x - q.x) - (q.x - p.x) * (r.y - q.y)
    if value == 0 {
        return 0 // p, q, r三点共线
    } else if value > 0 {
        return 1 // 逆时针方向
    } else {
        return 2 // 顺时针方向
    }
}

func convexHull(points: [Point]) -> [Point] {
    let n = points.count
    if n < 3 {
        return []
    }
    
    var hull = [Point]()
    
    var l = 0
    for i in 1..<n {
        if points[i].x < points[l].x {
            l = i
        }
    }
    
    var p = l, q = 0
    repeat {
        hull.append(points[p])
        q = (p + 1) % n
        
        for i in 0..<n {
            if orientation(p: points[p], q: points[i], r: points[q]) == 2 {
                q = i
            }
        }
        
        p = q
    } while p != l
    
    return hull
}

// 使用示例
let points = [
    Point(x: 0, y: 3),
    Point(x: 2, y: 2),
    Point(x: 1, y: 1),
    Point(x: 2, y: 1),
    Point(x: 3, y: 0),
    Point(x: 0, y: 0),
    Point(x: 3, y: 3)
]

let hull = convexHull(points: points)
print(hull) // 输出: [Point(x: 0.0, y: 0.0), Point(x: 3.0, y: 0.0), Point(x: 3.0, y: 3.0), Point(x: 0.0, y: 3.0)]

搬个砖，记录一下。

后续：
以下是可以使用的swift代码

extension LineMapViewController {
    
    struct Point {
        var x: Double
        var y: Double
    }

    func crossProduct(p1: Point, p2: Point, p3: Point) -> Double {
        return (p2.x - p1.x) * (p3.y - p1.y) - (p2.y - p1.y) * (p3.x - p1.x)
    }

    func getConvexHull(points: [Point]) -> [Point] {
        if points.count <= 1 {
            return points
        }
        
        let sortedPoints = points.sorted { (a, b) -> Bool in
            if a.x == b.x {
                return a.y < b.y
            }
            return a.x < b.x
        }
        
        var lowerHull: [Point] = []
        for i in 0..<sortedPoints.count {
            while lowerHull.count >= 2 && crossProduct(p1: lowerHull[lowerHull.count - 2], p2: lowerHull[lowerHull.count - 1], p3: sortedPoints[i]) <= 0 {
                lowerHull.removeLast()
            }
            lowerHull.append(sortedPoints[i])
        }
        
        var upperHull: [Point] = []
        for i in stride(from: sortedPoints.count - 1, through: 0, by: -1) {
            while upperHull.count >= 2 && crossProduct(p1: upperHull[upperHull.count - 2], p2: upperHull[upperHull.count - 1], p3: sortedPoints[i]) <= 0 {
                upperHull.removeLast()
            }
            upperHull.append(sortedPoints[i])
        }
        upperHull.removeLast()
        lowerHull.removeLast()
        return lowerHull + upperHull
    }
}

以下是可以使用的go代码

type Point struct {
    X float64
    Y float64
}

func crossProduct(p1, p2, p3 Point) float64 {
    return (p2.X-p1.X)*(p3.Y-p1.Y) - (p2.Y-p1.Y)*(p3.X-p1.X)
}

func GetConvexHull(points []Point) []Point {
    if len(points) <= 1 {
        return points
    }

    sort.Slice(points, func(i, j int) bool {
        if points[i].X == points[j].X {
            return points[i].Y < points[j].Y
        }
        return points[i].X < points[j].X
    })

    var lowerHull []Point
    for i := 0; i < len(points); i++ {
        for len(lowerHull) >= 2 && crossProduct(lowerHull[len(lowerHull)-2], lowerHull[len(lowerHull)-1], points[i]) <= 0 {
            lowerHull = lowerHull[:len(lowerHull)-1]
        }
        lowerHull = append(lowerHull, points[i])
    }

    var upperHull []Point
    for i := len(points) - 1; i >= 0; i-- {
        for len(upperHull) >= 2 && crossProduct(upperHull[len(upperHull)-2], upperHull[len(upperHull)-1], points[i]) <= 0 {
            upperHull = upperHull[:len(upperHull)-1]
        }
        upperHull = append(upperHull, points[i])
    }
    upperHull = upperHull[:len(upperHull)-1]
    lowerHull = lowerHull[:len(lowerHull)-1]
    return append(lowerHull, upperHull...)
}

以下是js的代码

/**
 *      p2
 *  p1<
 *      p3
 * 叉积判断 p1p2 p1p3
 * | p2.x-p1.x | p2.y-p1.y |
 * | p3.x-p1.x | p3.y-p1.y |
 * @param {{x:number,y:number}} p1 
 * @param {{x:number,y:number}} p2 
 * @param {{x:number,y:number}} p3 
 */
function crossProduct(p1, p2, p3) {
  return (p2.x - p1.x) * (p3.y - p1.y) - (p2.y - p1.y) * (p3.x - p1.x);
}

/**
 * 
 * @param {{x:number,y:number}[]} points 
 */
function getConvexHull(points) {

  if (points.length <= 1) { return points; }

  //按照x坐标排序 
  points.sort((a, b) => a.x - b.x || a.y - b.y);
  let lowerHull = [];
  for (let i = 0; i < points.length; i++) {
    //构建下凸包

    // 遍历凸包数据集判断当前点Pi是否在 H(n-2)H(n-1)的内侧(叉积<0)，如果在内侧就移除H(n-1) 
    while (
      lowerHull.length >= 2 && 
      crossProduct(lowerHull[lowerHull.length - 2], lowerHull[lowerHull.length - 1], points[i]) <= 0
    ) {
      lowerHull.pop();
    }
    lowerHull.push(points[i]);
  }
  let upperHull = [];
  for (let i = points.length - 1; i >= 0; i--) {
    //构建上凸包
    while (
      upperHull.length >= 2 && 
      crossProduct(upperHull[upperHull.length - 2], upperHull[upperHull.length - 1], points[i]) <= 0) {
      upperHull.pop();
    }
    upperHull.push(points[i]);
  }
  //合并上下凸包 
  upperHull.pop();
  lowerHull.pop();
  return lowerHull.concat(upperHull);
}