寫(xiě)在前面
嗨！很高興看到你點(diǎn)進(jìn)來(lái)閱讀這篇文章，請(qǐng)別介意，標(biāo)題有點(diǎn)長(zhǎng)有點(diǎn)啰嗦（完全是為了seo考慮），但也算是概括了這篇文章的內(nèi)容。如果你是要開(kāi)發(fā)如下圖所示的場(chǎng)景，但又苦于沒(méi)什么好的思路，那么這篇文章一定會(huì)幫助到你！
往復(fù)式運(yùn)動(dòng)航線(xiàn)
基于不規(guī)則凸多邊形地塊的往復(fù)式航線(xiàn)規(guī)劃
哦，對(duì)了，本文的實(shí)現(xiàn)是基于web平臺(tái)的地圖，使用javascript。如果你也是在web平臺(tái)上開(kāi)發(fā)，而且任務(wù)時(shí)間非常緊急，沒(méi)有時(shí)間閱讀完全文的話(huà)。。。我已經(jīng)將本文的思路封裝成一個(gè)庫(kù)了，你可以猛戳下面的鏈接，開(kāi)箱即用：
github.com/Char-Ten/cp…
兼容各大地圖平臺(tái)api（其實(shí)不同平臺(tái)api差異的影響很低）哦，不信的話(huà)戳demo：
百度地圖demo
高德地圖demo
leaflet地圖demo
覺(jué)得好用的話(huà)記得給個(gè)star～原創(chuàng)不易，謝謝支持
正文！
其實(shí)也是套公式
其實(shí)這種問(wèn)題，實(shí)際上是數(shù)學(xué)幾何應(yīng)用題，既然是數(shù)學(xué)題啦，那按照考試的套路第一步肯定是套公式啊，這種場(chǎng)景，核心的公式不多，就兩條：
一次函數(shù)兩點(diǎn)表達(dá)式
繞（tx,ty）點(diǎn)旋轉(zhuǎn)n度之后縮放SxSy倍的變換矩陣
第一條沒(méi)什么可以說(shuō)的，初二數(shù)學(xué)就開(kāi)始教一次函數(shù)的知識(shí)，這一條是用來(lái)計(jì)算航線(xiàn)與地塊邊界的交點(diǎn)的。 第二條就是很經(jīng)典的復(fù)合變換矩陣了，分別是位移矩陣叉乘旋轉(zhuǎn)矩陣叉乘位移縮放矩陣，我們?cè)O(shè)其叉乘結(jié)果為A，那么我們就可以列出下面的等式：
計(jì)算過(guò)程就是。。。橫乘豎橫乘豎橫乘豎橫乘豎橫乘豎橫乘豎橫乘豎橫乘豎。。。。最后化為用于程序的代數(shù)式就是：
通過(guò)這條公式，就可以計(jì)算出航線(xiàn)旋轉(zhuǎn)后的坐標(biāo)點(diǎn)。
然后我們把它們分別封裝一下，弄成一個(gè)函數(shù)調(diào)用先：
看到這里，恭喜你，你已經(jīng)完成了50%的工作量！如果是在考試，你把這兩條公式列出來(lái)，不寫(xiě)答案也有一半的分?jǐn)?shù)（
先從最簡(jiǎn)單的場(chǎng)景開(kāi)始
一個(gè)矩形地塊，航線(xiàn)水平于x軸:
這是一個(gè)大概是200*200大小的矩形，左上角的頂點(diǎn)經(jīng)緯度為
nw（西北），右上角的頂點(diǎn)經(jīng)緯度為ne（東北），右下角的頂點(diǎn)經(jīng)緯度為se（東南），左下角的頂點(diǎn)經(jīng)緯度為sw（西南），其中設(shè)置無(wú)人機(jī)飛行的間隔為10。你先不考慮折線(xiàn)的連接順序，就單單考慮一下，每一根橫線(xiàn)如何生成。觀(guān)察一下你會(huì)發(fā)現(xiàn)以下規(guī)律：
- 兩條橫線(xiàn)的間隔是20
- 每一條橫線(xiàn)都可以表示為
y=N，N為常數(shù)，表示某個(gè)緯度值 - 每一條橫線(xiàn)段都是
y=N與矩形相交產(chǎn)生，也就是每一條橫線(xiàn)段都是該矩形地塊與維度相交的結(jié)果
那么，現(xiàn)在矩形的四個(gè)頂點(diǎn)的經(jīng)緯度是已知的，無(wú)人機(jī)飛行的間隔也是已知的，這個(gè)矩形需要與多少條緯度線(xiàn)相交是未知的，每一條橫線(xiàn)的N是未知的，每一條橫線(xiàn)段左右兩個(gè)點(diǎn)的緯度是未知的。根據(jù)已知求未知，你的目標(biāo)已經(jīng)很明確了，一道很簡(jiǎn)單的幾何題:
- 該矩形需要與多少條緯度線(xiàn)相交：
- 求每一條橫線(xiàn)的
N:
- 因?yàn)榫匦蔚膬蓷l邊是垂直的，所以，橫線(xiàn)段左右兩個(gè)點(diǎn)的經(jīng)度分別為
nw.lng，ne.lng。這樣我們就可以繪制出來(lái)了：
場(chǎng)景開(kāi)始變形！
鏘鏘，我們把矩形上面的邊往東挪50米，得到一個(gè)平行四邊形：
聰明的你一定發(fā)現(xiàn)了，平行四邊形在Y軸上的投影根本沒(méi)有發(fā)生變化嘛，即使變了之后，穿過(guò)地塊的緯度線(xiàn)數(shù)目還是不變嘛，只不過(guò)，這次因?yàn)閮蓷l邊不是垂直的，所以，我們需要計(jì)算斜邊與緯度線(xiàn)的交點(diǎn)。等等，你這時(shí)候想起了，最開(kāi)始50%工作量里面所封裝的那個(gè)calcPointInLineWithY函數(shù)！
你已經(jīng)知道斜邊兩個(gè)點(diǎn)的坐標(biāo)，然后你又知道y=N，那你通過(guò)一次函數(shù)的兩點(diǎn)表達(dá)式，完全就可以知道x，也就是經(jīng)度是多少啦：
那你可以再變一變，讓y軸上的投影也發(fā)生變化，就像這樣：
好了，這下你觀(guān)察到，每條邊都跟緯度線(xiàn)相交了，也就是說(shuō)，這次你要遍歷一下這個(gè)平行四邊形四個(gè)頂點(diǎn)。等等，你似乎忘記了一個(gè)問(wèn)題，這個(gè)四邊形在y軸上的投影發(fā)生了變化，相交緯度線(xiàn)數(shù)目也跟著發(fā)生變化了。這時(shí)候你想到，要不給這個(gè)多邊形做個(gè)外接矩形？就像這樣：
這樣是不是又回歸了最開(kāi)始的場(chǎng)景？只是把calcPointInLineWithY函數(shù)加上去之后，你可以得到任意凸多邊形與緯度線(xiàn)相交的模型。
?