Partitioning a superset of coordinates into subsets that generate continuous curves

Consider the data set corresponding to recorded trajectories for a particle:

PairSet = {{108.892, 171.947}, {111.137, 165.402}, {108.899, 171.874}, {108.945,171.857}, {108.924, 171.864}, {108.884, 171.873}, {108.88, 171.843}, {108.89, 171.87}, {108.885, 171.851}, {108.955, 172.041}, {109.343, 172.278}, {108.946, 172.044}, {108.975, 172.115}, {111.287, 165.828}, {111.316, 165.817}, {111.332, 165.64}, {111.45, 165.793}, {111.413, 165.761}, {108.909, 172.09}, {108.93, 172.079}, {108.958, 172.182}, {109.011, 172.185}, {109.002, 172.181}, {111.192, 165.535}, {111.176, 165.526}, {111.175, 165.509}, {111.174, 165.525}, {111.166, 165.513}, {111.165, 165.501}, {111.161, 165.54}, {108.963, 172.128}, {108.968, 172.095}, {111.341, 165.686}, {111.362, 165.69}, {108.932, 171.696}, {108.944, 171.723}, {108.948, 171.731}, {110.933, 169.149}, {110.944, 169.123}, {110.954, 169.095}, {111.285, 165.491}, {111.278, 165.505}, {111.287, 165.492}, {111.278, 165.446}, {109.027, 171.606}, {109.021, 171.606}, {108.841, 171.503}, {108.864, 171.464}, {108.847, 171.469}, {108.866, 171.31}, {110.938, 165.172}, {109.026, 171.374}, {111.237, 165.29}, {111.248, 165.311}, {111.375, 165.291}, {111.395, 165.292}, {111.38, 165.301}, {111.392, 165.312}, {108.851, 171.421}, {109.099, 171.436}, {109.076, 171.388}, {109.111, 171.272}, {109.126, 171.294}, {108.944, 170.892}, {108.928, 170.883}, {111.312, 164.951}, {111.346, 164.942}, {111.346, 164.952}, {111.372, 164.95}, {108.738, 171.068}, {108.736, 171.087}, {108.746, 171.101}, {108.736, 171.069}, {108.738, 171.078}, {108.76, 171.063}, {108.751, 171.057}, {111.149, 164.876}, {108.881, 171.343}, {108.856, 171.099}, {108.62, 171.223}, {109.003, 171.17}, {109.007, 171.185}, {109.016, 171.179}, {108.935, 171.132}, {108.991, 171.296}, {111.094, 164.747}, {110.841, 164.757}, {110.884, 164.754}, {111.039, 165.13}, {110.77, 164.802}, {110.783, 164.826}, {111.142, 164.938}, {108.651, 171.395}, {108.652, 171.399}, {108.647, 171.399}, {108.659, 171.395}, {108.648, 171.398}, {108.658, 171.397}, {108.578, 171.345}, {108.554, 171.335}, {111.051, 164.885}, {111.058, 164.899}, {111.055, 164.9}, {111.156, 165.11}, {111.178, 165.167}, {111.196, 165.151}, {111.177, 165.157}, {110.952, 164.798}, {110.907, 164.989}, {110.922, 165.013}, {110.932, 165.012}, {110.902, 164.98}, {108.896, 171.168}, {108.88, 171.175}, {111.102, 164.846}, {111.067, 164.887}, {111.067, 164.888}, {108.648, 171.394}, {108.648, 171.377}, {108.641, 171.375}, {107.69, 174.79}, {107.642, 174.85}, {107.627, 174.829}, {107.644, 174.877}, {111.122, 164.697}, {108.848, 171.054}, {111.01, 164.69}, {111.01, 164.692}, {110.746, 164.674}, {110.768, 164.676}, {110.975, 164.747}, {110.963, 164.738}, {108.965, 171.145}, {109.041, 171.139}, {108.884, 170.805}, {109.147, 170.753}, {109.032, 170.858}, {108.835, 170.681}, {111.088, 164.242}, {111.126, 164.256}, {110.601, 168.27}, {110.954, 164.199}, {108.832, 170.403}, {108.883, 170.49}, {110.98, 164.164}, {110.964, 164.111}, {108.765, 170.363}, {108.813, 170.506}, {108.793, 170.518}, {107.659, 174.865}, {111.342, 164.143}, {111.132, 164.165}, {109.124, 170.116}, {109.117, 170.133}, {111.91, 164.068}, {111.976, 164.061}, {108.765, 170.258}, {109.286, 170.032}, {109.28, 170.019}, {109.287, 170.019}, {109.09, 169.663}, {111.225, 163.281}, {109.332, 169.637}, {109.326, 169.594}, {109.353, 169.607}, {109.343, 169.608}, {109.337, 169.565}, {111.197, 163.28}, {111.213, 163.269}, {111.216, 163.275}, {111.203, 163.264}, {109.034, 169.885}, {109.026, 169.906}, {111.536, 163.575}, {111.49, 163.534}, {111.228, 163.495}, {111.39, 163.298}, {111.384, 163.283}, {111.445, 163.063}, {111.472, 163.108}, {111.4, 163.212}, {111.37, 163.221}, {111.342, 163.259}, {110.185, 163.519}, {111.249, 163.328}, {109.135, 167.653}, {109.055, 169.794}, {111.196, 163.518}, {111.17, 163.487}, {111.048, 163.661}, {111.044, 163.666}, {108.701, 170.581}, {108.698, 170.618}, {108.711, 170.635}, {110.894, 164.58}, {110.908, 164.587}, {110.893, 164.575}, {110.895, 164.57}, {108.835, 171.427}, {108.779, 171.484}, {108.799, 171.484}, {108.783, 171.468}, {110.824, 165.108}, {110.828, 165.108}, {110.812, 165.127}, {108.397, 171.888}, {108.426, 171.897}, {108.706, 171.69}, {108.667, 171.786}, {108.615, 171.807}, {108.549, 172.089}, {108.561, 172.094}, {108.55, 172.11}, {108.562, 172.11}, {108.58, 172.18}, {108.592, 172.226}, {108.576, 172.232}, {108.566, 172.22}, {108.572, 172.233}, {108.572, 172.228}, {108.59, 172.254}, {108.589, 172.25}, {108.577, 172.249}, {108.589, 172.246}, {108.588, 172.249}, {108.609, 172.5}, {108.559, 172.793}, {110.494, 166.216}, {108.446, 171.122}, {108.381, 171.131}, {110.422, 166.838}, {110.432, 166.819}, {110.406, 166.852}, {110.401, 166.827}, {110.446, 166.846}, {110.566, 166.88}, {110.544, 166.864}, {110.552, 166.886}, {107.959, 172.963}, {107.968, 172.983}, {108.013, 172.978}, {107.98, 173.003}, {108., 172.99}, {108.004, 172.986}, {107.991, 172.959}, {107.982, 173.021}, {107.947, 173.016}, {108.021, 173.086}, {108.003, 172.968}, {107.996, 173.051}, {108.012, 173.012}, {107.967, 172.971}, {107.977, 172.994}, {107.964, 173.044}, {107.997, 173.044}, {108.014, 173.001}, {110.322, 167.291}, {110.691, 167.434}, {110.66, 167.429}, {110.544, 167.344}, {110.569, 167.402}, {108.088, 173.691}, {108.107, 173.677}, {110.533, 167.449}, {110.539, 167.447}, {108.212, 173.801}, {110.576, 167.628}, {108.131, 173.963}, {108.111, 173.969}, {110.11, 167.837}, {110.291, 167.796}, {110.296, 167.817}, {110.295, 167.82}, {110.289, 167.811}, {108.208, 173.96}, {108.073, 174.004}, {108.081, 174.057}, {107.847, 174.163}, {110.365, 167.818}, {110.356, 167.844}, {107.833, 174.322}, {107.985, 174.4}, {107.97, 174.467}, {108.057, 174.418}, {110.317, 168.33}, {110.284, 168.327}, {110.313, 168.326}, {109.963, 168.459}, {109.96, 168.424}, {107.616, 174.794}, {107.617, 174.79}, {110.08, 168.919}, {107.833, 174.947}, {107.844, 174.938}, {109.614, 168.861}, {109.822, 168.763}, {109.804, 168.759}, {109.93, 169.046}, {109.925, 169.035}, {109.929, 169.025}, {109.77, 168.641}, {109.773, 168.636}, {109.757, 168.638}, {107.534, 174.886}, {107.8, 175.148}, {109.848, 168.929}, {109.839, 168.937}, {107.656, 174.944}, {107.676, 174.944}, {107.327, 175.152}, {107.688, 174.778}, {107.636, 175.091}, {107.62, 175.103}, {107.638, 175.11}, {109.77, 168.778}, {109.762, 168.755}, {107.376, 174.939}, {107.371, 174.936}, {109.459, 168.727}, {111.82, 166.633}, {109.48, 168.559}, {109.462, 168.546}, {109.47, 168.553}, {109.64, 168.266}, {109.591, 168.279}, {108.609, 171.012}, {107.228, 174.63}, {107.247, 174.615}, {109.842, 168.014}, {109.745, 168.066}, {109.78, 168.074}, {109.99, 168.346}, {107.722, 174.066}, {109.67, 167.676}, {107.37, 174.28}, {107.378, 174.261}, {107.542, 174.208}, {107.576, 174.236}, {107.56, 174.239}, {107.567, 174.223}, {109.702, 167.667}, {107.272, 173.779}, {109.666, 167.402}, {109.602, 167.377}, {109.745, 167.237}, {109.671, 167.249}, {109.087, 167.369}, {107.71, 173.134}, {107.673, 173.173}, {109.811, 166.979}, {109.847, 166.96}, {109.845, 166.976}, {109.85, 166.959}, {109.863, 166.922}, {107.568, 172.868}, {107.659, 172.918}, {107.884, 173.044}, {110.114, 165.957}, {110.133, 165.984}, {110.147, 165.98}, {107.929, 172.094}, {107.959, 172.093}, {110.358, 165.823}, {108.221, 171.547}, {110.215, 165.408}, {110.219, 165.102}, {110.37, 165.374}, {110.421, 165.402}, {107.914, 171.519}, {110.399, 164.974}, {110.396, 164.987}, {108.294, 171.308}, {110.588, 164.718}, {111.676, 167.232}, {110.278, 164.873}, {108.114, 171.214}, {108.053, 171.228}, {108.042, 171.209}, {108.23, 170.952}, {108.48, 170.917}, {108.426, 170.943}, {110.812, 164.669},{107.51, 174.18}, {108.6, 176.258}, {108.764, 170.599}, {108.651, 170.367}, {108.782, 170.467}, {111.037, 164.138}, {110.811, 164.195}, {110.821, 164.195}, {108.854, 170.189}, {108.881, 170.175}};


Running ListPlot on PairSet generates a fairly noisy plot:

However, we see something surprising if (treating the elements of PairSet as $(x,y)$ coordinates) we plot the $x$ and $y$ values separately:

Plot for $x$-values:

Plot for $y$-values:

Here, we can clearly see we have inadvertently tracked a pair of particles instead of a single particle. We can also find instances where three or more seperate trajectories can be distinguished.

Is there some manner to automatically decompose PairSet (or the hypothetical TriSet, etc.) into lists of values:

 ParticleList = {Particle1, Particle2}


...corresponding to each of two or more curves, s.t. these trajectories can be independently fit and averaged?

-

This is a straightforward application of FindClusters:

ListPlot@FindClusters[#, 2] & /@ Transpose@PairSet // GraphicsRow


See the DistanceFunction and Method options to further fine tune your clustering or use a different metric.

-
There's a logical problem: the visual clustering uses time, which FindClusters doesn't know about. Randomly reordering PairSet destroys the obvious structure in the plots of x vs t and y vs t but does not change the FindCluster results. – Ray Koopman Jul 29 '13 at 8:57
@RayKoopman Good point. Do you have a suggestion how to make use of the time ordering? – Sjoerd C. de Vries Jul 30 '13 at 9:59
@SjoerdC.deVries: Not yet. – Ray Koopman Jul 30 '13 at 15:09

I tried to proceed from the approach mentioned by rm -rf. Using the Method option DistanceFunction -> EuclideanDistance helped in the example dataset you provided to get rid of the definition of the number of clusters. I'm not sure if this works out for multiple trajectories which are more messed up. The option gives about the same clustering of X and Y coordinates:

{clustersX, clustersY} =
FindClusters[#, DistanceFunction -> EuclideanDistance] & /@
Transpose@PairSet;

ListPlot[#, PlotStyle -> {Blue, Red}] & /@ {clustersX, clustersY} // GraphicsRow


Next I tried to select the points from PairSet which correspond to a cluster. I selected the points oce for the clustering made for the X coordinates (ParticleListX) and once for the clustering of Y coordinates (ParticleListY):

ParticleListX =
Table[Select[PairSet, MemberQ[clustersX[[i]], #[[1]]] &], {i, 1,
Length[clustersX]}];

ParticleListY =
Table[Select[PairSet, MemberQ[clustersY[[i]], #[[2]]] &], {i, 1,
Length[clustersY]}];

ListPlot[#, PlotStyle -> {Blue, Red}] & /@ {ParticleListX, ParticleListY} // GraphicsRow


From the ListPlot we can already see, that the clustering worked out quite similar but some points are assigned differently. To see where the two found clusters differ, I used Union to regroup the two lists ParticleListX and ParticleListY:

AllClusters = Union[ParticleList, ParticleList2];
ListPlot[AllClusters,PlotStyle -> {Blue, Red, Green}]


You can see from the ListPlot that the points in green are not put into the same cluster when using this approach for clustering. But I hope it is a good start to improve the clustering and selection procedure.

-
If I compare your and rm-rf's plots it looks like you have some data points that @rm-rf hasn't (last part of the plot, cluster of points between the main clusters). Any idea why this is so? – Sjoerd C. de Vries Jul 30 '13 at 10:08
@SjoerdC.deVries: Thanks for the advice. I will definitely have a look at it again. – g3kk0 Jul 30 '13 at 10:34
@SjoerdC.deVries: I have checked the code again. There are no differences in the point set. However, my guess is that due to the FindClusters there seems to be some reordering of the points happening such that if I plot the points afterwards they look different. I think this is related to the logical problem mentioned by Ray Koopman. – g3kk0 Jul 30 '13 at 10:48