In LBS development, you often encounter such a question: how do you determine if a given latitude and longitude point falls within a polygon region? For example, if a polygon region is drawn on a map and a latitude and longitude point is given, how can we determine whether the point is within the range of the polygon?

Recently I received a demand for the scene of clocking in:

  1. Users are not allowed to punch in while traveling
  2. Users are allowed to punch in only when they enter the time range

The first point is easy to solve: it is ok to prohibit the interaction of clocking when the user is on a business trip, while the second point may be a bit more complicated: how to determine the user’s attendance range? Expand similar needs and selling points to judge whether the business distribution range? Determine whether shared bikes are parked at parking spots?

These requirements are ultimately resolved in determining whether a coordinate point is within an irregular polygon.

Theoretical support

Method: Solve the number of intersection points between the horizontal ray passing through the point and each edge of the polygon. Results: If the intersection points between the horizontal ray and the polygon are odd, they are inside the polygon. If the intersection is even, it is on the outside of the polygon

Next up is the code. The first thing we need to do is to negotiate with the back end the rules of data transmission between APP and server: the server returns a string containing coordinates of pentagonal points, and these five points are connected in sequence to define an irregular pentagonal area, which is the effective range of our clocking time.

Coordinates of polygon points returned by server:

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

So let’s first process this string into five longitude and latitude Coordinate objects. The structure of Coordinate object is:

@interface Coordinate:NSObject
@property (nonatomic, assign) double lon;
@property (nonatomic, assign) double lat;
@end

@implementation Coordinate
@end
Copy the code

Note that when we’re working with strings, we’re converting Mars coordinates to baidu coordinates. (The coordinates returned by the service are Mars coordinates. After the positioning module in the project is in place, the longitude and latitude are directly converted into Baidu coordinates. Here, in order to keep the transformation consistent with the server coordinate system, you need to convert coordinates according to the actual situation of your project.)

Popularization and conversion of local map API coordinate system

  • WGS84 coordinate system: namely the earth coordinate system, the international universal coordinate system. The equipment generally includes GPS chip or Beidou chip, and the longitude and latitude obtained is WGS84 geographic coordinate system.
  • Google Maps uses the WGS84 geographic coordinate system (except for China);
  • GCJ02 coordinate system: Mars coordinate system is the coordinate system of geographic information system formulated by the State Bureau of Surveying and Mapping of China. The coordinate system encrypted by WGS84 coordinate system.
  • Google Map of China and Soso Map of China adopt GCJ02 geographical coordinate system; BD09 coordinate system: namely, baidu coordinate system and GCJ02 coordinate system after encryption;
  • Sogou coordinate system and toba coordinate system are estimated to be encrypted on the basis of GCJ02.

Process the data returned by the server and convert Mars coordinates to Baidu coordinates:

/ / handle returned by the server data - (void) dealWithDotCoordinateWithString: (locString nsstrings *) {/ / 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]; / / the server Mars Coordinate transformation for baidu coordinates Coordinate * baiduLoc = [self lonAndLatLocationBaiduFromMars: lonAndLat]; [locResult addObject:baiduLoc]; index ++; }}}Copy the code

Method of converting Martian coordinates to hundred coordinates:

/ / method of Coordinate transformation for baidu coordinates to Mars - (Coordinate *) lonAndLatLocationBaiduToMars: Coordinate *) Coordinate {double x_pi = 3000.0 / M_PI * 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;
}
Copy the code

Method of converting Baidu coordinates to Mars coordinates:

/ / baidu coordinates into Mars coordinates - (Coordinate *) lonAndLatLocationMarsToMars: Coordinate *) Coordinate {double x_pi = 3000.0 / M_PI * 180.0; Double x = coordinate. Lon-0.0065, y = coordinate. Double z = SQRT (x * x + y * y) -0.00002 * sin(y * x_pi); 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;

}

Copy the code

How to determine the coordinates inside the polygon

JudgeLocationX :(double)locationX locationY:(double)locationY insideSignArea:(NSArray *)areaArray{if(areaArray.count==0){
 NSLog(@"Return true if attendance area is empty");
        return true;
}

    NSMutableArray *xArray = [NSMutableArray new];
    NSMutableArray *yArray = [NSMutableArray new];
    
    for (Coordinate *coordinate inareaArray) { [xArray addObject: [NSNumber numberWithDouble:coordinate.lon]]; [yArray addObject:[NSNumber numberWithDouble:coordinate.lat]]; } BOOL flag = NO; // Select minX,maxX, minY,maxY from the four values minX,maxX, minY,maxY from the four values minX,maxX, minY,maxY from the four values minX,maxX, minY,maxY from the four values minX,maxX, minY,maxY from the four values minX,maxX, minY,maxY from the four values minX,maxX, minY,maxYfalseProve that the target point is not inside the polygon. 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; } // Draw a horizontal line to calculate the number of intersections with the polygon, odd inside the polygon, even outside the polygon. 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(@"Is the coordinate point in the irregular region: %d",success);
    return flag;
    
}
Copy the code

The method is to judge whether the latitude of the point is between two adjacent points of the polygon. If it is, then it is to judge whether there is an intersection between the single-direction horizontal ray of the point and the connecting edge of the two adjacent points. Start counting if there is an intersection. Then, the total number of points of intersection between the horizontal ray and the polygon edge can be obtained by traversing to determine whether there are any points of intersection with other sides of the polygon. If the total number of points of intersection is odd, the point is inside the polygon. An even number of intersections is on the outside of the polygon. The above method does not count the number of intersections, but directly uses flag to record the parity of the total number.

Finally, some simple data tests:

BOOL flag1 = [self judgeLocationX: locationY 116.3839694879:39.9274612554 insideSignArea: locResult]; / / should returntrueBOOL flag2 = [self judgeLocationX: locationY 116.4010873480:39.8485685476 insideSignArea: locResult]; / / should returntrueBOOL flag3 = [self judgeLocationX: locationY 116.5473037259:40.1688347176 insideSignArea: locResult]; / / should returnfalseBOOL flag4 = [self judgeLocationX: locationY 116.1909733537:40.0254447029 insideSignArea: locResult]; / / should returnfalse
Copy the code

conclusion

Think about what we just did:

  • Processing coordinate strings
  • Mars coordinates are converted to baidu coordinates
  • Determine if the point coordinates are inside the polygon
  • Simple authentication