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

简介: 文章版权由作者李晓晖和博客园共有,若转载请于明显处标明出处:http://www.cnblogs.com/naaoveGIS/1.    背景         任意多边形内部一定有一个最大圆,但是如果我们将条件设定为“任意多边形”、“最大圆”,该算法将十分复杂。

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

1.    背景

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

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

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

2.算法设计

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

2.1获取重心

       重心的获取有两个方法:

       a.各顶点的平均值。

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

      

2.2获取半径

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

      

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

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

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

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

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

        

4.实现

    

 

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

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

                                         

目录
相关文章
|
5月前
|
弹性计算 运维 算法
阿里云 Elasticsearch Serverless 检索增强型 8.17 版来袭!
阿里云Elasticsearch Serverless 8.17版本,深度融合无服务器架构与分层扩展能力,面向信息检索、向量搜索、语义分析等通用场景,提供全托管服务,在最新特性扩展、自动扩缩性能、资源成本优化等维度均有显著提升。
236 15
|
7月前
|
人工智能 安全 Linux
《2024 龙蜥操作系统开源社区白皮书》正式发布 引领开源操作系统新征程
该白皮书详细阐述了龙蜥社区在技术创新、生态建设等多方面的成果与规划。
《2024 龙蜥操作系统开源社区白皮书》正式发布 引领开源操作系统新征程
|
11月前
|
机器学习/深度学习 C# 索引
HashMap的容量为什么一定是2^n?
`HashMap` 的容量设计为 `2^n` 主要出于三个考虑:1) 位运算效率高,通过 `(hash & (capacity - 1))` 快速计算索引;2) 元素分布均匀,减少哈希冲突,提高性能;3) 扩容时只需检查最高位,简化重分布过程,提升扩容效率。初始容量为 `1 << 4`(16),扩容以2倍递增。
262 0
HashMap的容量为什么一定是2^n?
|
9月前
|
前端开发 Java 程序员
面试官刁钻提问?轻松应对 break、continue 和 return 的巧妙用法
本次分享的主题是在面试break社招时被问到continue和return的区别与作用,面试官还刁钻的问了一些场景使用的坑点,小伙伴表示不太懂,现场有点慌。今天由我来给大家深入讲讲这三个关键词的区别和作用还会结合一些实战例子,保证你看完后不仅面试游刃有余,临时写代码也更得心应手,我们分为以下四部分。 1.了解背景铺垫的相关知识 2.Break、continue和return的定义 3.使用代码来实现三个关键字的逻辑 4.三个关键字在实践中应注意的坑点
|
机器学习/深度学习 人工智能 自然语言处理
机器学习、深度学习和强化学习的关系和区别是什么?
众所周知,人工智能领域知识庞大且复杂,各种专业名词层出不穷,常常让初学者看得摸不着头脑。比如“机器学习”、“深度学习”、“强化学习”就属于这类名词。那么,针对这三者各自具体有哪些内容?三者是否有相关性?不同核心及侧重点是什么?以及各自的应用领域有哪些?应用的前景如何?等问题,本文根据百度百科等相关资料里的内容进行整理,形成了以下详细的阐述。
2551 0
HTML【详解】表格 table 标签(table的属性,语义化表格,简易表格,合并单元格)
HTML【详解】表格 table 标签(table的属性,语义化表格,简易表格,合并单元格)
530 0
HTML【详解】表格 table 标签(table的属性,语义化表格,简易表格,合并单元格)
|
算法 Java 索引
单元格法近似求解多边形最大内接矩形问题【思路讲解+java实现】
单元格法近似求解多边形最大内接矩形问题【思路讲解+java实现】
462 0
|
Ubuntu Linux 计算机视觉
Linux安装和使用OpenCV
Linux安装和使用OpenCV
|
编解码 芯片 内存技术
数字基带传输系统 1
数字基带传输系统
557 0
|
并行计算 数据可视化 PyTorch