The classical K-Medoids algorithm is easily trapped into local extremum and is sensitive to initialization. After analyzed the existing algorithms of spatial clustering with obstacles constraints, the paper proposed a new spatial clustering algorithm with obstacles constraints combined QPSO with K-Medoids, which named QKSCO. This algorithm introduced QPSO's rapid global convergence to separating the global clusters firstly, then it finds the optimal exact solutions of clusters by K-Medoids; and it called the two algorithms to improving the efficiency of the implementation of the new algorithm coordinating. The experimental results indicated that the algorithm has better time complexity and clustering efficiency.