MathGroup Archive 1995

[Date Index] [Thread Index] [Author Index]

Search the Archive

Re: 3D Cluster Detection

Fergal Shevlin <fshevlin at>
>Subject: [mg2413] 3D Cluster Detection
Asks about dealing with clusters of points in R3(message attached)


The function Clusters,below might be of use. You can also use the  
function ConnectedComponents from the standard package
DiscreteMath`Combinatorica`, but some preliminary setting up is  
needed and the final calculation is much slower than with this more  
limited function.
The supporting function, Split, seems to be very useful.

Clusters::usage = "Clusters[lst,d] for a list of points in Rn gives
the equivalence classes of the equivalence relation generated by the 
relation x ~ y <=> Max[Abs[x - y]] <=d
Clusters[lst,d] for a list, lst, of non-complex numbers works  
Clusters[{{1,0},{1,9},{8,9},{3,2}},2] -->\n
{{{1, 0}, {3, 2}}, {{1, 9}}, {{8, 9}}} ";

Split::usage = "Split[lst] for a list lst splits lst into sublists at 
each change in entry: {1,2,2,2,3,3} gives {{1},{2,2,2},{3,3}}.
Split[lst,crit] splits between x and y when crit[x,y] is not

Split[e_, tst_:SameQ]:=
		con[{x___,u:A[___,m_]},p_]/;tst[m,p] := {x,A[u,p]};
		con[u:{___,A[___,m_]},p_] := {u,A[p]};
		con[{},p_] = {A[p]};
		Apply[List,Flatten/@Flatten[Fold[con,{}, e]],1]

clusters1[d_][lst_] := Split[ Sort[lst], (#2[[1]]-#1[[1]] <=d)&];

Clusters[lst_?VectorQ,d_] := clusters1[d][lst]

Clusters[lst_?MatrixQ,d_] :=

Allan Hayes
hay at

Begin forwarded message:

>From: Fergal Shevlin <fshevlin at>
>To: mathgroup at
>Subject: [mg2413] 3D Cluster Detection
>Organization: Dept. of Maths, Trinity College, Dublin, Ireland.


I have a list of Real 3D points, each coordinate having a value
between 0 and 2 Pi. Within this list there are several
"clusters" of points, i.e. the coordinates agree to several
decimal places. Each cluster is quite distinct from the other,
for example when I view the points with
I see 4 points, despite the fact that there are hundreds in
the list.

Can anybody suggest a means of automatically detecting the
means or modes of these clusters?

Thanks in advance,
Fergal Shevlin                    Phone: +353-1-6081209 Fax: 6772204 
Dept. of Computer Science            
Trinity College, Dublin 2, Ireland.         Fergal.Shevlin at

  • Prev by Date: Re: Re: Puzzle
  • Next by Date: question: {a,b,c}->{{a,b},{b,c}}??
  • Previous by thread: 3D Cluster Detection
  • Next by thread: Axel's question