Visibility Aware Obstacle Clustering and Path Planning
摘要
Clustering point sites in the two-dimensional plane is a well explored problem with applications that include robotics, data mining, and image processing. This paper deals with the problem of clustering polygonal obstacles in the plane. The objective is to extract polygon clusters that satisfy certain compactness properties. The compactness is measured in term of a pre-determined parameter δ such that any obstacle in the cluster is no more than δ distance from its closest neighbor. Such clusters are referred to as δ -clusters. The objective is to transform n polygonal obstacles into m δ-clusters (m < n) so that each δ-cluster can be treated as a single aggregated obstacle. Existing clustering algorithms for point clustering and obstacle clustering are reviewed. The visibility properties of δ-clusters are introduced and algorithms for checking whether a given δ-clusters is visible from its outer boundary are presented. Applications of boundary visible δ-clusters in path planning problem is discussed.