一种求任意多边形内部水平方向似最大矩形的算法

简介: 文章版权由作者李晓晖和博客园共有,若转载请于明显处标明出处:http://www.cnblogs.com/naaoveGIS/1.背景       在前一篇中,我们探讨了如何求凸多边形中的似最大圆,但是针对实际情况需求,我们并没有完全解决问题。

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

1.背景

       在前一篇中,我们探讨了如何求凸多边形中的似最大圆,但是针对实际情况需求,我们并没有完全解决问题。实际情况中,凹凸多边形同时存在,并且在行政区划应用上,凹多边形更多。所以这里我们依然得探讨如何在任意多边形中得出其内部的似最大矩形或者似最大圆。

       这里,我们将方向优先选择为求似最大矩形,原因有二:矩形的判断不涉及运算,效率更高;更重要的原因是,之后我们构建R树索引,基于矩形会更加便捷。

2.算法详解

       在我之前的文章《网格索引判断点面关系的方法》(http://www.cnblogs.com/naaoveGIS/p/5148185.html),提到了GIS中常用的网格方法。同样,这里我将把该网格法的思路引入至算法中。

                       

       具体描述为:

       a.获取任意多边形的四角坐标,通过四角坐标构造矩形,将该矩形划分成N*M个规则格网。

       b.遍历所有格网,判断每个格网和多边形的包含关系。格网在多边形中,则标记为1,否则为0。

       c.计算由0和1组成的矩形中,由1组成的最大矩形。

       d.求得所得最大矩形代表的四角坐标,构造成真实地理矩形。

3.算法探讨

       a.该算法最大的难点在于计算由0和1组成的矩形中,由1组成的最大矩形:

                           

       b.该算法获取的矩形是否为最大取决于网格的划分粒度,实际项目中,要进行综合考虑。实际上,只要能够逼近,是否最大不重要。

4.算法实现

 

 

5.问题扩展

       昨天一个朋友问了一个相似的问题,项目背景为土地利用分析,需要提取任意规划土地内一平方公里的样本。

       利用网格的思想,该问题同样能很好的解决。

      

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

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

                                      

目录
相关文章
|
1月前
|
算法 vr&ar 图形学
☆打卡算法☆LeetCode 223. 矩形面积 算法解析
☆打卡算法☆LeetCode 223. 矩形面积 算法解析
|
8月前
|
算法 测试技术 C#
C++前缀和算法应用:矩形区域不超过 K 的最大数值和
C++前缀和算法应用:矩形区域不超过 K 的最大数值和
|
8月前
|
算法 测试技术 C++
C++算法:柱状图中最大的矩形
C++算法:柱状图中最大的矩形
|
6天前
|
算法 JavaScript 前端开发
在JavaScript中实现基本的碰撞检测算法,我们通常会用到矩形碰撞检测,也就是AABB(Axis-Aligned Bounding Box)碰撞检测
【6月更文挑战第16天】JavaScript中的基本碰撞检测涉及AABB(轴对齐边界框)方法,常用于2D游戏。`Rectangle`类定义了矩形的属性,并包含一个`collidesWith`方法,通过比较边界来检测碰撞。若两矩形无重叠部分,四个条件(关于边界相对位置)均需满足。此基础算法适用于简单场景,复杂情况可能需采用更高级的检测技术或物理引擎库。
42 6
|
21小时前
|
算法 Python
二维矩形件排样算法之最低水平线搜索算法实现
二维矩形件排样算法之最低水平线搜索算法实现
5 0
|
21小时前
|
机器学习/深度学习 移动开发 算法
二维矩形件排样算法之最低水平线算法实现
二维矩形件排样算法之最低水平线算法实现
2 0
|
28天前
|
算法
多边形裁剪算法
多边形裁剪算法
多边形扫描转换-扫描线算法
多边形扫描转换-扫描线算法
|
1月前
|
算法
代码随想录算法训练营第六十天 | LeetCode 84. 柱状图中最大的矩形
代码随想录算法训练营第六十天 | LeetCode 84. 柱状图中最大的矩形
25 3
|
1月前
|
算法 图形学
【头歌 计算机图形学 练习】多边形填充v1.0 (第1关:扫描线填充算法(活动边表AET法) 第2关:边缘填充法 第3关:区域四连通种子填充算法 第4关:区域扫描线种子填充算法)
【头歌 计算机图形学 练习】多边形填充v1.0 (第1关:扫描线填充算法(活动边表AET法) 第2关:边缘填充法 第3关:区域四连通种子填充算法 第4关:区域扫描线种子填充算法)
249 0