Skip to content

Instantly share code, notes, and snippets.

@Goos
Last active January 22, 2017 22:25
Show Gist options
  • Save Goos/5e73623a5d029c0aae82 to your computer and use it in GitHub Desktop.
Save Goos/5e73623a5d029c0aae82 to your computer and use it in GitHub Desktop.
A category for checking whether or not an MKPolygon contains a point or coordinate.
//
// MKPolygon+Containment.h
// Pods
//
// Created by Robin Goos on 28/04/15.
//
//
#import <MapKit/MapKit.h>
@interface MKPolygon (Containment)
- (BOOL)containsPoint:(MKMapPoint)point;
- (BOOL)containsCoordinate:(CLLocationCoordinate2D)coordinate;
@end
//
// MKPolygon+Containment.m
// Pods
//
// Created by Robin Goos on 28/04/15.
//
// Courtesy of 'Mecki' on StackOverflow:
// http://stackoverflow.com/questions/217578/point-in-polygon-aka-hit-test#218081
#import "MKPolygon+Containment.h"
typedef struct {
MKMapPoint p1;
MKMapPoint p2;
} MKMapLine;
BOOL MKMapLineIntersectsLine(MKMapLine l1, MKMapLine l2) {
double d1, d2;
double a1, a2, b1, b2, c1, c2;
/* Convert line 1 to a line (line 1) of infinite length.
We want the line in linear equation standard form: A*x + B*y + C = 0
See: http://en.wikipedia.org/wiki/Linear_equation */
a1 = l1.p2.y - l1.p1.y;
b1 = l1.p1.x - l1.p2.x;
c1 = (l1.p2.x * l1.p1.y) - (l1.p1.x * l1.p2.y);
/* Every point (x,y), that solves the equation above, is on the line,
every point that does not solve it, is either above or below the line.
We insert (x1,y1) and (x2,y2) of line 2 into the equation above. */
d1 = (a1 * l2.p1.x) + (b1 * l2.p1.y) + c1;
d2 = (a1 * l2.p2.x) + (b1 * l2.p2.y) + c1;
/* If d1 and d2 both have the same sign, they are both on the same side of
our line 1 and in that case no intersection is possible. 0 is a special
case, which is why we don't test >= and <=, but < and >. */
if (d1 > 0 && d2 > 0) return NO;
if (d1 < 0 && d2 < 0) return NO;
/* We repeat everything above for line 2.
We start by calculating line 2 in linear equation standard form. */
a2 = l2.p2.y - l2.p1.y;
b2 = l2.p1.x - l2.p2.x;
c2 = (l2.p2.x * l2.p1.y) - (l2.p1.x * l2.p2.y);
// Calulate d1 and d2 again, this time using points of line 1
d1 = (a2 * l1.p1.x) + (b2 * l1.p1.y) + c2;
d2 = (a2 * l1.p2.x) + (b2 * l1.p2.y) + c2;
/* Again, if both have the same sign (and neither one is 0),
no intersection is possible. */
if (d1 > 0 && d2 > 0) return NO;
if (d1 < 0 && d2 < 0) return NO;
/* If we get here, only three possibilities are left. Either the two
lines intersect in exactly one point or they are collinear
(they both lie both on the same infinite line), in which case they
may intersect in an infinite number of points or not at all. */
if ((a1 * b2) - (a2 * b1) == 0.0f) return NO;
// If they are not collinear, they must intersect in exactly one point.
return YES;
};
@implementation MKPolygon (Containment)
- (BOOL)containsPoint:(MKMapPoint)point
{
NSUInteger pointCount = self.pointCount;
MKMapPoint *points = self.points;
// Getting the bounding box in order to determine a point outside the polygon.
MKMapRect boundingRect = self.boundingMapRect;
// Defining an epsilon based on the size of the polygon.
double e = (MKMapRectGetMaxX(boundingRect) - MKMapRectGetMinX(boundingRect)) / 100.0;
// Putting the starting point of the line just outside the polygon's bounds.
double startX = MKMapRectGetMinX(boundingRect) - e;
double startY = point.y;
MKMapPoint startPoint = MKMapPointMake(startX, startY);
/* Creating a line between the point outside and the target point,
which is going to be the 'ray' we're casting to determine the
amount of intersections. */
MKMapLine ray = (MKMapLine){ .p1 = startPoint, .p2 = point };
// Creating a line for every point inside the polygon.
MKMapLine lines[pointCount];
for (NSUInteger i = 0; i < pointCount; i++) {
MKMapPoint start = points[i];
/* If it's the last point, create a line between it and the first one,
instead of the next one. */
MKMapPoint end = (i == (pointCount - 1)) ? points[0] : points[i + 1];
MKMapLine line = (MKMapLine){ .p1 = start, .p2 = end };
lines[i] = line;
}
// Testing the ray for intersections with all the lines (sides) of the polygon.
NSUInteger intersections = 0;
for (NSUInteger i = 0; i < pointCount; i++) {
MKMapLine line = lines[i];
if (MKMapLineIntersectsLine(ray, line)) {
intersections++;
}
}
// A non-zero uneven amount of intersections means the point is inside the polygon.
return (intersections & 1) == 1;
}
- (BOOL)containsCoordinate:(CLLocationCoordinate2D)coordinate
{
MKMapPoint point = MKMapPointForCoordinate(coordinate);
return [self containsPoint:point];
}
@end
@raphaelschaad
Copy link

Have you looked into letting CGPathContainsPoint do the "heavy math"?

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment