前言
最近日子苦還房貸 ，聽人說大頭菜現(xiàn)在商機很足，于是我決定自己去種大頭菜，來實現(xiàn)快速的發(fā)家致富
好景不長，種的大肉菜才剛長出來一點點，昨天夜里就冒出來了一頭野豬拱了我好幾顆菜，看來必須要上柵欄了。但是怎么圍柵欄這事難倒我了。
早先種大頭菜的時候偷懶一把種子直接甩了出去，現(xiàn)如今長的七零八落。也不好把大頭菜都拔起來再擺整齊種下去，這大大增加了圍柵欄的難度。
但是沒有關(guān)系！隔壁的猴子同學(xué)家里的菜園圍的嚴(yán)嚴(yán)實實，一次也沒被野豬偷過。找他來幫幫忙不就可以完美解決了嗎？
想到這里我就以一顆長的最好看的大頭菜為報酬，請了隔壁的猴子同學(xué)來授之以漁。
猴子同學(xué)的思路講解
這個問題可以抽象為 凸包問題
在給定的點中，找出有限點構(gòu)造一個最小凸邊形，使其可以將給定的所有點都包含在內(nèi)
最關(guān)鍵的一點是把所有的菜【一下簡化為點】，都放在柵欄的內(nèi)側(cè)。所以可以從 判斷點是否在線段的某一邊 來下手。
判斷點是否在線段的某一邊
那么如何判斷呢？這里要引入一個數(shù)學(xué)概念，叉乘
由叉乘的定義可知，在三維坐標(biāo)系中。向量 a 叉乘 向量 b 可以得到一個垂直于 a b 向量組成平面的新向量 c，且它的模長等于向量 a b 形成的平行四邊形面積。且 c 根據(jù) a b 的方向不同，也會有自己的方向。這里可以根據(jù)右手定則來得知向量 c 的方向。
那么在這里，我們不需要用到全部 叉乘 的特點。由于我們凸包構(gòu)造的是二維坐標(biāo)系，那么擴展到三維的話 z 向量系數(shù)一定為 0。所以簡單來說二維平面上三點 A, B, C 構(gòu)造出的向量 ab 叉乘 ac 得出的向量必定是在 z 軸上的向量(0x, 0y, kz)。那么通過計算出單位向量 z 的系數(shù) k。 如果 k > 0 ，那么點 C 在向量 ab 的左邊。 k = 0， 點 C 在向量 ab 上。 k < 0，點 C 在向量 ab 右邊。
叉乘的計算可以寫為
所以如果在二維坐標(biāo)系中，就可以簡化為 U ?? V = (u1v2 - u2v1)k
這里把 u v 更換為 x y， 那么我們可以根據(jù) (x1y2 - x2y1) 的值是否大于等于 0 來進行判斷
然后以它為核心思想，從最基礎(chǔ)的窮舉方法來開始優(yōu)化
給定 n 個點，那么會有 n * (n - 1) / 2 條線，對每一條線進行計算，剩余的 (n - 2) 個點是否都位于這點線段的一側(cè)。如果是，那么這兩點為 凸點。
窮舉法復(fù)雜度為 O(n^3)
這里可以繼續(xù)對窮舉法進行優(yōu)化，首先取縱坐標(biāo)最小的一個點，如果有兩個就取其中一個，它肯定在凸包上。
然后以它為極坐標(biāo)中心，對剩下的所有點進行一個角度排序，排序結(jié)果如下圖。
然后就按順序依次對每一個點 開始依次嘗試剩下的
個點，找到第一個滿足條件的點【其他點都在
線段左側(cè)】。
這樣可以降低時間復(fù)雜度到 O(n^2)
到了這一步，想繼續(xù)優(yōu)化就得換一個思路，考慮是否可以不再對每一個點都進行嘗試。Graham 介紹
這里通過從最低點開始，然后分析凸包的特點找規(guī)律，距離它角度最小的第一個點肯定是凸包上的點【當(dāng)然角度最大的也是】，那么把 p0p1 入棧，接著考慮在線段 p1p2 是否是左轉(zhuǎn)【可以想象一個人先沿著 p0p1 走，到了 p1 的時候是需要向左轉(zhuǎn)還是向右轉(zhuǎn)】。如果是向左，那么這個點入棧，繼續(xù)下一個點。如果這個點向右，那么說明當(dāng)前棧頂不是凸包上的點，出棧。然后再次拿棧頂兩點來和當(dāng)前拿的點比較。這樣如此反復(fù)。
復(fù)雜度 O(n * log n)
最后附上 Graham 的簡單實現(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,
}
// 向量叉乘，這里簡化了 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 }
})
// 按照凸包的性質(zhì)，第一個點必定在凸包上
result.push(sortedPoint.shift())
sortedPoint.forEach((p, index) => {
while (crossProduct(result[result.length - 2], result[result.length - 1], p) < 0) {
// 在右方，說明棧頂不是凸包上的點
result.pop()
}
// 在一條線上的情況，多去一個點，屬于優(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}
*/
后記
通過猴子同學(xué)的一番講解操作，我成功的學(xué)會了如何圍柵欄，雖然在最后大頭菜經(jīng)濟泡沫了，但是萬萬沒想到，我在這次經(jīng)濟泡沫中大肆兜售的【我不可能能用這么少的錢圍起最好的柵欄】一書同樣讓我實現(xiàn)了財富自由。
-------------------
原文鏈接：[https://mp.weixin.qq.com/s/7Mek0vdv7r04zkj7oyISuw] (https://mp.weixin.qq.com/s/7Mek0vdv7r04zkj7oyISuw)
