一种高效的组团或自然村覆盖范围凸包生成算法

摘要

在宽带业务需求点规划时,每个业务需求点都归属于一个组团或自然村,实际工作中,需要在地图上利用业务需求点来描述组团或自然村的覆盖范围,组团或自然村覆盖范围描述问题从本质上就是计算其所包含的业务需求点的最小凸包。提出一种计算业务需求点凸包的快速算法。首先,获取基准点,通过对业务点集进行全量扫描,寻找两个维度的4个极值点;其次,利用这4个极值点,构造初始凸包;接着,排除初始凸包内的业务需求点;随后,利用分治思想对剩余点进行分组,每组运用Graham算法计算生成凸包;最后,将所有子集的凸包顶点作为一个新的集合,再次运用Graham算法生成最终凸包。