文档名：基于四边形改进二维凸包生成算法
凸包生成算法已在模式识别、求解TSP问题、GIS(地理信息系统)、巡航预警等各个方面得到应用,传统的生成凸包算法时间复杂度相对较高和生成凸包的时间较长,不适用于处理数据量较大的凸包生成.为此本文提出运用四边形进行预处理点集的思想,即遍历点集寻找x坐标和y坐标的极值点(最大点和最小点),利用四个极值点构成四边形将其内部的点删除.同时将四边形外的点分为四个子点集,计算出每一个子点集中的点与基点的斜率.然后根据斜率运用合并排序对每一个点集中的点按照斜率进行排序,最后在运用向量叉积算法求得分区中的点是否为凸包上的点.该算法在运算速度上相对于Graham算法有一定提升.
作者：张照贝李海明
作者单位：上海电力大学计算机科学与技术学院中国上海市200000
母体文献：2019年上海市“智能计算与智能电网”研究生学术论坛论文集
会议名称：2019年上海市“智能计算与智能电网”研究生学术论坛
会议时间：2019年5月17日
会议地点：上海
主办单位：上海市学位委员会
语种：chi
分类号：TP3TN9
关键词：二维凸包生成算法 时间复杂度 平面点集 运算速度
在线出版日期：2022年9月21日
基金项目：
相似文献
相关博文
- 文件大小:
- 802.95 KB
- 下载次数:
- 60
-
高速下载
|
|
