扫描线算法:是一种基于排序的算法,类比可得,最低时间复杂度O(NlogN) 扫描线算法流程:空间O(N) 扫描线从图像的一边到另一边(假设为从上到下) 扫描线会在遇到(扫描到)某个点(event point)时触发事件 对于维诺图,提出海岸线(beach line),海岸线的每条弧都是抛物线线 海岸线处于上方点和下方平直的扫描线中央...
1.一种基于wavefront算法的快速生成广义维诺图的方法,其特征在于:对于SLAM地图快速生成广义维诺图,并用A*算法进行查询寻路,具体步骤如下:步骤1:对地图进行转化,将灰度图或者SLAM所构建的地图二值化处理并将地图边界定为不可通过,得到转化后的地图图像矩阵IMG,此过程称为地图二值化过程;步骤2:将地图二值化处理后的...
摘要 本发明公开了一种基于wavefront算法的快速生成广义维诺图的方法,Voronoi图法是由俄国数学家GeorgyFedoseevichVoronoi建立的空间分割算法,它以一些离散点为基,生成一系列图块,每个图块到其对应的基的距离比到其他基的距离都要短,而图块边界上的点就到两个或者多个基的距离相等,这称为狭义上的Voronoi图。在路径...