序言
整理下电子围栏的算法.
先看下经纬度的含义(^_^),与地球的关联.这个会在算法中有影响,你在考虑算法的过程中应该会联想到相关的问题.cuiyaonan2000@163.com
- 经线(英文:longitude,简写long): 连接南北极的圆
- 纬线(英文:latitude,简写lat): 以赤道为中心的圆
另外关于地理坐标的值(算法会考虑这些):
- 经度：东经为正数，西经为负数。
- 纬度：北纬为正数，南纬为负数。
规则的多边形
这种的处理比较简单具体思路如下.
在坐标系中需要计算在规则多边形中T点是是否在范围内只需要满足如下的2点需求(这里算法需要考虑坐标横跨北纬南纬以及东经西经的问题cuiyaonan2000@163.com):
- C-lat <= T-lat <= B-lat
- C-Long <= T-Long <= B-Long
如上的是以BC为对角线的判断,当然我们可以同时增加AD的对角线的判断,来使结果更加正确.
规则的圆形
圆形电子围栏的实现有种简单的方式,就是根据半径来计算目标点与中心原点的直径是否超过了它的半径.这里介绍的是稍微复杂的一种算法.
算法太复杂研究中
不规则的区域
不规则计算规则也是比较简单的.
如下图所示:红色的点是目标点. 以红色的点为中心点画一条垂直于Longitude的线.
如果该红色的点左右两侧的交点数量是奇数,则表示该红色的点在电子围栏之内.
如果该红色的点左右两侧的交点数量是偶数,则表示该红色的点不在电子围栏之内.
其实如上的规则利用了现实的情况,我们的电子围栏边界都是直线,且都是一个封闭的区域.必然会产生奇数或者偶数的交点cuiyaonan2000@163.com
交点的生成规则
结合上图所示.我们需要知道 交点只能跟一条边线产生.
如下图所示最右边有一个交点 正好在A边线和B边线的合并处.
该交点属于B边线,因为(同时也是交点产生的必要条件cuiyaonan2000@163.com):
- 边线必须有一端在交点的上方,可以覆盖
- 边线必须有一端在交点的下方,不可以覆盖,即交点不能跟边线低点重合
更复杂的一个情况
可以看到如下图所示: 横线直接与B边线重合
但是这里只有C边线有交点,因为只有C边线满足如上的规则,
因为:有一点在水平线上有一点在点在水平线下.
