带障碍物情况下两点间最短距离的求解方法  

Solution of Shortest Distance Between Two Points in Presence of Obstacles

作　　者：陈智鹏[1] 杨诗琴[2] 

机构地区：[1]上海电机学院电子信息学院,上海200240 [2]上海电机学院信息化办公室,上海200240

出　　处：《计算机工程》2010年第16期171-173,共3页Computer Engineering

基　　金：上海市高校选拔培养优秀青年教师科研专项基金资助项目(09A112)

摘　　要：带障碍物聚类问题的关键是求解存在障碍物情况下两点间的最短距离。针对该问题提出边缘可见点概念,给出一种解决方法,从一点依次寻找障碍物上的边缘可见点,顺次连接这些点,可以形成上边缘最短路径和下边缘最短路径,最终的最短路径是这两者中的较短者。实验结果验证了该方法的有效性。A key of the Clustering with Obstructed Distance（COD） problem is solving the shortest distance between two points in the presence of obstacles.Aiming at this problem,this paper presents the concept of edge visible points,and proposes a solution to the problem.It departs from the point,and finds edge visible points on the set of obstructions,and sequential connects these points.It forms a shortest path along upper edge and a shortest path along lower edge,the final shortest path is the shorter of the two.Experimental results verify the effectiveness of the method.

关 键 词：聚类 障碍物 凸多边形 边缘可见点 

分 类 号：TP391[自动化与计算机技术—计算机应用技术]