如何使用向量計算路徑步驟

背景

類似于地圖導航的應用場景碟狞，當在地圖里面，知道了起點婚陪，知道了終點族沃，那么必然有一條，最短（或者最合適）的路徑泌参，有了路徑數(shù)據(jù)脆淹，就能在地圖上繪制一根路線，當用戶遵循這個路線走的過程沽一，就會分解成多個步驟盖溺。本片文章旨在如何利用路線的數(shù)據(jù)，計算出步驟的數(shù)據(jù)铣缠。

問題

1.什么是路徑咐柜？ 2.什么是步驟?

路徑圖.png

如圖所示，以蘇州站到蘇州中心這段地圖導航為例攘残。
路徑就是指截圖中綠色的線條拙友，拐點就是指路線變化方向時候的那個點，在這個截圖里面歼郭，藍色的點基本都是拐點（別杠遗契，有幾個確實不是）。
為了簡化問題病曾，先暫時不考慮曲線路徑（要考慮也可以牍蜂，把曲線理解成無數(shù)個拐點之間組成的折線，這樣會產(chǎn)生很多相近數(shù)據(jù)泰涂，不便于分析）鲫竞，那么其實路徑就是一個個拐點之間連接產(chǎn)生的折線。換句話說逼蒙，有拐點就能畫線从绘。
步驟就是左側截圖框框的部分，可以看出幾乎每次拐彎之前都被拆解成了一個步驟是牢。

那么僵井，我們就可以這么理解，一個導航的過程驳棱，就是由若干個步驟組合而成批什，同時這些步驟是跟路徑和拐點息息相關的。所以在項目開發(fā)的時候社搅，就會有如題的需求驻债。

分析

既然如此乳规，我們是知道路徑的，即我們都知道所有的拐點合呐，比方說為pointList,里面的元素均為CGPoint坐標驯妄，這個坐標是指拐點，在當前地圖上的坐標合砂，對于iOS而言青扔，就理解為frame。
我們來看看每一條步驟翩伪，包含了哪些基本信息：
1.方向微猖，這一步是直走還是左拐還是右拐 2.距離，這一步我要走多少缘屹。
至于走完了一步凛剥，是從哪條路到了哪條街，這個屬于上層業(yè)務的范疇轻姿，不予討論犁珠。

由易到難，距離很好算互亮，既然知道了兩個點犁享，直接勾股定理直接能算出來，再根據(jù)你的地圖比例尺豹休，換算成實際長度單位炊昆。基本代碼如下

let distance = sqrt(pow(point.x - previousPonit.x, 2) + pow(point.y - previousPonit.y, 2))

看來主要問題是在第1個威根，如何去確定步驟的方向凤巨。這個時候就需要用到了高中數(shù)學學到的向量知識了。如果忘記了洛搀，還請自行百度敢茁。
其實每一個步驟，都可以抽象一個向量留美。從拐點中取出任意3點A,B,C,那么向量AB就是第一步彰檬，向量BC就是第二步。如下圖所示独榴，我們要求的就是如何描述僧叉，到達B點時奕枝，C距離B的方位棺榔。

向量.png

從圖上就可以看出，只要將B往左偏移θ即可隘道，那么如何動態(tài)的用代碼計算呢症歇？

1.角度大小

由圖看出郎笆，θ就是向量AB和向量BC的夾角，那么可以根據(jù)向量數(shù)量積來計算出θ的余弦值以及大小忘晤。

公式.png

let ab = CGPoint(x: secondPoint.x - firstPoint.x, y: secondPoint.y - firstPoint.y)
let bc = CGPoint(x: thirdPoint.x - secondPoint.x, y: thirdPoint.y - secondPoint.y)
let cosA = (ab.x * bc.y + bc.x * ab.y) / ( sqrt(pow(ab.x, 2) + pow(ab.y, 2)) + sqrt(pow(bc.x, 2) + pow(bc.y, 2)) )
let A = acos(Double(cosA))

有人可能會注意到宛蚓，我圖里有兩個C，一個是C1另個C2设塔，因為光知道一個角度的大小凄吏，站在B點時有兩種選擇的，順時針和逆時針方向旋轉(zhuǎn)闰蛔，所以必須要想辦法確定旋轉(zhuǎn)方向痕钢。

2.偏移方向

關于便宜方向的計算，也許有人會說序六，這個很簡單啊任连，你看向量AB和X軸的夾角為α，θ已經(jīng)算出來了例诀，比較這兩根大小随抠，α < θ，逆時針反之則順時針繁涂。非也非也拱她！
首先第一步計算出向量余弦值，用反函數(shù)求出角度的時候扔罪，也有個問題椭懊，余弦函數(shù)是有周期的為2π，B點可選的角度范圍也是0到2π步势，其實在這個范圍內(nèi)氧猬，取出的角度有可能是兩個值。當然坏瘩，在實際場景中盅抚，用戶都回取最小的θ，為什么呢倔矾？因為能左轉(zhuǎn)90°的事情辦到的事情妄均，沒人愿意右轉(zhuǎn)270°達到同一目標。
那么應該如何做處理呢哪自？

順逆時針.png

如圖所示丰包，我們把步驟1，也就是AB向量現(xiàn)在坐標軸中體現(xiàn)出來壤巷，虛線就是向量AB所在的直線邑彪，由圖分析可知，從B 出發(fā)胧华，到達在直線上方的點寄症，逆時針旋轉(zhuǎn)的角度最兄姹搿；到達直線下方的點有巧，順時針旋轉(zhuǎn)角度最惺推帷；
那么如何表示直線篮迎？這還不簡單男图，一次函數(shù) y=kx + b, b為0，斜率k = y1/x1 甜橱。但是并不是每次都是這樣的享言，當前AB向量所在區(qū)域為第一象限，如果是在其他象限渗鬼，結果會有不同览露。所以最終結果如下

最終結果.png

第一四象限情況相同，第二三象限情況相同譬胎。那么問題就迎刃而解了差牛。但是還要考慮一些特殊情況，那就是水平和豎直的時候堰乔，是沒有斜率的偏化，要特殊處理一下。

func caculateDetial(firstPoint: CGPoint, secondPoint: CGPoint, thirdPoint: CGPoint) -> (Bool, Double) {
        
        let ab = CGPoint(x: secondPoint.x - firstPoint.x, y: secondPoint.y - firstPoint.y)
        let bc = CGPoint(x: thirdPoint.x - secondPoint.x, y: thirdPoint.y - secondPoint.y)
        let cosA = (ab.x * bc.y + bc.x * ab.y) / ( sqrt(pow(ab.x, 2) + pow(ab.y, 2)) + sqrt(pow(bc.x, 2) + pow(bc.y, 2)) )
        let a = acos(Double(cosA))
        var isClockWise = false
        if ab.y == 0 {
            // horizontal
            if ab.x > 0 {
                isClockWise = bc.y < 0
            } else if ab.x < 0 {
                isClockWise = bc.y > 0
            }
        } else if ab.x == 0 {
            // vertical
            if ab.y > 0 {
                isClockWise = bc.x > 0
            } else if ab.y < 0 {
                isClockWise = bc.x < 0
            }
        } else {
            // general
            let k = CGFloat(ab.y / ab.x)
            if ab.x > 0 {
                // first fourth qudrant
                if bc.y < k * bc.x {
                    isClockWise = true
                } else if bc.y > k * bc.x {
                    isClockWise = false
                }
            } else if ab.x < 0 {
                // second third qudrant
                if bc.y < k * bc.x {
                    isClockWise = false
                } else if bc.y > k * bc.x {
                    isClockWise = true
                }
            }
        }
        // 要取反镐侯，笛卡爾坐標系和frame的坐標系有區(qū)別
        return (!isClockWise, a)
    }

特別提醒
數(shù)學里面用的坐標系都是笛卡爾坐標系侦讨，坐標原點是在左下角，而iPhone手機屏幕的frame的坐標原點是在左上角苟翻，所以要在最后對結果做取反操作韵卤。
經(jīng)過這樣的計算，就能把每一步要走多少崇猫，往哪個方向拐多少角度都能夠計算出來沈条。

總結

數(shù)學真的很有用！最后诅炉，數(shù)學帝鎮(zhèn)樓蜡歹！

數(shù)學帝.png