Abstract: The Delaunay triangulation skeleton is a widely applied spatial partitioning structure for cartographic generalization. An algorithm for skeleton extraction of the gap space between map objects based on a constrained Delaunay triangulation was improved. From the perspective of program design，we describe the data structure and the control process of the algorithm in detail. According to the number of constrained edges,triangles are assigned into four types，i. e.，type-0，type-1，type-2 and type-3. By using type-0，type-2 and single-path type-1 triangles as starting or ending triangles，and two-path type-1 triangles as channel triangles，the whole triangulation is traversed. In addition，corresponding treatments are proposed for some special cases，e. g.，looped triangle paths of and type-3 triangles.The algorithm is used for contour interpolation and proximity analysis of map objects in a district. The results show that the algorithm is feasible and robust.