MathGroup Archive 2007

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

Search the Archive

Re: Identifying clusters of adjacent points on a lattice — Solution

  • To: mathgroup at smc.vnet.net
  • Subject: [mg81425] Re: Identifying clusters of adjacent points on a lattice — Solution
  • From: Gareth Russell <russell at njit.edu>
  • Date: Sun, 23 Sep 2007 04:29:00 -0400 (EDT)
  • References: <fcvr81$7r9$1@smc.vnet.net>

Hi again,

Daniel Lichtblau pointed me towards WeakComponents[]. I contructed a 
function around that to process a binary matrix such that each 
connected patch of 1's is replaced by a patch of distinct integers 1, 
2, ... n where n is the total number of patches. I takes about 1 second 
to process a 100 by 100 matrix with approx 250 patches. The last line 
can easily be altered to produce {x,y,i} triples. I post it in here in 
case it's useful to anyone.

Gareth



findPatches[m_] :=
 Module[{x, y, indexMatrix, rowEdges, colEdges, allIndices, clusterIndices,
   soloIndices, xy, groups},
  Needs["GraphUtilities`"];
  x = Length[m[[1]]];
  y = Length[m];

  indexMatrix = Table[i*x + j, {i, 0, y - 1}, {j, 0, x - 1}];

  rowEdges =
   DeleteCases[
    Flatten[
     Table[
      If[{m[[i, j]], m[[i, j + 1]]} == {1, 1},
       indexMatrix[[i, j]] -> indexMatrix[[i, j + 1]], 0], {i, 1, y}, {j, 1,
       x - 1}]], _Integer];

  colEdges =
   DeleteCases[
    Flatten[
     Table[
      If[{m[[i, j]], m[[i + 1, j]]} == {1, 1},
       indexMatrix[[i, j]] -> indexMatrix[[i + 1, j]], 0], {j, 1, x}, {i, 1,
       y - 1}]], _Integer];

  allIndices = Flatten[Extract[indexMatrix, Position[m, 1]]];
  clusterIndices = WeakComponents[Join[rowEdges, colEdges]];
  soloIndices = Complement[allIndices, Flatten[clusterIndices]];

  xy = Map[{Floor[#/x] + 1, Mod[#, x] + 1} &,
    Join[clusterIndices, Map[{#} &, soloIndices]], {2}];

  groups = Range[Length[xy]];

  Normal[SparseArray[
    Flatten[Table[Map[# -> groups[[i]] &, xy[[i]]], {i, 1, Length[groups]}],
     1],{y,x}]]
  ]

On 2007-09-21 03:18:25 -0400, Gareth Russell <russell at njit.edu> said:

> Hi,
> 
> Is there any way to use the built-in clustering routines to find
> clusters of ajacent elements on a 2d lattice? For example, I might
> generate a 'map' with
> 
> SeedRandom[1];
> testMap = =E2=80=A8 Last[CellularAutomaton[{1018, {2, {{0, 2, 0}, {2, 1, 2},
> {0, 2, 0}}}, {1, =E2=80=A8     1}}, Table[If[Random[Real] < 0.1, 1, 0], {100},
> {100}], 10]];
> 
> I would then like to find and label the separate 'patches' consisting
> of clusters of 1's. Ultimately, I'm looking for a list of {x,y,id}
> triples where the x and y are the coordinates of each 1 and the id is a
> number that identifies the patch to which that element belongs, but the
> trick is to find the clusters. I can't see how any of the included
> options for FindClusters would perform this particular test (each
> cluster must consist of elements connected to at least one other
> element by a distance of 1).
> 
> Of perhaps there is another way?
> 
> Thanks,
> 
> Gareth


-- 
Gareth Russell
NJIT



  • Prev by Date: Re: LegendreP error (bug?) in Mathematica
  • Next by Date: Re: Re: FullSimplify regress?
  • Previous by thread: Re: Any Mathematica 6 book yet?
  • Next by thread: simple question about plot/evaluate