Test if MKCircle intersects with MKPolygon

Question

I'm looking for some guidance in testing if a MKPolygon intersects an MKCircle. Currently I'm using:

if ([circle intersectsMapRect:[poly boundingMapRect]]) {
                    //they do intersect
   }

I'm finding this returns inaccurate results simply b/c it draws a rectangle around my circle, thus giving me intersections that shouldn't otherwise be.

Searching the topic has lead me to Chad Saxon's polygon-polygon intersection project. This could be useful if I could somehow convert my MKCircle to a multi-sided polygon - which could be possible but ultimately I believe this is the round-about way to solve this.

I'm ultimately wondering if there is a simple solution I've overlooked before delving into porting my own custom geometry-ray-testing-algorithm implementation.

Answer 1

A couple of thoughts:

1. If you use that polygon intersection project, be aware that it has a few leaks in it. I issued a pull request that fixes a few of them (and a few other random observations). I would be wary of adopting any of that view controller code (as it has other issues), too, but the category seems ok if you're ok with the various limitations it entails (notably, the clockwise limitation, which is not really an issue if you're only determining if they intersected).

2. Rather than converting the circle to a series of polygons and then using that polygon intersection class, I might consider an alternative approach leveraging that you can detect the intersection with a circle by leveraging the fact that you can look at the distance between the relevant points in the polygon and the radius of a circle. It seems that there are three aspects of the problem:

   • If the distance between any of the polygon's vertices and the center of the circle is less than the radius of the circle, then the polygon and circle intersect.

     

   • Does the polygon encompass the circle (this is that special case where the distance from all of the sides of the polygon would be greater than the circle's radius, but the circle and polygon still obviously intersect). This is easily achieved by checking to see if the CGPath of the polygon's view encompasses the center of the circle using CGPathContainsPoint.

     

   • The only complicated part is to check to see if any side of the polygon intersects the circle, namely that the minimum distance between the sides of the polygon and the center of the circle less than the radius of the circle;

     

   To calculate the distance of each side from the center of the circle, I might therefore iterate through each side of the polygon and for those sides facing the circle's center (i.e. for which the circle's center is perpendicular to the segment, meaning that an imaginary line perpendicular to the polygon's side that goes through the center of the circle actually crosses the line segment), you could:

   • Calculate the constants a, b, and c for this side of the polygon for the equation ax + by + c = 0 for a line segment going between vertices of the polygon (x₁, y₁) and (x₂, y₂):

   • a = (y₁ – y₂)

   • b = (x₂ – x₁)

   • c = (x₁y₂ – x₂y₁)

   • Calculate the distance from a point to a line, using (x₀, y₀) as the center of the circle:

     

   • If that distance is less than the radius of the circle, then you know that the polygon intersects the circle.

I put a sample project employing this technique on github.

Answer 2

Just for those to get a bit of substance on the solution, here is a useful MKCircle extension I wrote that checks if a point (in this case a polygon point) is inside the circle or not. Enjoy!

//MKCircle+PointInCircle.h

#import <Foundation/Foundation.h>
#import <MapKit/MapKit.h>

@interface MKCircle (PointInCircle)

-(BOOL)coordInCircle:(CLLocationCoordinate2D)coord;

@end

//MKCircle+PointInCircle.m

#import "MKCircle+PointInCircle.h"

@implementation MKCircle (PointInCircle)

-(BOOL)coordInCircle:(CLLocationCoordinate2D)coord {

    CLLocation *locFrom = [[CLLocation alloc] initWithLatitude:self.coordinate.latitude longitude:self.coordinate.longitude];
    CLLocation *locTo = [[CLLocation alloc] initWithLatitude:coord.latitude longitude:coord.longitude];

    double distance = [locFrom distanceFromLocation:locTo];
    BOOL isInside = (distance <= self.radius);

    return isInside;
}

@end