文章版权由作者李晓晖和博客园共有，若转载请于明显处标明出处：http://www.cnblogs.com/naaoveGIS/

1.    背景

         任意多边形内部一定有一个最大圆，但是如果我们将条件设定为“任意多边形”、“最大圆”，该算法将十分复杂。比如获取多边形内任意点进行膨胀、通过碰撞检测来进行判定，算法复杂且效率低下。

       回到实际项目本身，需求为判断点是否落在规划的电子围栏内。观察电子围栏，多数是凸多边形。而我们之所以要求内部圆，是因为单纯通过外包矩形可以过滤掉的点十分有限，并且即使点落在外包矩形内后，依然不能肯定点是否落在多边形内，还是要做一次点和多边形关系的判断。考虑到实际情况中点落在多边形内是大概率事件，这将导致点面关系的判断十分频繁。而如果我们内部构造出一个圆，这个圆足够大，则可以先进行点是否在圆内的简单判断。如果这个圆可以占多边形50%的空间，则可以避免百分之五十的点和多边形的判断。那么这个圆需要是最大么，考虑到算法代价，似最大便足够。

       总结这个需求，我将其简化为，求凸多边形内部的似最大圆。

2.算法设计

       求出多边形的重心为圆心，获取重心到各边垂直距离中的最短距离为半径。

2.1获取重心

       重心的获取有两个方法：

       a.各顶点的平均值。

       b.考虑面积加权，将多边形切分为各三角形，通过平面薄板重心公式把积分变成累加和:

      

2.2获取半径

       以重心为原点，与各个边相连，将多边形划分为多个三角形，求出该顶点到三角形对边的垂直距离。

      

       a.利用海伦公式算出三角形的面积。

       b.利用三角形面积和边的长度，算出原点到对边的垂直距离。

       c.遍历此运算，得出“高”中的最短高（距离）。

3.补充多边形凹凸关系判断

       由于该算法主要针对凸多边形，所以需要对多边形进行凹凸判断。判断思路为角度合算法。

        

4.实现

    

 

　　　　　　　　　　　　　　　　　　　　　　　　　-----欢迎转载，但保留版权，请于明显处标明出处：http://www.cnblogs.com/naaoveGIS/

                                                                      　　　　  如果您觉得本文确实帮助了您，可以微信扫一扫，进行小额的打赏和鼓励，谢谢 ^_^