無(wú)人機(jī)航線規(guī)劃思路剖析，基于凸多邊形地塊往復(fù)式運(yùn)動(dòng)

• 首先是創(chuàng)建多邊形外接的矩形，將多邊形頂點(diǎn)全部遍歷一遍，取到最大和最小的經(jīng)緯度值。經(jīng)度最大為東，經(jīng)度最小為西。緯度最大為北，緯度最小為南。將這幾個(gè)組合一下，獲得西北點(diǎn)，東北點(diǎn)，東南點(diǎn)和西南點(diǎn)，就可以弄出一個(gè)矩形出來(lái)

• 然后是計(jì)算這個(gè)外接矩形穿過(guò)了多少條緯度線，跟之前那個(gè)場(chǎng)景是一樣的。rect是上面那個(gè)函數(shù)創(chuàng)建的數(shù)組，可以看到西北點(diǎn)的索引是0，西南點(diǎn)的索引是3，所以計(jì)算西北到西南的點(diǎn)，也就是這個(gè)外接矩形的高度。這個(gè)方法返回有l(wèi)en條緯度線穿過(guò)，而且穿過(guò)的緯度相差lat。

• 最后就是結(jié)合上面幾個(gè)場(chǎng)景，改寫一下最終的生成函數(shù)，這里你是直接將生成的橫線畫了出來(lái)，如果需要做折線連接順序處理，還需要聲明一個(gè)數(shù)組去存儲(chǔ)生成的點(diǎn)，比如當(dāng)緯度線的索引是奇數(shù)時(shí)，橫線從西往東畫，也就是先放西邊的點(diǎn)再放東邊的點(diǎn)；如果緯度線索引是偶數(shù)時(shí)，橫線從東往西畫，也就是反過(guò)來(lái)。這里就留給你自己處理了

到這里，基本上已經(jīng)完成了90%，剩下10%那部分最簡(jiǎn)單了。簡(jiǎn)單么？你歪著頭問(wèn)，到現(xiàn)在為止只是多邊形與緯度線相交啊，現(xiàn)實(shí)中無(wú)人機(jī)又不可能都是沿著緯度在地圖上橫著飛！它可以在地圖上沿任意方向飛行的，可上面的做法，只能讓無(wú)人機(jī)橫著走?。?br /> 別急，你這時(shí)候要淡定，你要想想開頭不是還留了一個(gè)transform函數(shù)么？
這個(gè)transform的作用是讓坐標(biāo)(x,y)繞著(tx,ty)旋轉(zhuǎn)deg度后在縮放SySx倍得到一個(gè)的新坐標(biāo)(_x,_y)。沒錯(cuò)，這次我們要拿這些坐標(biāo)進(jìn)行旋轉(zhuǎn)運(yùn)動(dòng)。
而且牛頓告訴過(guò)你：

運(yùn)動(dòng)都是相對(duì)的

先放一張gif圖，看看如何繪制一個(gè)斜45度角的航線：

先讓多邊形繞著中心點(diǎn)旋轉(zhuǎn)想要的角度，將得到的新多邊形再與緯度線做相交操作，獲取到那些交點(diǎn)之后，再將那些交點(diǎn)旋轉(zhuǎn)回來(lái)。換句話說(shuō)，變換前它是一個(gè)任意多邊形，變換后，它還是一個(gè)任意多邊形，都是滿足上面已經(jīng)預(yù)設(shè)好的場(chǎng)景的。這樣的好處顯而易見，你不需要修改上面的任何一個(gè)函數(shù)，也不需要去多寫一條兩個(gè)一次函數(shù)求交點(diǎn)的公式。把問(wèn)題化到最簡(jiǎn)單的場(chǎng)景去，只需要添加變換的代碼：

這里你一定要牢記，lng是經(jīng)度，對(duì)應(yīng)x；lat是緯度，對(duì)應(yīng)y（被leaflet框架坑哭的我QuQ。。。 然后，將原來(lái)的代碼加上去

小瑕疵

也許細(xì)心的你發(fā)現(xiàn)了，gif圖里面轉(zhuǎn)是轉(zhuǎn)了，斜45度的角也是畫出來(lái)了，但是旋轉(zhuǎn)后的圖形好像是被拉長(zhǎng)了！旋轉(zhuǎn)回來(lái)時(shí)又會(huì)被壓肥回來(lái)。這個(gè)嘛。。。
這個(gè)問(wèn)題其實(shí)我在寫驗(yàn)證的時(shí)候也發(fā)現(xiàn)了，粗略計(jì)算多邊形面積和航線掃過(guò)的面積的比值，總是發(fā)現(xiàn)0度的比值最接近于1，90度的比值最小，不管多邊形是什么形狀。
最開始我一直以為是面積算法的原因，直到寫這篇文章的時(shí)候去寫那個(gè)gif動(dòng)畫后才發(fā)現(xiàn)，多邊形變換后變形了，轉(zhuǎn)換后與緯度相交的數(shù)量變多了。而我猜想變形的原因可能是，地球并不是一個(gè)平面，它是彎的你知道吧，這些經(jīng)緯度雖然是投影到了平面上了，但實(shí)際上它們是在一個(gè)球上。直接拿經(jīng)緯度變換相當(dāng)于先在球上做了旋轉(zhuǎn)，然后在投影到地圖的平面上，這樣看起來(lái)就像是被拉長(zhǎng)了。
所以，你不能直接變換經(jīng)緯度，而是要將經(jīng)緯度換算成地圖上的像素坐標(biāo)，變換完之后再轉(zhuǎn)回來(lái)，這樣圖像就不會(huì)被拉長(zhǎng)了。
因此先來(lái)兩個(gè)像素系與經(jīng)緯度坐標(biāo)系轉(zhuǎn)換的方法壓壓驚：

然后將原來(lái)的createRotatePolygon函數(shù)改為

這樣就解決了拉長(zhǎng)的問(wèn)題：

寫在最后

終于寫完了此文，真是不容易。這個(gè)思路，從最開始思想混亂與Leaflet框架緊密耦合，到一步步解耦，到自己決定寫一個(gè)適用于各個(gè)地圖平臺(tái)的庫(kù)，到寫這篇文章，差不多已經(jīng)過(guò)去兩個(gè)星期了。我發(fā)現(xiàn)，很多問(wèn)題是你調(diào)試過(guò)程中發(fā)現(xiàn)不了的，等到你調(diào)試好了，決定寫一篇裝逼的文章，在寫的過(guò)程中你就會(huì)發(fā)現(xiàn)各種調(diào)試中出現(xiàn)不了的問(wèn)題，比如那個(gè)變換變形的問(wèn)題。

在動(dòng)手前，關(guān)于此類的教程文章少之又少，唯一可以找到比較符合場(chǎng)景的竟然是百度文庫(kù)里面的一篇論文:
基于作業(yè)航向的不規(guī)則區(qū)域作業(yè)航線規(guī)劃算法研究
論文懂吧，長(zhǎng)倒是不長(zhǎng)，就是臭，里面堆砌著各種奇奇怪怪的術(shù)語(yǔ)。之后看了兩天后才明白他的實(shí)現(xiàn)思路，大同小異，只不過(guò)不知道他怎么搞的，新弄出一個(gè)坐標(biāo)系出來(lái)，感覺這樣是增加了思路的復(fù)雜度啊。所以在他的算法的基礎(chǔ)上我做了簡(jiǎn)化，不做坐標(biāo)系偏移，取代的是變換地塊坐標(biāo)，這樣實(shí)現(xiàn)起來(lái)相對(duì)簡(jiǎn)單些。

因此在這里，小小貢獻(xiàn)一下這個(gè)思路吧，也讓以后有人像我這樣被坑去寫這種無(wú)人機(jī)航線規(guī)劃的，能夠很快地實(shí)現(xiàn)，不用再去看那些奇奇怪怪的論文了。。。

最后最后最后，安利一下github.com/Char-Ten/cp… 這個(gè)庫(kù)（已經(jīng)無(wú)恥到這個(gè)地步了。。。），可以接入百度、高德、leaflet，然后算航線！什么？你不需要。。。那你需要計(jì)算地圖上多邊形地塊的面積不？我也提供算面積的方法，百度地圖、高德地圖都沒有這種算面積的方法！好評(píng)給個(gè)star！謝謝大家！（夠了喂！(╯‵□′)╯︵┻━┻）
如果你有更好的實(shí)現(xiàn)思路，或者新的使用場(chǎng)景，或者有使用問(wèn)題，或者有bug，歡迎在下面評(píng)論。。?；蛘咧苯犹醝ssue: github.com/Char-Ten/cp…