基于四边形改进二维凸包生成算法
凸包生成算法已在模式识别、求解TSP 问题、GIS(地理信息系统)、巡航预警等各个方面得到应用，传统的生成凸包算法时间复杂度相对较高和生成凸包的时间较长，不适用于处理数据量较大的凸包生成。为此本文提出运用四边形进行预处理点集的思想，即遍历点集寻找x 坐标和y 坐标的极值点(最大点和最小点)，利用四个极值点构成四边形将其内部的点删除。同时将四边形外的点分为四个子点集，计算出每一个子点集中的点与基点的斜率。然后根据斜率运用合并排序对每一个点集中的点按照斜率进行排序，最后在运用向量叉积算法求得分区中的点是否为凸包上的点。该算法在运算速度上相对于Graham 算法有一定提升。
凸包 平面点集 极值点 Graham算法
张照贝 李海明
上海电力大学计算机科学与技术学院 中国上海市200000
国内会议
上海
中文
364-372
2019-05-17（万方平台首次上网日期，不代表论文的发表时间）