平面点集凸壳的快速算法

来源 :计算机工程与应用 | 被引量 : 0次 | 上传用户:pipijiayoua
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
提出一种计算平面点集凸壳的快速算法。利用极值点划分出四个矩形,它们包含了所有凸壳顶点,通过对矩形中的点进行扫描,排除明显不是凸壳顶点的点,剩余的点构成一个简单多边形。再利用极点顺序法判断多边形顶点的凹凸性并删除所出现的凹顶点,最终得到一个凸多边形即为点集的凸壳。整个算法简洁明了,避免了乘法运算(除最坏情况外),从而节省计算时间。
其他文献
对研发项目的管理不仅涉及企业高新技术资格的认定、研发费用的加计扣除优惠申请,更关系到企业的长远发展、核心竞争能力的培育和国家经济增长方式的转型.
综合管廊作为近年来国家所提倡建设的基础设施形式,具有集约化、智能化和综合化等特点。可以有效地保障城市的产业稳定高效地运行及城市市政管线的安全运营,增强城市抗灾能力、
针对传统粒子群算法的不足,提出了一种改进思想:分"初选"和"细搜"两个阶段搜索,分别设立评价能力递增的不同适应度函数和采用不同的惯性权重,进行递进式搜索;构造了一种新的网格构
泰国内阁批准了泰中铁路合作项目一期工程(曼谷一呵叻段)的设计合同,为泰中双方尽快落实签署创造了条件.中国驻泰国大使馆日前发布公告说,中泰双方已完成了中泰铁路合作项目一
通过建立(72+128+72)m高速铁路大跨度连续刚构桥-轨道系统模型,研究梁、墩单独存在温度梯度时系统受力变形特征,比较梁墩同时存在温度梯度与单独存在温度梯度对系统受力变形
针对某生物杀螺剂制作中多目标约束问题,提出了一种应用Pareto遗传算法来解决问题的优化方法。建立了用于多目标优化的适应度函数,使用排列选择方法将带约束的多目标问题转换为
针对在建怀邵衡铁路岩鹰鞍隧道F4断层,为解决隧道施工过程中遇富水含砂断层安全风险,通过对隧道涌水涌砂风险数据分析、方案比选、力学验算确定合理的施工参数,研究形成完善的隧
无线传感网络普遍使用CSMA/CA机制和二进制指数退避算法避免碰撞。提出了一种能量有效的免碰撞MAC协议ERC。该协议将数据传输划分为协商和节点排队传输两个阶段,通过碰撞避免
从2005年年初到2008年5月间.美元指数从85下降到73.黄金价格由400美元/盎司上涨到1045美元/盎司.石油价格从48美元/桶上涨到125美元/桶……所有数据都显示出美元在贬值.其购买力也在
参数曲线集将平面划分为多个区域,区域的准确识别和提取是矢量图案填充的基础。目前,已经有多种光栅图形学区域识别的成熟算法,但准确、快速地识别任意复杂参数曲线集目标区域还比较困难,其关键问题是:如何利用计算机有效地描述参数曲线集划分的多个区域(内含孔、岛)以及准确地识别目标区域。从空间认知的需求出发,采用图论中的多叉树形式化表达区域的空间组织结构,在建立定向闭环的基础上,给出了目标区域的自动识别方法。