测试MKCircle是否与MKPolygon相交

Question

我正在寻找测试MKPolygon是否与MKCircle相交的一些指导.目前我正在使用:

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

我发现这返回不准确的结果只是b/c它在我的圆圈周围绘制一个矩形,从而给我交叉,否则不应该.

搜索主题让我看到了Chad Saxon的多边形 - 多边形交叉项目.如果我能以某种方式将我的MKCircle转换为多边形多边形,这可能是有用的 - 这可能是可能的,但最终我相信这是解决这个问题的圆形方法.

我最终想知道在钻研我自己的自定义几何光线测试算法实现之前是否有一个我忽略的简单解决方案.

Answer 1

几点想法:

1. 如果您使用该多边形交叉项目,请注意它中有一些泄漏.我发出了一个拉取请求,修复了其中的一些(以及其他一些随机观察).我也会谨慎地采用任何一个视图控制器代码(因为它还有其他问题),但如果你对它所带来的各种限制(特别是顺时针限制,这不是真正的问题,如果你只是确定他们是否相交).

2. 不是将圆转换为一系列多边形,然后使用该多边形交集类,我可能会考虑另一种方法,利用您可以通过利用您可以查看相关点之间距离的事实来检测圆的交点.多边形和圆的半径.似乎问题有三个方面:

   • 如果任何多边形的顶点与圆的中心之间的距离小于圆的半径,则多边形和圆相交.

     

   • 多边形是否包含圆(这是特殊情况,其中多边形的所有边的距离将大于圆的半径,但圆和多边形仍显然相交).通过检查CGPath多边形视图是否包含圆的中心,可以轻松实现这一点CGPathContainsPoint.

     

   • 唯一复杂的部分是检查多边形的任何一侧是否与圆相交,即多边形的两边和圆的中心之间的最小距离小于圆的半径;

     

   为了计算每一边与圆心的距离,我可能因此遍历多边形的每一边以及面向圆的中心的那些边(即圆的中心垂直于该截面,意味着一条虚线垂直于穿过圆心的多边形边实际上穿过线段),你可以:

   • 为多边形顶点(x ₁,y ₁)和(x ₂,y ₂)之间的线段计算公式的常数a,b和c多边形的这一边:ax + by + c = 0

   • a =(y ₁ - y ₂)

   • b =(x ₂ - x ₁)

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

   • 使用(x ₀,y ₀)作为圆心:计算从点到直线的距离:

     

   • 如果该距离小于圆的半径,则表示多边形与圆相交.

我在github上放了一个采用这种技术的示例项目.