寫在前面

嗨！很高興看到你點(diǎn)進(jìn)來閱讀這篇文章，請(qǐng)別介意，標(biāo)題有點(diǎn)長(zhǎng)有點(diǎn)啰嗦（完全是為了seo考慮），但也算是概括了這篇文章的內(nèi)容。如果你是要開發(fā)如下圖所示的場(chǎng)景，但又苦于沒什么好的思路，那么這篇文章一定會(huì)幫助到你！

往復(fù)式運(yùn)動(dòng)航線



基于不規(guī)則凸多邊形地塊的往復(fù)式航線規(guī)劃

哦，對(duì)了，本文的實(shí)現(xiàn)是基于web平臺(tái)的地圖，使用javascript。如果你也是在web平臺(tái)上開發(fā)，而且任務(wù)時(shí)間非常緊急，沒有時(shí)間閱讀完全文的話。。。我已經(jīng)將本文的思路封裝成一個(gè)庫了，你可以猛戳下面的鏈接，開箱即用：
github.com/Char-Ten/cp…
兼容各大地圖平臺(tái)api（其實(shí)不同平臺(tái)api差異的影響很低）哦，不信的話戳demo：
百度地圖demo
高德地圖demo
leaflet地圖demo
覺得好用的話記得給個(gè)star～原創(chuàng)不易，謝謝支持

正文！

其實(shí)也是套公式

其實(shí)這種問題，實(shí)際上是數(shù)學(xué)幾何應(yīng)用題，既然是數(shù)學(xué)題啦，那按照考試的套路第一步肯定是套公式啊，這種場(chǎng)景，核心的公式不多，就兩條：

• 
• 
  一次函數(shù)兩點(diǎn)表達(dá)式
•  
• 
• 
  繞（tx,ty）點(diǎn)旋轉(zhuǎn)n度之后縮放SxSy倍的變換矩陣

第一條沒什么可以說的，初二數(shù)學(xué)就開始教一次函數(shù)的知識(shí)，這一條是用來計(jì)算航線與地塊邊界的交點(diǎn)的。 第二條就是很經(jīng)典的復(fù)合變換矩陣了，分別是位移矩陣叉乘旋轉(zhuǎn)矩陣叉乘位移縮放矩陣，我們?cè)O(shè)其叉乘結(jié)果為A，那么我們就可以列出下面的等式：

計(jì)算過程就是。。。橫乘豎橫乘豎橫乘豎橫乘豎橫乘豎橫乘豎橫乘豎橫乘豎。。。。最后化為用于程序的代數(shù)式就是：

通過這條公式，就可以計(jì)算出航線旋轉(zhuǎn)后的坐標(biāo)點(diǎn)。

然后我們把它們分別封裝一下，弄成一個(gè)函數(shù)調(diào)用先：

看到這里，恭喜你，你已經(jīng)完成了50%的工作量！如果是在考試，你把這兩條公式列出來，不寫答案也有一半的分?jǐn)?shù)（

先從最簡(jiǎn)單的場(chǎng)景開始

一個(gè)矩形地塊，航線水平于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è)置無人機(jī)飛行的間隔為10。你先不考慮折線的連接順序，就單單考慮一下，每一根橫線如何生成。觀察一下你會(huì)發(fā)現(xiàn)以下規(guī)律：

1. 兩條橫線的間隔是20
2. 每一條橫線都可以表示為 y=N，N為常數(shù)，表示某個(gè)緯度值
3. 每一條橫線段都是y=N與矩形相交產(chǎn)生，也就是每一條橫線段都是該矩形地塊與維度相交的結(jié)果

那么，現(xiàn)在矩形的四個(gè)頂點(diǎn)的經(jīng)緯度是已知的，無人機(jī)飛行的間隔也是已知的，這個(gè)矩形需要與多少條緯度線相交是未知的，每一條橫線的N是未知的，每一條橫線段左右兩個(gè)點(diǎn)的緯度是未知的。根據(jù)已知求未知，你的目標(biāo)已經(jīng)很明確了，一道很簡(jiǎn)單的幾何題:

• 該矩形需要與多少條緯度線相交：

• 求每一條橫線的N:

• 因?yàn)榫匦蔚膬蓷l邊是垂直的，所以，橫線段左右兩個(gè)點(diǎn)的經(jīng)度分別為nw.lng，ne.lng。這樣我們就可以繪制出來了：

場(chǎng)景開始變形！

鏘鏘，我們把矩形上面的邊往東挪50米，得到一個(gè)平行四邊形：

聰明的你一定發(fā)現(xiàn)了，平行四邊形在Y軸上的投影根本沒有發(fā)生變化嘛，即使變了之后，穿過地塊的緯度線數(shù)目還是不變嘛，只不過，這次因?yàn)閮蓷l邊不是垂直的，所以，我們需要計(jì)算斜邊與緯度線的交點(diǎn)。等等，你這時(shí)候想起了，最開始50%工作量里面所封裝的那個(gè)calcPointInLineWithY函數(shù)！
你已經(jīng)知道斜邊兩個(gè)點(diǎn)的坐標(biāo)，然后你又知道y=N，那你通過一次函數(shù)的兩點(diǎn)表達(dá)式，完全就可以知道x，也就是經(jīng)度是多少啦：

那你可以再變一變，讓y軸上的投影也發(fā)生變化，就像這樣：

好了，這下你觀察到，每條邊都跟緯度線相交了，也就是說，這次你要遍歷一下這個(gè)平行四邊形四個(gè)頂點(diǎn)。等等，你似乎忘記了一個(gè)問題，這個(gè)四邊形在y軸上的投影發(fā)生了變化，相交緯度線數(shù)目也跟著發(fā)生變化了。這時(shí)候你想到，要不給這個(gè)多邊形做個(gè)外接矩形？就像這樣：

這樣是不是又回歸了最開始的場(chǎng)景？只是把calcPointInLineWithY函數(shù)加上去之后，你可以得到任意凸多邊形與緯度線相交的模型。