Abstract: 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.

Key words: clustering, obstacles, convex polygon, edge visible point

摘要： 带障碍物聚类问题的关键是求解存在障碍物情况下两点间的最短距离。针对该问题提出边缘可见点概念，给出一种解决方法，从一点依次寻找障碍物上的边缘可见点，顺次连接这些点，可以形成上边缘最短路径和下边缘最短路径，最终的最短路径是这两者中的较短者。实验结果验证了该方法的有效性。

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

CLC Number: 

• TP391