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