SuperCollider CLASSES (extension)

NearestN
ExtensionExtension

Find the nearest-neighbours in a set of points

Description

This UGen takes an input point (such as a 2D or 3D location) and searches for the nearest few points in a dataset (by Euclidean distance).

You need the KDTree quark to generate the data for this UGen.

Class Methods

*kr (treebuf, in, gate: 1, num: 1)

Arguments:

treebuf

a Buffer containing data which MUST be in the special format created using the KDTree class and NearestN.makeBufferData

in

An array representing the input point. Num channels must match the dimensionality of the points in the dataset

gate

The unit is active while gate > 0. While <=0, no search is performed and output is held steady

num

Number of points to retrieve. NOT modulatable.

Returns:

A flat array containing (3 * num) channels, which is a ranked list of the nearest items (the very nearest coming first). For each match, this returns three channels [treeindex, distancesquared, label]

*makeBufferData (tree)

Processes a KDTree into a special format that can be loaded into a Buffer, and then searched by this UGen.

Inherited class methods

Instance Methods

Inherited instance methods

Examples

The most basic workflow is something like this:

// Find/make a dataset of points:
x = 15.collect{[1.0.rand, 1.0.rand]};
// Append the index onto the end, for later reference
x = x.collect{|data, i| data ++ i };
// Use the KDTree quark and the .makeBufferData method to put the data in the searchable format
~treedata = NearestN.makeBufferData(KDTree(x, lastIsLabel: true));
// Load the data to the server
~treebuf = Buffer.sendCollection(s, ~treedata.flat, 5);
// Run a synth with the ugen and some kind of query data
~synth = { NearestN.kr(~treebuf, {LFNoise0.kr(1)}.dup, num:3).poll(1)}.play;
~synth.free

This more complete example shows it in action:

(
s.waitForBoot{
(
x = 15.collect{|i| [1.0.rand, 1.0.rand, i]};
~treedata = NearestN.makeBufferData(KDTree(x, lastIsLabel: true));
~size = 800;
~treebuf = Buffer.sendCollection(s, ~treedata.flat, 5);
~foundbus = Bus.control(s, 3);
~mousebus = Bus.control(s, 2);
// lang-side cache of values which we'll poll from the server:
~mousepos = [0.5,0.5];
~nearests = [0,1,2];
);

(
w = Window.new("points of proximity", Rect(100, 100, ~size, ~size)).front;
w.drawHook = {
    var thesize, y;
    Pen.color = Color.white;
    Pen.fillRect(Rect(0, 0, ~size, ~size));
    x.do{|ax, index|
        y = 1 - ax[1]; // y is flipped for drawing
        Pen.color = Color.blue.alpha_(0.6);
        switch(~nearests.indexOf(index),
            0, { Pen.fillOval(Rect(ax[0] * ~size - 10, y * ~size - 10, 20, 20)) },
            1, { Pen.fillOval(Rect(ax[0] * ~size - 8, y * ~size - 8, 16, 16))   },
            2, { Pen.fillOval(Rect(ax[0] * ~size - 5, y * ~size - 5, 10, 10))   }
        );
        Pen.color = Color.black;
        Pen.fillOval(Rect(ax[0] * ~size - 2, y * ~size - 2, 4, 4));
        Pen.stringAtPoint(index.asString, ax[0] @ y * ~size, Font.default, Color.black);
    };
    Pen.color = Color.green.alpha_(0.5);
    Pen.fillOval(Rect(~mousepos[0] * ~size - 7, (1.0-~mousepos[1]) * ~size - 7, 14, 14));
};
);

s.sync;

(
~synth = {
    var mouse = Latch.kr([MouseX.kr, MouseY.kr], Impulse.kr(10));
    var found = NearestN.kr(~treebuf, mouse, num:3);
    //found.poll(1);
    var findices = found[2,5..]; // original array index, stored as 'labels'
    var fdistsq = found[1,4..]; // distances
    Out.kr(~foundbus, findices);
    Out.kr(~mousebus, mouse);
    Out.ar(0, SinOsc.ar((findices * 2 + 60).midicps, 0, fdistsq.explin(1e-6, 1, 0.5, 0)).sum);
}.play;

~updater = Task{loop{
    ~foundbus.getn(3, {|data| ~nearests = data.asInt});
    ~mousebus.getn(2, {|data| ~mousepos = data});
    s.sync;
    defer{w.refresh};
    0.1.wait;
}}.play
)

}

)