向量叉积的坐标计算方法和二维空间几何意义：Jarvis 凸包算法，求解《587. 安装栅栏》

向量叉积的坐标计算方法和二维空间几何意义，用 Jarvis  凸包算法，求解《587. 安装栅栏》

向量叉积（向量叉乘）

• 坐标计算：如图上图所示
• 二维空间的几何意义：以两个向量为边的平行四边形面积

向量叉积（向量叉乘）坐标计算模板

const cross = (p, q, r)= => (q[0] - p[0]) * (r[1] - q[1]) - (q[1] - p[1]) * (r[0] - q[0]) // 向量 pq qr 的叉积

向量叉积的意义

• < 0 夹角 > 180 度，r 在 pq 右边
• = 0 夹角 = 180 度， r在 pq 所在直线上
• > 0 夹角 < 180 度，r 在 pq 左边

例题

587. 安装栅栏

在一个二维的花园中，有一些用 (x, y) 坐标表示的树。由于安装费用十分昂贵，你的任务是先用最短的绳子围起所有的树。只有当所有的树都被绳子包围时，花园才能围好栅栏。你需要找到正好位于栅栏边界上的树的坐标。

答案

Jarvis 算法

/**
 * @param {number[][]} trees
 * @return {number[][]}
 */
var outerTrees = function(trees) {
  const n = trees.length, visited = new Uint8Array(n), r = []
  if (n < 4) return trees
  const cross = (p, q, r) => (q[0] - p[0]) * (r[1] - q[1]) - (q[1] - p[1]) * (r[0] - q[0])
  let leftMin = 0
  for (let i = 1; i < n; i++) {
    if (trees[i][0] < trees[leftMin][0]) leftMin = i
  }
  let p = leftMin
  do {
    q = (p + 1) % n 
    for (let r = 0; r < n; r++) {
      if (r === p || r === q) continue
      if (cross(trees[p], trees[q], trees[r]) < 0) {
        q = r
      }
    }
    for (let i = 0; i < n; i++) {
      if (visited[i] === 1 || i === p || i === q) continue
      if (cross(trees[p], trees[q], trees[i]) === 0) {
        r.push(trees[i])
        visited[i] = 1
      }
    }
    if (visited[q] === 0) {
      r.push(trees[q])
      visited[q] = 1
    }
    p = q
  } while (p !== leftMin)
  return r
};

func outerTrees(trees [][]int) [][]int {
  n, leftMin := len(trees), 0
  for i := 1; i < n; i++ {
    if trees[i][0] < trees[leftMin][0] {
      leftMin = i
    } 
  }
  var ans [][]int
  p, visited := leftMin, make([]int, n) 
  for {
    q := (p + 1) % n
    for r := 0; r < n; r++ {
      if r == p || r == q {
        continue
      }
      if cross(trees[p], trees[q], trees[r]) < 0 {
        q = r
      }
    }
    for i := 0; i < n; i++ {
      if visited[i] == 1 || i == p || i == q {
        continue
      }
      if cross(trees[p], trees[q], trees[i]) == 0 {
        ans = append(ans, trees[i])
        visited[i] = 1
      }
    }
    if visited[q] == 0 {
      ans = append(ans, trees[q])
      visited[q] = 1
    } 
    p = q
    if p == leftMin {
      break
    }
  }
  return ans
}
func cross(p []int, q []int, r []int) int {
  return (q[0] - p[0]) * (r[1] - q[1]) - (q[1] - p[1]) *  (r[0] - q[0])
}