一种求凸多边形内部似最大圆的算法

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

1.    背景

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

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

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

2.算法设计

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

2.1获取重心

       重心的获取有两个方法:

       a.各顶点的平均值。

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

      一种求凸多边形内部似最大圆的算法

2.2获取半径

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

      一种求凸多边形内部似最大圆的算法

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

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

       c.遍历此运算,得出“高”中的最短高(距离)。

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

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

        一种求凸多边形内部似最大圆的算法

4.实现

    一种求凸多边形内部似最大圆的算法

 

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

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

                                         一种求凸多边形内部似最大圆的算法

上一篇:全景虚拟漫游技术实现(three.js vs ThingJS) Javascript 3D开发 前端 物联网 webgl 三维建模 3D模型 虚拟 全景


下一篇:控件产品官方文档/手册/API列表汇总