前言
最近日子苦還房貸 腻贰，聽(tīng)人說(shuō)大頭菜現(xiàn)在商機(jī)很足吁恍，于是我決定自己去種大頭菜，來(lái)實(shí)現(xiàn)快速的發(fā)家致富
好景不長(zhǎng)银受，種的大肉菜才剛長(zhǎng)出來(lái)一點(diǎn)點(diǎn)践盼，昨天夜里就冒出來(lái)了一頭野豬拱了我好幾顆菜，看來(lái)必須要上柵欄了宾巍。但是怎么圍柵欄這事難倒我了咕幻。
早先種大頭菜的時(shí)候偷懶一把種子直接甩了出去，現(xiàn)如今長(zhǎng)的七零八落顶霞。也不好把大頭菜都拔起來(lái)再擺整齊種下去肄程，這大大增加了圍柵欄的難度。
但是沒(méi)有關(guān)系选浑！隔壁的猴子同學(xué)家里的菜園圍的嚴(yán)嚴(yán)實(shí)實(shí)蓝厌，一次也沒(méi)被野豬偷過(guò)。找他來(lái)幫幫忙不就可以完美解決了嗎古徒？
想到這里我就以一顆長(zhǎng)的最好看的大頭菜為報(bào)酬拓提，請(qǐng)了隔壁的猴子同學(xué)來(lái)授之以漁。
猴子同學(xué)的思路講解
這個(gè)問(wèn)題可以抽象為 凸包問(wèn)題
在給定的點(diǎn)中隧膘，找出有限點(diǎn)構(gòu)造一個(gè)最小凸邊形代态，使其可以將給定的所有點(diǎn)都包含在內(nèi)
最關(guān)鍵的一點(diǎn)是把所有的菜【一下簡(jiǎn)化為點(diǎn)】寺惫，都放在柵欄的內(nèi)側(cè)。所以可以從 判斷點(diǎn)是否在線段的某一邊 來(lái)下手蹦疑。
判斷點(diǎn)是否在線段的某一邊
那么如何判斷呢西雀？這里要引入一個(gè)數(shù)學(xué)概念，叉乘
由叉乘的定義可知歉摧，在三維坐標(biāo)系中艇肴。向量 a 叉乘 向量 b 可以得到一個(gè)垂直于 a b 向量組成平面的新向量 c，且它的模長(zhǎng)等于向量 a b 形成的平行四邊形面積叁温。且 c 根據(jù) a b 的方向不同再悼，也會(huì)有自己的方向。這里可以根據(jù)右手定則來(lái)得知向量 c 的方向券盅。
那么在這里帮哈，我們不需要用到全部 叉乘 的特點(diǎn)。由于我們凸包構(gòu)造的是二維坐標(biāo)系锰镀，那么擴(kuò)展到三維的話 z 向量系數(shù)一定為 0娘侍。所以簡(jiǎn)單來(lái)說(shuō)二維平面上三點(diǎn) A, B, C 構(gòu)造出的向量 ab 叉乘 ac 得出的向量必定是在 z 軸上的向量(0x, 0y, kz)。那么通過(guò)計(jì)算出單位向量 z 的系數(shù) k泳炉。 如果 k > 0 憾筏，那么點(diǎn) C 在向量 ab 的左邊。 k = 0花鹅， 點(diǎn) C 在向量 ab 上氧腰。 k < 0，點(diǎn) C 在向量 ab 右邊刨肃。
叉乘的計(jì)算可以寫(xiě)為
所以如果在二維坐標(biāo)系中古拴，就可以簡(jiǎn)化為 U ?? V = (u1v2 - u2v1)k
這里把 u v 更換為 x y， 那么我們可以根據(jù) (x1y2 - x2y1) 的值是否大于等于 0 來(lái)進(jìn)行判斷
然后以它為核心思想真友，從最基礎(chǔ)的窮舉方法來(lái)開(kāi)始優(yōu)化
給定 n 個(gè)點(diǎn)黄痪，那么會(huì)有 n * (n - 1) / 2 條線，對(duì)每一條線進(jìn)行計(jì)算盔然，剩余的 (n - 2) 個(gè)點(diǎn)是否都位于這點(diǎn)線段的一側(cè)桅打。如果是，那么這兩點(diǎn)為 凸點(diǎn)愈案。
窮舉法復(fù)雜度為 O(n^3)
這里可以繼續(xù)對(duì)窮舉法進(jìn)行優(yōu)化挺尾，首先取縱坐標(biāo)最小的一個(gè)點(diǎn)，如果有兩個(gè)就取其中一個(gè)站绪，它肯定在凸包上遭铺。
然后以它為極坐標(biāo)中心，對(duì)剩下的所有點(diǎn)進(jìn)行一個(gè)角度排序，排序結(jié)果如下圖掂僵。
然后就按順序依次對(duì)每一個(gè)點(diǎn) 開(kāi)始依次嘗試剩下的
個(gè)點(diǎn)航厚，找到第一個(gè)滿足條件的點(diǎn)【其他點(diǎn)都在
線段左側(cè)】。
這樣可以降低時(shí)間復(fù)雜度到 O(n^2)
到了這一步锰蓬，想繼續(xù)優(yōu)化就得換一個(gè)思路，考慮是否可以不再對(duì)每一個(gè)點(diǎn)都進(jìn)行嘗試眯漩。Graham 介紹
這里通過(guò)從最低點(diǎn)開(kāi)始芹扭，然后分析凸包的特點(diǎn)找規(guī)律，距離它角度最小的第一個(gè)點(diǎn)肯定是凸包上的點(diǎn)【當(dāng)然角度最大的也是】赦抖，那么把 p0p1 入棧舱卡，接著考慮在線段 p1p2 是否是左轉(zhuǎn)【可以想象一個(gè)人先沿著 p0p1 走，到了 p1 的時(shí)候是需要向左轉(zhuǎn)還是向右轉(zhuǎn)】队萤。如果是向左轮锥，那么這個(gè)點(diǎn)入棧，繼續(xù)下一個(gè)點(diǎn)要尔。如果這個(gè)點(diǎn)向右舍杜，那么說(shuō)明當(dāng)前棧頂不是凸包上的點(diǎn)，出棧赵辕。然后再次拿棧頂兩點(diǎn)來(lái)和當(dāng)前拿的點(diǎn)比較既绩。這樣如此反復(fù)。
復(fù)雜度 O(n * log n)
最后附上 Graham 的簡(jiǎn)單實(shí)現(xiàn)还惠。
// 叉乘
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,
}
// 向量叉乘饲握，這里簡(jiǎn)化了 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()
// 最低點(diǎn)一定在凸包上，有多個(gè)最低點(diǎn)可以隨便選一個(gè)
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 }
})
// 按照凸包的性質(zhì)蚕键，第一個(gè)點(diǎn)必定在凸包上
result.push(sortedPoint.shift())
sortedPoint.forEach((p, index) => {
while (crossProduct(result[result.length - 2], result[result.length - 1], p) < 0) {
// 在右方救欧，說(shuō)明棧頂不是凸包上的點(diǎn)
result.pop()
}
// 在一條線上的情況，多去一個(gè)點(diǎn)锣光，屬于優(yōu)化操作
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}
*/
后記
通過(guò)猴子同學(xué)的一番講解操作笆怠，我成功的學(xué)會(huì)了如何圍柵欄，雖然在最后大頭菜經(jīng)濟(jì)泡沫了嫉晶，但是萬(wàn)萬(wàn)沒(méi)想到骑疆，我在這次經(jīng)濟(jì)泡沫中大肆兜售的【我不可能能用這么少的錢圍起最好的柵欄】一書(shū)同樣讓我實(shí)現(xiàn)了財(cái)富自由。
-------------------
原文鏈接：[https://mp.weixin.qq.com/s/7Mek0vdv7r04zkj7oyISuw] (https://mp.weixin.qq.com/s/7Mek0vdv7r04zkj7oyISuw)
