譜聚類（Spectral Clustering）是一種廣泛使用的數(shù)據(jù)聚類算法，[Liu et al. 2004]基于譜聚類算法首次提出了一種三維網(wǎng)格分割方法。該方法首先構建一個相似矩陣用于記錄網(wǎng)格上相鄰面片之間的差異性，然后計算相似矩陣的前k個特征向量，這些特征向量將網(wǎng)格面片映射到k維譜空間的單位球上，最后使用K-means方法對譜空間中的數(shù)據(jù)點進行聚類。具體算法過程如下：
一．相似矩陣
網(wǎng)格分割以面片為基本單元，為了能使算法沿著幾何模型的凹形區(qū)域進行分割，網(wǎng)格相鄰面片之間的距離采用[Katz et al. 2003]中提到的方法，具體形式在“三維網(wǎng)格分割算法”中有所解釋，距離由測地距離Geod_Dist和角度距離Ang_Dist兩部分組成，如下所示：
