Calculate the centroids for a grid controller

Questions
#1

I’m trying to figure out how to calculate the x and y centroids to be able to use my Manta as a 2D controller, combining the currently held pads. Searching around, i see integration formulas and stuff and my math skills are unfortunately not there to understand how to implement those in sc. Any help on how to solve this is highly appreciated!

My Manta has a 6x8 grid of touch sensitive pads and I have written a class that stores all my pad values between 0-1 in a 2D array so i’m getting something like this:

[ 
   [ 0, 0, 0, 0, 0, 0.56498826028397, 0, 0 ], 
   [ 0.45307553537759, 0, 0, 0, 0, 0, 0, 0 ], 
   [ 0, 0.017162084842514, 0.018331095896545, 0, 0, 0, 0, 0 ], 
   [ 0, 0.60755015816675, 0.47020854015963, 0.82371384159056, 0, 0, 0, 0 ], 
   [ 0, 0, 0, 0, 0, 0, 0, 0 ], 
   [ 0, 0, 0, 0, 0, 0, 0, 0 ] 
];

So, given this, how do i calculate the centroid for x and y?

#2

I think this is right…

a = [ 
   [ 0, 0, 0, 0, 0, 0.56498826028397, 0, 0 ], 
   [ 0.45307553537759, 0, 0, 0, 0, 0, 0, 0 ], 
   [ 0, 0.017162084842514, 0.018331095896545, 0, 0, 0, 0, 0 ], 
   [ 0, 0.60755015816675, 0.47020854015963, 0.82371384159056, 0, 0, 0, 0 ], 
   [ 0, 0, 0, 0, 0, 0, 0, 0 ], 
   [ 0, 0, 0, 0, 0, 0, 0, 0 ] 
];

~centroidOfArray = {|a, width, height| 
	var weighted = a.flat.collect({ |v, i|
		v * [i.mod(width), i.div(height) ]
	});
	(a.flat.sum == 0).if(
		{ nil },
		{ weighted.sum / a.flat.sum }
	);
}
~centroidOfArray.(a, 6, 8)
#3

Thanks! But if i set the “corners” to 1 like this:

a = [ 
   [ 1, 0, 0, 0, 0, 0, 0, 1 ], 
   [ 0, 0, 0, 0, 0, 0, 0, 0 ], 
   [ 0, 0, 0, 0, 0, 0, 0, 0 ], 
   [ 0, 0, 0, 0, 0, 0, 0, 0 ], 
   [ 0, 0, 0, 0, 0, 0, 0, 0 ], 
   [ 1, 0, 0, 0, 0, 0, 0, 1 ] 
];

Shouldn’t the result be [0.5, 0.5]? Now it’s [2.5, 2.5].

#4

oops, typo

~centroidOfArray = {|a, width, height| 
	var weighted = a.flat.collect({ |v, i|
		v * [i.mod(width), i.div(width) ]
	});
	(a.flat.sum == 0).if(
		{ nil },
		{ (weighted.sum / a.flat.sum) / [width - 1, height - 1] } // this change normalises the output between 0 and 1 rather than between width and height
	);
};
1 Like
#5

At one point the Manta sent the centroid as a data point…but that was a while ago.

Sam

#6

Doesn’t this represent a 3D space?

#7

I actually asked Jeff about that and he said it was implemented in the Max object. I checked the C++ code for that, but i’m as bad at that as i am with math i’m afraid. :wink:

#8

Great! Seems to work. Thanks a lot!

#9

It works, but it’s slow:

(
~centroidOfArray = {|a, width, height| 
	var weighted = a.flat.collect({ |v, i|
		v * [i.mod(width), i.div(width) ]
	});
	(a.flat.sum == 0).if(
		{ nil },
		{ (weighted.sum / a.flat.sum) / [width - 1, height - 1] } // this change normalises the output between 0 and 1 rather than between width and height
	);
};

~fasterCentroid = { |a|
	var width = a.maxValue { |row| row.size };
	var height = a.size;
	var xsum = 0, ysum = 0, sum = 0;
	
	a.do { |row, y|
		row.do { |item, x|
			sum = sum + item;
			xsum = xsum + (item * x);
			ysum = ysum + (item * y);
		};
	};
	
	if(sum == 0) {
		nil
	} {
		[xsum / sum / max(1, width - 1), ysum / sum / max(1, height - 1)]
	}
};

a = Array.fill(10, { Array.fill(10, { 1.0.rand }) });

~centroidOfArray.(a, 10, 10).postln;
~fasterCentroid.(a).postln;

bench { 2000.do { ~centroidOfArray.(a, 10, 10) } };
bench { 2000.do { ~fasterCentroid.(a) } };
)

[ 0.47755483779819, 0.53409270372467 ]
[ 0.47755483779819, 0.53409270372467 ]  // <<-- equal results

time to run: 0.58395168300001 seconds.
time to run: 0.021130881999994 seconds.  // <<-- but 27x faster

Knuth famously said “premature optimization is the root of evil” but in this case, old-school looping so vastly outperforms the allocation of multiple temporary arrays that I think it’s worth it to write out the loops.

hjh

3 Likes
#10

That’s even better! Thank you, James.

#11

Very nice. And yes, functional programs do need a kind of “listlessness” to go fast…

https://dl.acm.org/doi/pdf/10.1145/800055.802020

This one seems a little faster still, and is even more Fortran like! (Is it faster because of the single letter variables names?)

var c = { | a, w, h |
	var t = 0, x = 0, y = 0;
	(0 .. h - 1).do { | j |
		(0 .. w - 1).do { | i |
			var e = a[j][i];
			t = t + e;
			x = x + (e * i);
			y = y + (e * j)
		}
	};
	[x / t / (w - 1), y / t / (h - 1)]
}
#12

No.

Actually that’s a bit strange finding; both Number:forSeries and ArrayedCollection:do use special bytecodes for speed.

hjh

#13

I’m not familiar with this centroid calculation. Shouldn’t this be based on a position in 3D space?

#14

You could, if you like, imagine a 3d space where x has “width” items, y has “height” items, and z has 1 item – that is, defining a (trivial) 3d space. Now the centroid will be x = the average weighted according to x coordinates, y = the average weighted according to y coordinates, and z = the average weighted according to z coordinates.

z has only one possible coordinate value = 0; therefore the only possible z value in this 3d centroid is 0. Because the value can be predicted in advance, there’s no need to waste CPU time to calculate it.

Therefore a 2d centroid calculation is completely valid provided there is only one plane of data being considered, and the supposed 3d requirement is illusory.

hjh

#15

But in this case shouldn’t I take this array that is given as a 2D array with points in the 2D array having a z value, so it’s a 10x10x10 array in 3D space? Like a top down plan view.

It seems the solution is using the values in the array as scaling factors of the 2D positions instead.

#16

The centroid calculates the x, y etc coordinates representing a center of mass.

It’s a weighted average.

Because the desired result consists of coordinates, the values being averaged are the coordinates: 0, 1, 2, 3 … n-1.

The weights are the data values.

If you have a two-dimensional array, then you have coordinates (indices) in two dimensions, and each coordinate pair points to a weight.

It may be counterintuitive at first to think of averaging the coordinate values, with weights, but it is a correct definition and produces the right result.

At this point, I’m out of time on this thread.

hjh

#17

:slight_smile:
A few search engine queries later:
I was thinking the values were z coordinates, but they’re weights instead. The centroid is where the turning moment is equal to all the other moments in the mass. So it’s sum(xhat * w) = sum(x * w) → xhat=sum(x * w)/sum(w).

#18

The other (possibly better?) version of this calculation would find local maxima (with sub-cell interpolation) for the cells based on weight. Imagining the 2-d version of this, you might have:

a = [0.0, 0.1, 0.3, 0.01, 0.0, 0.2, 0.7, 0.9, 0.4, 0.1, 0.0]

If you do some interpolation / curve fitting, you’ve got a peak between index=6 and 7, which could be your best choice for locating a primary touch. In particular, this way of calculating would throw away (or track separately) the other less prominent peak at ~2. If you’re JUST doing the weighted averaging we’re talking about, then the extra touch at 2 will actually pull the overall centroid left, which may be desired or may be annoying, depending on your controller and the kind of control you’re going for.

Obviously, the above would need to be calculated in 2d not 1d - I don’t know of anything existing in SC or MathLib that can do this unfortunately.

1 Like
#19

One central tendency in n-dimensional Euclidean space that’s more robust to outliers is the geometric median:

Computing it isn’t trivial, but there are efficient algorithms for it. (I’m not sure if this is actually helpful in interface design, but nerdy math trivia is fun.)