After making my new smart fabric, I’m successfully turning leather into a touch panel. So right now I can get the raw data and translate them into my point matrix!

According to unknown confidentiality agreement, I better not put any picture here. I would just talk about real-time k-means algorithm for 2 dimension points.

And here is the problem: every time you touch the fabric, it light up 1 to 9 point in my matrix. For one finger it’s totally fine, but for multi-touch, I need to figure out where exactly my fingers are. To do this, I need to assign every point to it’s finger. Here I need clustering analysis, I choose k-means clustering algorithm (wiki).

Let’s code it in JavaScript! Here is the tutorial I found.

Here is the quick explanation: 1. Randomly assign a position of each finger.
2. Assign every point to it’s closest finger position.
3. Change position of finger to the centroid of each group.
4. Repeat step 2 and 3 until the position stop change.

But K-means is not a high efficiency algorithm, there’s a lot of calculating. In the original algorithm, if there’s any group have not point inside, it’ll get a new randomly position. But here we’re trying to detect fingers, the position is predictable. I set default positions into different corners, so in most cases, the calculating loop would stop within 2 times. (Notice:  for real time calculating, if your computer is not fast enough or your matrix is too large, this might be a bad solution.)

```function kmeans(comingPoints) {
data = comingPoints;
dataExtremes = getDataExtremes(data);
dataRange = getDataRanges(dataExtremes);

run();
}
```

Create a function and call it every time I receive new data;

```function makeAssignments() {
assignments = [];
for (var i in data)
{
var OnePoint = data[i];
var distances = [];

for (var j=0; j<kPoints;j++)
{
var mean = means[j];
var sum = 0;

for (var dimension in OnePoint)
{
var difference = OnePoint[dimension] - mean[dimension];
difference *= difference;
sum += difference;
}
distances[j] = Math.sqrt(sum);
}
assignments[i] = distances.indexOf( Math.min.apply(null, distances) );///return closest mean point index
}

}
```

In this function, assign every point into a group.

```function moveMeans() {

makeAssignments();
var sums = [];
var counts = [];
var moved = false;

for (var j=0; j<kPoints; j++)
{
counts[j] = 0;
sums[j] = [];
for (var i=0; i<2; i++)
{
sums[j][i] = 0;
}
}

for (var point_index in assignments)
{
var mean_index = assignments[point_index];
var OnePoint = data[point_index];
var mean = means[mean_index];

counts[mean_index]++;

for (var i=0; i<2; i++){
sums[mean_index][i] += OnePoint[i];
}
}

for (var i=0; i<kPoints; i++)
{
if ( 0 === counts[i] ) {
sums[i]= defaultMeans[i]; //If it didn't have any points assigned to it, give it a new position in the conner.
continue;
}

for (var dimension=0 ; dimension<2; dimension++)
{
sums[i][dimension] /= counts[i];
}
}

if (means.toString() !== sums.toString())
{
moved = true; //if centroid stop changing, stop loop
}
means = sums;

return moved;
}
```

Here we calculating centroid of each group and loop until stop changing.

```function run() {

var moved = moveMeans();

if (moved)
{
setTimeout(run,1);
}
else
{
//send result here
waitForCalculating = false; //allow new calculating loop start
}
}
```

Run() function checks to see if the algorithm has stopped. Here Arduino sends data every 100ms, call kmeans() function before last calculating finished would cause error or wrong result. So here I create a boolean variable to prevent that.