add radius searching to kdtree example (#87)

flucoma · Nov 27, 2021 · 340e5d0 · 340e5d0
1 parent a71bb77
commit 340e5d0
Show file tree

Hide file tree

Showing 2 changed files with 45 additions and 18 deletions.
diff --git a/src/lib/widget/KDTree.svelte b/src/lib/widget/KDTree.svelte
@@ -5,7 +5,7 @@
 
  <script lang='ts'>
     import { onMount } from 'svelte';
-    import { CanvasSpace, Create, GroupLike } from 'pts';
+    import { CanvasSpace, Create, GroupLike, Circle } from 'pts';
     import Slider from '$lib/components/Slider.svelte';
     import Button from '$lib/components/Button.svelte';
 
@@ -16,6 +16,7 @@
     let numNeighbours: number = 1;
     let fit: boolean = false;
     let rect;
+    let radius: number = 0.0;
 
     function getMousePos(canvas, evt) {
         // We need to do this manually otherwise when shifting the window the resize is not accounted for.
@@ -26,10 +27,15 @@
         ]
     }
 
-    onMount(async() => {      
-        let space = new CanvasSpace('#sketch')
+    onMount(async() => {    
+        
+        // const module = await import('static-kdtree');
+		// const KDTree = module.default;
+        // console.log(KDTree)
+        let space = new CanvasSpace('#sketch');
+        let darkBlue = 'rgba(8, 60, 100,0.5)';
         space.setup({ 
-            bgcolor: '#e8e4ec',
+            bgcolor: 'rgba(28,164,252,0.01)',
             resize: true
         });
 
@@ -41,21 +47,30 @@
                 pts = Create.distributeRandom( space.innerBound, 120 );
             },
             animate: (time, ftime, space) => {
-
+                // if (radius > 0.0) {
+                let circle: GroupLike = Circle.fromCenter( space.pointer, radius * space.size.y)
+                form.fillOnly(darkBlue).circle( circle );
+                // }
                 if (fit) {
                     form.fillOnly("#123").points( pts, 3, "circle" );
+                    
                     pts.sort((a, b) => a.$subtract(mouse).magnitude() - b.$subtract(mouse).magnitude())
 
-                    // Draw lines from mouse to points
-                    for (let j=0; j < numNeighbours; j++) {
-                        form.strokeOnly('#0d47a1', 2).line( [ pts[j], mouse ] );
-                    }
-
-                    // Draw bigger circles on top of points
+                    // Draw bigger on top of points
                     for (let i=0; i < numNeighbours; i++) {
-                        form.fill("#f03").point( pts[i], 7, "square" );
+                        form.strokeOnly('#0d47a1', 2).line( [ pts[i], mouse ] );
+
+                        if (radius > 0.0) {
+                            if (Circle.withinBound( circle, pts[i] )) {
+                                form.fill("#f03").point( pts[i], 7, "square" );
+                            }
+                        }
+                        else {
+                            form.fill("#f03").point( pts[i], 7, "square" );
+                        }
                     }
-                } else {
+                } 
+                else {
                     form.fillOnly("#787878").points( pts, 3, "circle" );
                 }
             },
@@ -73,7 +88,8 @@
 
 <div class="controls">
     <Button on:click={ () => fit = true } label='Fit' />
-    <Slider bind:value={numNeighbours} min={1} max={15} title='Number of Neighbours' step={1} />
+    <Slider bind:value={numNeighbours} min={1} max={50} title='Number of Neighbours' step={1} />
+    <Slider bind:value={radius} min={0.0} max={1.0} title='Radius' step={0.01} />
 </div>
 
 <style>

diff --git a/src/routes/reference/kdtree.svx b/src/routes/reference/kdtree.svx
@@ -10,12 +10,23 @@ tags:
     import KDTree from '$lib/widget/KDTree.svelte';
 </script>
 
-The [KDTree](/reference/kdtree) facilitates the rapid querying of data stored in a [FluidDataSet](/reference/dataset). It makes querying by distance much more efficient by first analysing a [FluidDataSet](/reference/dataset) and creating a data structure known as a _k_-d tree. As such, before the [KDTree](/reference/kdtree) can be used you have to `fit` a [FluidDataSet](/reference/dataset). After this, the tree can be quered by calling `knearest <buffer>` and providing the name of a buffer containing data.
+The [KDTree](/reference/kdtree) facilitates the rapid querying of data stored in a [FluidDataSet](/reference/dataset). It makes querying by distance much more efficient by first analysing a [FluidDataSet](/reference/dataset) and creating a data structure known as a _k_-d tree. As such, before the [KDTree](/reference/kdtree) can be used you have to `fit` a [FluidDataSet](/reference/dataset). This constructs the tree that can then be queried.
 
-A common application of the [KDTree](/reference/kdtree) is for performing rapid nearest neighbour lookups. The interactive example below contains a collection of data points ranging between 0.0 and 1.0 which are then plotted on to a canvas like a scatterplot. Using the coordinates of our mouse in the square, we can search for the point, or group of poitns which are closest to our mouse.
-
-Before you use the example you will have to `fit` the underlying [KDTree](/reference/kdtree) by pressing the button labelled _fit_. You can change how many nearest neighbours you query for with the range slider at the bottom.
+A common application of the [KDTree](/reference/kdtree) is for performing _nearest neighbour lookups_. The interactive example below contains a collection of data points ranging between 0.0 and 1.0 which are then plotted on to a canvas like a scatterplot. Using the coordinates of our mouse in the square, we can search for the point, or group of points closest to our mouse. We can also control the radius constraints of the search, meaning only points within a certain distance, and not just whatever is closest, are returned. Before you use the example you will have to `fit` the underlying [KDTree](/reference/kdtree) by pressing the button labelled _fit_. 
 
 <KDTree />
 
+You can change the number of neighbours and the radius constraint with the sliders at the bottom. Points that are highlighted with a red square are those that are deemed to be the nearest neighbours, given both the number of neighbours and radius constraint. Even if points fall outside the radius, a line will be drawn to them. Notice how working with both constraints can help you to hone in on different neighbourhoods of points. For example, by using a large number of neighbours (50) and a small radius (0.1) you can ensure that if there are actually 50 very nearby points they will be returned, but only if they are within a tight proximity to the query (your mouse).
+
+<!-- ## Musical Motivations
+The _k_-d tree can is useful towards a number of different musical applications. Namely, it is a way of employing the computer to perform comparisons of similarity between data, that may or may not be associated to sound files, synthesiser parameters or anything musically useful. -->
+
+
+
+
+
+
+
+
+
 <!-- TODO: Tutorial on YouTube which uses a KDTREE to perform multi-dimensional searching for nearest neighbours in a descriptor dataset. -->