Clustering with constraints
Each clustering algorithm in my knwledge is based on distance, which is calculated as pairwise differences. So I'm not sure if it is easy to find a general more elegant approach. 

In you case you can calculate the distance and than override it based on your constraint.

Here an simple example reduced to one numerical dimension with distance threshold 30.

 nlst &lt;- c(1,3,5, 36,39,42, 1001,1003,1005, 1036,1039,1042)

 d &lt;- dist(nlst, method="euclidean")
 dr &lt;- as.dist(ifelse(as.matrix(d) &gt; 30, NA, 0))


     1  2  3  4  5  6  7  8  9 10 11
 2   0                              
 3   0  0                           
 4  NA NA NA                        
 5  NA NA NA  0                     
 6  NA NA NA  0  0                  
 7  NA NA NA NA NA NA               
 8  NA NA NA NA NA NA  0            
 9  NA NA NA NA NA NA  0  0         
 10 NA NA NA NA NA NA NA NA NA      
 11 NA NA NA NA NA NA NA NA NA  0   
 12 NA NA NA NA NA NA NA NA NA  0  0 


A scan through the points collecting those with distance zero will give the result clustering.

This should be always possible if your constraints are local (i.e. depending only on the two points for which you calculate the distance).