测试MKCircle是否与MKPolygon相交

Question

我正在寻求一些关于如何测试MKPolygon和MKCircle是否相交的指导。目前我正在使用：

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

我发现这个方法返回的结果不准确，因为它在我的圆周围画了一个矩形，从而给出了本不应该有的交点。

搜索这个主题引导我找到了Chad Saxon's polygon-polygon intersection project。如果我能将MKCircle转换为多边形，这可能会很有用，但最终我认为这是解决问题的迂回之路。

我最终想知道是否有简单的解决方案被我忽略了，然后再深入探究我的自定义几何光线测试算法实现的移植。

- capikaw

Answer 1

一些想法：

1. 如果您使用该多边形交集项目，请注意它有一些漏洞。我发出了一个拉取请求，修复了其中的一些问题（以及其他一些随机观察）。如果您只想确定它们是否相交，则应该谨慎采用任何那个视图控制器代码（因为它还有其他问题），但是如果您可以接受各种限制（特别是顺时针限制），则该类别似乎没问题。
2. 与其将圆转换为一系列多边形，然后使用该多边形交集类，不如考虑一种替代方法，利用您可以通过查看多边形中相关点与圆的半径之间的距离来检测与圆的交点的事实。似乎问题有三个方面：
• 如果多边形的任何顶点与圆心之间的距离小于圆的半径，则多边形和圆相交。
• 多边形是否包含圆（这是特殊情况，即多边形的所有侧的距离都大于圆的半径，但圆和多边形明显相交）。这可以通过使用CGPathContainsPoint检查多边形视图的CGPath是否包含圆的中心来轻松实现。
• 唯一复杂的部分是检查多边形的任何一侧是否与圆相交，即多边形的边缘与圆心之间的最小距离小于圆的半径；

为了计算每个边缘与圆心之间的距离，因此我可能会遍历多边形的每个边缘，并针对面向圆心的那些边缘（即对于其中圆心垂直于线段的多边形边缘，意味着通过圆形中心的垂直于多边形边缘的虚拟线实际上穿过了线段），您可以：

• 计算该多边形边缘的常量a、b和c，用于方程ax + by + c = 0，表示连接多边形顶点（x₁, y₁）和（x₂，y₂）的线段：
• a = (y₁ – y₂)
• b = (x₂ – x₁)
• c = (x₁y₂ – x₂y₁)
• 计算从点到线的距离，使用（x₀，y₀）作为圆心：



• 如果该距离小于圆的半径，则您知道多边形与圆相交。

我用这种技术创建了一个样例项目在github上。

- Rob

---

那就是他所拥有的，多边形并不是矩形。 - Daij-Djan

@Daij-Djan 我使用矩形只是为了说明算法的三种情况，但这个答案并不依赖于多边形是矩形。 - Rob

嗨，罗布 - 你的回答非常好。谢谢。我已经想出了多边形顶点距离测试的方法。我循环遍历多边形的每个点，然后基本上检查它到圆心的距离：如果小于半径，就中断并返回是。我猜计算少量“点到边”的距离比计算许多“点到点”的距离更快？我将在本周测试两种方法的性能，并在此发布结果。 - capikaw

@capikaw 不是因为性能原因，我才不会执行从中心到多边形边缘的逻辑。我这样做是因为我的第三个场景，在这种情况下，即使多边形的任何一个角落都不在圆内，它们仍然相交。也许这是你不用担心的情况，那样的话就简单得多了。但我认为精确的“多边形和圆相交”逻辑可能需要它。 - Rob

当然，现在完全明白了 - 再次感谢@Rob！ - capikaw

Answer 2

以下是一个我编写的有用的MKCircle扩展，用于检查点（在本例中为多边形点）是否在圆内。仅供参考！

//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

- capikaw