在 LBS 开发中,可能经常要碰到这样的问题,如何判断一个指定的经纬度点是否落在一个多边形区域内?比如在地图上画了一个多边形区域,然后给出一个经纬度点,怎样判断这个点是否在这个多边形范围之内?

image

需求描述

最近接到个考勤打卡场景需求:

  1. 用户在差旅状态下禁止打卡
  2. 用户进入考勤范围才允许打卡

第一点好解决:在用户差旅状态下禁止打卡交互就可以了,而第二点可能就有点复杂了: 如何来判断用户进入考勤范围内呢?拓展下类似的需求还有外卖点餐判断是否在商家配送范围?判断共享单车是否停靠在停车点?

这些需求拆分到最后都是 在判断一个坐标点是否在一个无规则的多边形内的问题

理论支持

需求: 判断某点坐标是否在多边形内
方法: 求解通过该点的水平射线与多边形各边的交点个数
结果: 水平射线与多边形交点为奇数,则在多边形内部;交点为偶数,则在多边形外部

代码实现

接下来就是上代码。我们首先要做的就是与后端商定 app 与服务器数据传输的规则:服务器传回包含五边形点坐标字符串,这五个点按顺序联结框定出一个不规则的五边形区域, 这个五边形区域就是我们的打卡考勤有效范围。

服务器传回的多边形各点坐标:

1
@"POLYGON((116.2310052844 39.9980477478,116.5143798001 40.0028565483,116.2460357549 39.8348654814,116.3976525318 39.7646827931,116.5157236632 39.8221811347))";

我们先把这个字符串处理成五个包含经度和纬度的 Coordinate 对象。Coordinate 对象的结构为:

1
2
3
4
5
6
7
@interface Coordinate:NSObject
@property (nonatomic, assign) double lon;
@property (nonatomic, assign) double lat;
@end
@implementation Coordinate
@end

坐标转换

需要注意的是,我们在处理字符串的时候,将火星坐标转化为百度坐标。(服务传回的坐标为火星坐标,项目中定位模块定到位后直接将经纬度转化为了百度坐标,这里是为了保持与服务器坐标系的一致进行转化,各位小伙伴需要根据自己项目实际情况进行坐标转换)

各地图API坐标系统科普与转换

  • WGS84坐标系:即地球坐标系,国际上通用的坐标系。设备一般包含GPS芯片或者北斗芯片获取的经纬度为WGS84地理坐标系,
    • 谷歌地图采用的是WGS84地理坐标系(中国范围除外);
    • GCJ02坐标系:即火星坐标系,是由中国国家测绘局制订的地理信息系统的坐标系统。由WGS84坐标系经加密后的坐标系。
  • 谷歌中国地图和搜搜中国地图采用的是GCJ02地理坐标系; BD09坐标系:即百度坐标系,GCJ02坐标系经加密后的坐标系;
  • 搜狗坐标系、图吧坐标系等,估计也是在GCJ02基础上加密而成的。

处理服务器返回的数据,并将火星坐标转化为百度坐标:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
//处理服务器返回的数据
- (void)dealWithDotCoordinateWithString:(NSString *)locString{
//locString = @"POLYGON((116.2310052844 39.9980477478,116.5143798001 40.0028565483,116.2460357549 39.8348654814,116.3976525318 39.7646827931,116.5157236632 39.8221811347))";
locString = [locString stringByReplacingOccurrencesOfString:@"POLYGON((" withString:@""];
locString = [locString stringByReplacingOccurrencesOfString:@"))" withString:@""];
NSArray *locArray = [locString componentsSeparatedByString:@","];
NSMutableArray *locResult = [NSMutableArray new];
NSInteger index = 0;
for (NSString * str in locArray) {
NSArray *strArray = [str componentsSeparatedByString:@" "];
if (strArray.count > 1) {
Coordinate *lonAndLat = [Coordinate new] ;
NSString *lon = [strArray objectAtIndex:0];
lonAndLat.lon = [lon doubleValue];
NSString *lat = [strArray objectAtIndex:1];
lonAndLat.lat = [lat doubleValue];
//将服务器的火星坐标转换为百度坐标
Coordinate *baiduLoc = [self lonAndLatLocationBaiduFromMars:lonAndLat];
[locResult addObject:baiduLoc];
index ++;
}
}
}

火星坐标转换为百度坐标的方法:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
//将火星坐标转换为百度坐标的方法
- (Coordinate *)lonAndLatLocationBaiduToMars:(Coordinate *)coordinate{
double x_pi = M_PI * 3000.0 / 180.0;
double x = coordinate.lon, y = coordinate.lat;
double z = sqrt(x * x + y * y) + 0.00002 * sin(y * x_pi);
double theta = atan2(y, x) + 0.000003 * cos(x * x_pi);
coordinate.lon = z * cos(theta) + 0.0065;
coordinate.lat = z * sin(theta) + 0.006;
return coordinate;
}

百度坐标转化为火星坐标方法:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
//百度坐标转化为火星坐标
- (Coordinate *) lonAndLatLocationMarsToMars:(Coordinate *)coordinate{
double x_pi = M_PI * 3000.0 / 180.0;
double x = coordinate.lon - 0.0065, y = coordinate.lat - 0.006;
double z = sqrt(x * x + y * y) - 0.00002 * sin(y * x_pi);
double theta = atan2(y, x) - 0.000003 * cos(x * x_pi);
coordinate.lon = z * cos(theta);
coordinate.lat = z * sin(theta);
return coordinate;
}

如何判断

接下来就是重点,怎么判断坐标在多边形内部方法:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
//判断点是否在多边形内部
- (BOOL)judgeLocationX:(double)locationX locationY:(double)locationY insideSignArea:(NSArray *)areaArray{
if(areaArray.count==0){
NSLog(@"考勤区域为空 直接返回 true");
return true;
}
NSMutableArray *xArray = [NSMutableArray new];
NSMutableArray *yArray = [NSMutableArray new];
for (Coordinate *coordinate in areaArray) {
[xArray addObject: [NSNumber numberWithDouble:coordinate.lon]];
[yArray addObject:[NSNumber numberWithDouble:coordinate.lat]];
}
BOOL flag = NO;
//取横坐标和纵坐标的最大值和最小值,根据这四个值minX,maxX,minY,maxY,算出一个四边形,判断目标点是否在这个四边形内,不满足,直接返回false,证明该目标点不在此多边形内部。
double minX = [[xArray valueForKeyPath:@"@min.doubleValue"] doubleValue];
double maxX = [[xArray valueForKeyPath:@"@max.doubleValue"] doubleValue];
double minY = [[yArray valueForKeyPath:@"@min.doubleValue"] doubleValue];
double maxY = [[yArray valueForKeyPath:@"@max.doubleValue"] doubleValue];
if (longitude < minX || longitude > maxX || latitude < minY || latitude > maxY ) {
return false;
}
//坐标点画条水平线射线计算与多边形的交点个数,奇数在多边形内, 偶数在多边形外。
int count = (int) areaArray.count ;
for (int i = 0, j = count-1; i < count; j = i++) {
if ( ( ([yArray[i] doubleValue] > locationY) != ([yArray[j] doubleValue] > locationY)) &&
(locationX < ([xArray[j] doubleValue] - [xArray[i] doubleValue]) * (locationY-[yArray[i] doubleValue]) / ([yArray[j] doubleValue]-[yArray[i] doubleValue]) + [xArray[i] doubleValue]) )
flag = !flag;
}
NSLog(@"坐标点是否在不规则区域内: %d",success);
return flag;
}

方法内部对坐标点进行判断,判断该点纬度是否在多边形相邻两点纬度之间,如果在两纬度之间则接着判断该点单方向的水平射线与这两相邻点连结边是否有交点。如果有交点则开始计数。接着遍历判断与多边形其它边是否有交点,这样就可以得到该水平射线与多边形边交点的总个数,交点总数为奇数则该点在多边形内部;交点总数为偶数则该点在多边形外部。上面方法中并没有统计交点个数而是直接使用 flag 记录总数的奇偶性。

验证

最后进行一些简单的数据测试:

1
2
3
4
BOOL flag1 = [self judgeLocationX:116.3839694879 locationY:39.9274612554 insideSignArea:locResult]; //应返回 true
BOOL flag2 = [self judgeLocationX:116.4010873480 locationY:39.8485685476 insideSignArea:locResult]; //应返回 true
BOOL flag3 = [self judgeLocationX:116.5473037259 locationY:40.1688347176 insideSignArea:locResult]; //应返回 false
BOOL flag4 = [self judgeLocationX:116.1909733537 locationY:40.0254447029 insideSignArea:locResult]; //应返回 false

总结

回想下我们刚才都做了些什么:

  • 处理坐标字符串
  • 火星坐标转化为百度坐标
  • 判断点坐标是否在多边形内部
  • 简单验证