序言

整理下电子围栏的算法.

先看下经纬度的含义(^_^),与地球的关联.这个会在算法中有影响,你在考虑算法的过程中应该会联想到相关的问题.cuiyaonan2000@163.com

经线(英文:longitude,简写long): 连接南北极的圆纬线(英文:latitude,简写lat): 以赤道为中心的圆

另外关于地理坐标的值(算法会考虑这些):

经度：东经为正数，西经为负数。纬度：北纬为正数，南纬为负数。

规则的多边形

这种的处理比较简单具体思路如下.

在坐标系中需要计算在规则多边形中T点是是否在范围内只需要满足如下的2点需求(这里算法需要考虑坐标横跨北纬南纬以及东经西经的问题cuiyaonan2000@163.com):

C-lat <= T-lat <= B-latC-Long <= T-Long <= B-Long

如上的是以BC为对角线的判断,当然我们可以同时增加AD的对角线的判断,来使结果更加正确.

规则的圆形

圆形电子围栏的实现有种简单的方式,就是根据半径来计算目标点与中心原点的直径是否超过了它的半径.这里介绍的是稍微复杂的一种算法.

算法太复杂研究中

不规则的区域

不规则计算规则也是比较简单的.

如下图所示:红色的点是目标点. 以红色的点为中心点画一条垂直于Longitude的线.

如果该红色的点左右两侧的交点数量是奇数,则表示该红色的点在电子围栏之内.

如果该红色的点左右两侧的交点数量是偶数,则表示该红色的点不在电子围栏之内.

其实如上的规则利用了现实的情况,我们的电子围栏边界都是直线,且都是一个封闭的区域.必然会产生奇数或者偶数的交点cuiyaonan2000@163.com

交点的生成规则

结合上图所示.我们需要知道 交点只能跟一条边线产生.

如下图所示最右边有一个交点 正好在A边线和B边线的合并处.

该交点属于B边线,因为(同时也是交点产生的必要条件cuiyaonan2000@163.com):

边线必须有一端在交点的上方,可以覆盖边线必须有一端在交点的下方,不可以覆盖,即交点不能跟边线低点重合

更复杂的一个情况

可以看到如下图所示: 横线直接与B边线重合

但是这里只有C边线有交点,因为只有C边线满足如上的规则,

因为:有一点在水平线上有一点在点在水平线下.