前言
最近日子苦还房贷 ，听人说大头菜现在商机很足，于是我决定自己去种大头菜，来实现快速的发家致富
image.png
好景不长，种的大肉菜才刚长出来一点点，昨天夜里就冒出来了一头野猪拱了我好几颗菜，看来必须要上栅栏了。但是怎么围栅栏这事难倒我了。
早先种大头菜的时候偷懒一把种子直接甩了出去，现如今长的七零八落。也不好把大头菜都拔起来再摆整齐种下去，这大大增加了围栅栏的难度。
但是没有关系！隔壁的猴子同学家里的菜园围的严严实实，一次也没被野猪偷过。找他来帮帮忙不就可以完美解决了吗？
image.png
想到这里我就以一颗长的最好看的大头菜为报酬，请了隔壁的猴子同学来授之以渔。
猴子同学的思路讲解
这个问题可以抽象为 凸包问题
在给定的点中，找出有限点构造一个最小凸边形，使其可以将给定的所有点都包含在内
最关键的一点是把所有的菜【一下简化为点】，都放在栅栏的内侧。所以可以从 判断点是否在线段的某一边 来下手。
image.png
判断点是否在线段的某一边
那么如何判断呢？这里要引入一个数学概念，叉乘
由叉乘的定义可知，在三维坐标系中。向量 a 叉乘 向量 b 可以得到一个垂直于 a b 向量组成平面的新向量 c，且它的模长等于向量 a b 形成的平行四边形面积。且 c 根据 a b 的方向不同，也会有自己的方向。这里可以根据右手定则来得知向量 c 的方向。
那么在这里，我们不需要用到全部 叉乘 的特点。由于我们凸包构造的是二维坐标系，那么扩展到三维的话 z 向量系数一定为 0。所以简单来说二维平面上三点 A, B, C 构造出的向量 ab 叉乘 ac 得出的向量必定是在 z 轴上的向量(0x, 0y, kz)。那么通过计算出单位向量 z 的系数 k。 如果 k > 0 ，那么点 C 在向量 ab 的左边。 k = 0， 点 C 在向量 ab 上。 k < 0，点 C 在向量 ab 右边。
叉乘的计算可以写为
image.png
所以如果在二维坐标系中，就可以简化为 U ✖️ V = (u1v2 - u2v1)k
这里把 u v 更换为 x y， 那么我们可以根据 (x1y2 - x2y1) 的值是否大于等于 0 来进行判断
然后以它为核心思想，从最基础的穷举方法来开始优化
给定 n 个点，那么会有 n * (n - 1) / 2 条线，对每一条线进行计算，剩余的 (n - 2) 个点是否都位于这点线段的一侧。如果是，那么这两点为 凸点。
穷举法复杂度为 O(n^3)
这里可以继续对穷举法进行优化，首先取纵坐标最小的一个点，如果有两个就取其中一个，它肯定在凸包上。
然后以它为极坐标中心，对剩下的所有点进行一个角度排序，排序结果如下图。
image.png
然后就按顺序依次对每一个点 开始依次尝试剩下的
个点，找到第一个满足条件的点【其他点都在
线段左侧】。
这样可以降低时间复杂度到 O(n^2)
到了这一步，想继续优化就得换一个思路，考虑是否可以不再对每一个点都进行尝试。Graham 介绍
这里通过从最低点开始，然后分析凸包的特点找规律，距离它角度最小的第一个点肯定是凸包上的点【当然角度最大的也是】，那么把 p0p1 入栈，接着考虑在线段 p1p2 是否是左转【可以想象一个人先沿着 p0p1 走，到了 p1 的时候是需要向左转还是向右转】。如果是向左，那么这个点入栈，继续下一个点。如果这个点向右，那么说明当前栈顶不是凸包上的点，出栈。然后再次拿栈顶两点来和当前拿的点比较。这样如此反复。
复杂度 O(n * log n)
最后附上 Graham 的简单实现。
// 叉乘
function crossProduct(p0, p1, p2) {
const vectorA = {
x: p1.x - p0.x,
y: p1.y - p0.y,
}
const vectorB = {
x: p2.x - p0.x,
y: p2.y - p0.y,
}
// 向量叉乘，这里简化了 z 轴
return vectorA.x * vectorB.y - vectorA.y * vectorB.x
}
function getConvexHull(pointData) {
const result = []
const arr = pointData.sort((a, b) => a.y - b.y)
const p0 = arr.shift()
// 最低点一定在凸包上，有多个最低点可以随便选一个
result.push(p0)
// 按角度排序
const sortedPoint = arr
.map((p) => {
const cos = (p.x - p0.x) / Math.sqrt(Math.pow(p.y - p0.y, 2) + Math.pow(p.x - p0.x, 2))
return {
...p,
cos,
}
})
.sort((a, b) => b.cos - a.cos)
.map((p) => {
return { x: p.x, y: p.y }
})
// 按照凸包的性质，第一个点必定在凸包上
result.push(sortedPoint.shift())
sortedPoint.forEach((p, index) => {
while (crossProduct(result[result.length - 2], result[result.length - 1], p) < 0) {
// 在右方，说明栈顶不是凸包上的点
result.pop()
}
// 在一条线上的情况，多去一个点，属于优化操作
if (crossProduct(result[result.length - 2], result[result.length - 1], p) === 0) result.pop()
// 在左边及线上
result.push(p)
})
return result
}
const pointData = [
{ x: 1, y: 28 },
{ x: 2, y: 1 },
{ x: 2, y: 12 },
{ x: 3, y: 46 },
{ x: 4, y: 1 },
{ x: 5, y: 11 },
{ x: 6, y: 21 },
{ x: 5, y: 51 },
{ x: 6, y: 1 },
{ x: 7, y: 43 },
{ x: 10, y: 45 },
]
const areaData = getConvexHull(JSON.parse(JSON.stringify(pointData)))
/*
* console areaData:
*
* {x: 2, y: 1}
* {x: 6, y: 1}
* {x: 10, y: 45}
* {x: 5, y: 51}
* {x: 3, y: 46}
* {x: 1, y: 28}
*/
后记
通过猴子同学的一番讲解操作，我成功的学会了如何围栅栏，虽然在最后大头菜经济泡沫了，但是万万没想到，我在这次经济泡沫中大肆兜售的【我不可能能用这么少的钱围起最好的栅栏】一书同样让我实现了财富自由。
-------------------
原文链接：[https://mp.weixin.qq.com/s/7Mek0vdv7r04zkj7oyISuw] (https://mp.weixin.qq.com/s/7Mek0vdv7r04zkj7oyISuw)
网友评论