如何使用向量计算路径步骤

背景

类似于地图导航的应用场景，当在地图里面，知道了起点，知道了终点，那么必然有一条，最短（或者最合适）的路径，有了路径数据，就能在地图上绘制一根路线，当用户遵循这个路线走的过程，就会分解成多个步骤。本片文章旨在如何利用路线的数据，计算出步骤的数据。

问题

1.什么是路径？ 2.什么是步骤?

路径图.png

如图所示，以苏州站到苏州中心这段地图导航为例。
路径就是指截图中绿色的线条，拐点就是指路线变化方向时候的那个点，在这个截图里面，蓝色的点基本都是拐点（别杠，有几个确实不是）。
为了简化问题，先暂时不考虑曲线路径（要考虑也可以，把曲线理解成无数个拐点之间组成的折线，这样会产生很多相近数据，不便于分析），那么其实路径就是一个个拐点之间连接产生的折线。换句话说，有拐点就能画线。
步骤就是左侧截图框框的部分，可以看出几乎每次拐弯之前都被拆解成了一个步骤。

那么，我们就可以这么理解，一个导航的过程，就是由若干个步骤组合而成，同时这些步骤是跟路径和拐点息息相关的。所以在项目开发的时候，就会有如题的需求。

分析

既然如此，我们是知道路径的，即我们都知道所有的拐点，比方说为pointList,里面的元素均为CGPoint坐标，这个坐标是指拐点，在当前地图上的坐标，对于iOS而言，就理解为frame。
我们来看看每一条步骤，包含了哪些基本信息：
1.方向，这一步是直走还是左拐还是右拐 2.距离，这一步我要走多少。
至于走完了一步，是从哪条路到了哪条街，这个属于上层业务的范畴，不予讨论。

由易到难，距离很好算，既然知道了两个点，直接勾股定理直接能算出来，再根据你的地图比例尺，换算成实际长度单位。基本代码如下

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

看来主要问题是在第1个，如何去确定步骤的方向。这个时候就需要用到了高中数学学到的向量知识了。如果忘记了，还请自行百度。
其实每一个步骤，都可以抽象一个向量。从拐点中取出任意3点A,B,C,那么向量AB就是第一步，向量BC就是第二步。如下图所示，我们要求的就是如何描述，到达B点时，C距离B的方位。

向量.png

从图上就可以看出，只要将B往左偏移θ即可，那么如何动态的用代码计算呢？

1.角度大小

由图看出，θ就是向量AB和向量BC的夹角，那么可以根据向量数量积来计算出θ的余弦值以及大小。

公式.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点时有两种选择的，顺时针和逆时针方向旋转，所以必须要想办法确定旋转方向。

2.偏移方向

关于便宜方向的计算，也许有人会说，这个很简单啊，你看向量AB和X轴的夹角为α，θ已经算出来了，比较这两根大小，α < θ，逆时针反之则顺时针。非也非也！
首先第一步计算出向量余弦值，用反函数求出角度的时候，也有个问题，余弦函数是有周期的为2π，B点可选的角度范围也是0到2π，其实在这个范围内，取出的角度有可能是两个值。当然，在实际场景中，用户都回取最小的θ，为什么呢？因为能左转90°的事情办到的事情，没人愿意右转270°达到同一目标。
那么应该如何做处理呢？

顺逆时针.png

如图所示，我们把步骤1，也就是AB向量现在坐标轴中体现出来，虚线就是向量AB所在的直线，由图分析可知，从B 出发，到达在直线上方的点，逆时针旋转的角度最小；到达直线下方的点，顺时针旋转角度最小；
那么如何表示直线？这还不简单，一次函数 y=kx + b, b为0，斜率k = y1/x1 。但是并不是每次都是这样的，当前AB向量所在区域为第一象限，如果是在其他象限，结果会有不同。所以最终结果如下

最终结果.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的坐标系有区别
        return (!isClockWise, a)
    }

特别提醒
数学里面用的坐标系都是笛卡尔坐标系，坐标原点是在左下角，而iPhone手机屏幕的frame的坐标原点是在左上角，所以要在最后对结果做取反操作。
经过这样的计算，就能把每一步要走多少，往哪个方向拐多少角度都能够计算出来。

总结

数学真的很有用！最后，数学帝镇楼！

数学帝.png