n-body-pairs - npm Package Compare versions

Comparing version 0.0.1 to 0.1.0

package.json

 {
   "name": "n-body-pairs",
-  "version": "0.0.1",
+  "version": "0.1.0",
   "description": "Given a collection of spheres with equal radii, find all pairwise intersections.",
@@ -5,0 +5,0 @@ "main": "pairs.js",

pairs.js

 "use strict"
 
-function allocateGrid(max_points, dimension) {
-  max_points = max_points|0
-  dimension = dimension|0
-  var grid = new Array(max_points<<dimension)
-  for(var i=0, len=grid.length; i<len; ++i) {
-    var g = new Array(dimension+1)
-    for(var j=0; j<=dimension; ++j) {
-      g[j] = 0
-    }
-    grid[i] = g
+function Storage(max_points, dimension) {
+  this.coordinates = new Array(dimension)
+  this.points = new Array(dimension)
+  for(var i=0; i<dimension; ++i) {
+    this.coordinates[i] = new Int32Array(max_points<<dimension)
+    this.points[i] = new Float64Array(max_points<<dimension)
   }
-  return grid
+  this.indices = new Int32Array(max_points<<dimension)
 }
 
-function resizeGrid(grid, max_points, dimension) {
-  if(grid.length > 0) {
-    dimension = (grid[0].length-1)|0
+Storage.prototype.resize = function(max_points) {
+  var dimension = this.coordinates.length
+  for(var i=0; i<dimension; ++i) {
+    this.coordinates[i] = new Int32Array(max_points<<dimension)
+    this.points[i] = new Float64Array(max_points<<dimension)
   }
-  var nlen = max_points<<dimension
-  if(nlen < grid.length) {
-    grid.length = nlen
-  } else {
-    var plen = grid.length
-    grid.length=nlen
-    for(var i=plen; i<nlen; ++i) {
-      var g = new Array(dimension+1)
-      for(var j=0; j<=dimension; ++j) {
-        g[j] = 0
-      }
-      grid[i] = g
-    }
+  this.indices = new Int32Array(max_points<<dimension)
+}
+
+Storage.prototype.size = function() {
+  return this.indices >> this.coordinates.length
+}
+
+Storage.prototype.move = function(p, q) {
+  var coords = this.coordinates
+    , points = this.points
+    , indices = this.indices
+    , dimension = coords.length
+    , a, b, k
+  for(k=0; k<dimension; ++k) {
+    a = coords[k]
+    a[p] = a[q]
+    b = points[k]
+    b[p] = b[q]
   }
-  return grid
+  indices[p] = indices[q]
 }
 
-function compareLex(a, b) {
-  for(var i=0, len=a.length-1; i<len; ++i) {
-    var d = a[i] - b[i]
-    if(d) { return d }
+Storage.prototype.load = function(scratch, i) {
+  var coords = this.coordinates
+    , points = this.points
+  for(var k=0, d=coords.length; k<d; ++k) {
+    scratch[k] = coords[k][i]|0
+    scratch[k+d+1] = +points[k][i]
   }
-  return 0
+  scratch[d] = this.indices[i]|0
 }
 
-function findPairs_impl(points, count, dimension, radius, cb, grid, compareFun) {
+Storage.prototype.store = function(i, scratch) {
+  var coords = this.coordinates
+    , points = this.points
+  for(var k=0, d=coords.length; k<d; ++k) {
+    coords[k][i] = scratch[k]
+    points[k][i] = scratch[k+d+1]
+  }
+  this.indices[i] = scratch[d]
+}
+
+Storage.prototype.swap = function(i, j) {
+  var coords = this.coordinates
+  var points = this.points
+  var ind = this.indices
+  var t, a, b
+  for(var k=0, d=coords.length; k<d; ++k) {
+    a = coords[k]
+    t = a[i]
+    a[i] = a[j]
+    a[j] = t
+    b = points[k]
+    t = b[i]
+    b[i] = b[j]
+    b[j] = t
+  }
+  t = ind[i]
+  ind[i] = ind[j]
+  ind[j] = t
+}
+
+Storage.prototype.compare = function(i,j) {
+  var coords = this.coordinates
+  for(var k=0, d=coords.length; k<d; ++k) {
+    var a = coords[k]
+      , s = a[i] - a[j]
+    if(s) { return s }
+  }
+  return this.indices[i] - this.indices[j]
+}
+
+Storage.prototype.compareNoId = function(i,j) {
+  var coords = this.coordinates
+  for(var k=0, d=coords.length-1; k<d; ++k) {
+    var a = coords[k]
+      , s = a[i] - a[j]
+    if(s) { return s }
+  }
+  return coords[d][i] - coords[d][j]
+}
+
+Storage.prototype.compareS = function(i, scratch) {
+  var coords = this.coordinates
+  for(var k=0, d=coords.length; k<d; ++k) {
+    var s = coords[k][i] - scratch[k]
+    if(s) { return s }
+  }
+  return this.indices[i] - scratch[d]
+}
+
+/*
+  Modified from this: http://stackoverflow.com/questions/8082425/fastest-way-to-sort-32bit-signed-integer-arrays-in-javascript
+ */
+Storage.prototype.sort = function(n) {
+  var coords = this.coordinates
+  var points = this.points
+  var indices = this.indices
+  var dimension = coords.length|0
+  var stack = []
+  var sp = -1
+  var left = 0
+  var right = n - 1
+  var i, j, k, d, swap = new Array(2*dimension+1), a, b, p, q, t
+  for(i=0; i<dimension; ++i) {
+    swap[i] = 0|0
+  }
+  swap[dimension] = 0|0
+  for(i=0; i<dimension; ++i) {
+    swap[dimension+1+i] = +0.0
+  }
+  while(true) {
+    if(right - left <= 25){
+      for(j=left+1; j<=right; j++) {
+        for(k=0; k<dimension; ++k) {
+          swap[k] = coords[k][j]|0
+          swap[k+dimension+1] = +points[k][j]
+        }
+        swap[dimension] = indices[j]|0
+        i = j-1;        
+lo_loop:
+        while(i >= left) {
+          for(k=0; k<dimension; ++k) {
+            d = coords[k][i] - swap[k]
+            if(d < 0) {
+              break lo_loop
+            } if(d > 0) {
+              break
+            }
+          }
+          p = i+1
+          q = i--
+          for(k=0; k<dimension; ++k) {
+            a = coords[k]
+            a[p] = a[q]
+            b = points[k]
+            b[p] = b[q]
+          }
+          indices[p] = indices[q]
+        }
+        this.store(i+1, swap)
+      }
+      if(sp == -1)    break;
+      right = stack[sp--];
+      left = stack[sp--];
+    } else {
+      var median = (left + right) >> 1;
+      i = left + 1;
+      j = right;
+      
+      this.swap(median, i)
+      if(this.compare(left, right) > 0) {
+        this.swap(left, right)
+      } if(this.compare(i, right) > 0) {
+        this.swap(i, right)
+      } if(this.compare(left, i) > 0) {
+        this.swap(left, i)
+      }
+      
+      this.load(swap, i)
+      while(true){
+ii_loop:
+        while(true) {
+          ++i
+          for(k=0; k<dimension; ++k) {
+            d = coords[k][i] - swap[k]
+            if(d > 0) {
+              break ii_loop
+            } if(d < 0) {
+              continue ii_loop
+            }
+          }
+          if(indices[i] >= swap[dimension]) {
+            break
+          }
+        }
+jj_loop:
+        while(true) {
+          --j
+          for(k=0; k<dimension; ++k) {
+            d = coords[k][j] - swap[k]
+            if(d < 0) {
+              break jj_loop
+            } if(d > 0) {
+              continue jj_loop
+            }
+          }
+          if(indices[j] <= swap[dimension]) {
+            break
+          }
+        }
+        if(j < i)    break;
+        for(k=0; k<dimension; ++k) {
+          a = coords[k]
+          t = a[i]
+          a[i] = a[j]
+          a[j] = t
+          b = points[k]
+          t = b[i]
+          b[i] = b[j]
+          b[j] = t
+        }
+        t = indices[i]
+        indices[i] = indices[j]
+        indices[j] = t
+      }
+      this.move(left+1, j)
+      this.store(j, swap)
+      if(right - i + 1 >= j - left){
+        stack[++sp] = i;
+        stack[++sp] = right;
+        right = j - 1;
+      }else{
+        stack[++sp] = left;
+        stack[++sp] = j - 1;
+        left = i;
+      }
+    }
+  }
+}
+
+Storage.prototype.hashPoints = function(points, bucketSize, radius) {
   var floor = Math.floor
-    , dbits = 1<<dimension
+    , coords = this.coordinates
+    , spoints = this.points
+    , indices = this.indices
+    , count = points.length|0
+    , dimension = coords.length|0
+    , dbits = (1<<dimension)|0
     , ptr = 0
   for(var i=0; i<count; ++i) {
-    var c = grid[ptr++]
+    var t = ptr
       , p = points[i]
+      , cross = 0
     for(var j=0; j<dimension; ++j) {
-      c[j] = floor(p[j]/radius)|0
+      var ix = floor(p[j]/bucketSize)
+      coords[j][ptr] = ix
+      spoints[j][ptr] = p[j]
+      if(bucketSize*(ix+1) <= p[j]+2*radius) {
+        cross += (1<<j)
+      }
     }
-    c[dimension]=i
+    indices[ptr++] = i
+    cross = ~cross
     for(var j=1; j<dbits; ++j) {
-      var g = grid[ptr++]
+      if(j & cross) {
+        continue
+      }
       for(var k=0; k<dimension; ++k) {
-        g[k] = (c[k]+((j>>>k)&1))|0
+        var c = coords[k]
+        c[ptr] = c[t]+((j>>>k)&1)
+        spoints[k][ptr] = p[k]
       }
-      g[dimension]=i
+      indices[ptr++] = i
     }
   }
-  grid.sort(compareFun)
-  var r2 = radius * radius
-  for(var i=0, len=grid.length; i<len; ++i) {
-    var cs = grid[i]
-    var j=i
-j_loop:
-    while(++j < len) {
-      var as = grid[j]
-      for(var k=0; k<dimension; ++k) {
-        if(as[k] !== cs[k]) {
-          break j_loop
-        }
+  return ptr
+}
+
+Storage.prototype.computePairs = function(cellCount, bucketSize, radius, cb) {
+  var floor = Math.floor
+    , coords = this.coordinates
+    , points = this.points
+    , indices = this.indices
+    , dimension = coords.length|0
+    , ptr = 0
+    , r2 = 4 * radius * radius
+    , i, j, k, l
+    , a, b, pa, pb, d, d2, ac, bc
+  for(i=0; i<cellCount;) {
+    for(j=i+1; j<cellCount; ++j) {
+      if(this.compareNoId(i, j) !== 0) {
+        break
       }
-      var a = as[dimension]
-      var pa = points[a]
+      a = indices[j]
 k_loop:
-      for(var k=i; k<j; ++k) {
-        var b = grid[k][dimension]
-        //Check if the coordinate is lexicographically first intersection
-        var pb = points[b]
-        var d2 = 0.0
-        for(var l=0; l<dimension; ++l) {
-          var ac = pa[l]
-          var bc = pb[l]
-          var d = ac - bc
-          if(d >= 0) {
-            if(cs[l] !== (floor(pa[l]/radius)|0)) {
+      for(k=i; k<j; ++k) {
+        b = indices[k]
+        d2 = 0.0
+        for(l=0; l<dimension; ++l) {
+          ac = points[l][j]
+          bc = points[l][k]
+          if(ac > bc) {
+            if(coords[l][i] !== floor(ac/bucketSize)) {
               continue k_loop
             }
-          } else if(cs[l] !== (floor(pb[l]/radius)|0)) {
+          } else if(coords[l][i] !== floor(bc/bucketSize)) {
             continue k_loop
           }
+          d = ac - bc
           d2 += d * d
-        }
-        //Then check if l2 bound holds
-        if(d2 <= r2) {
-          if(cb(a, b, d2)) {
-            return
+          if(d2 > r2) {
+            continue k_loop
           }
         }
+        if(cb(a, b, d2)) {
+          return
+        }
       }
@@ -111,18 +323,31 @@ }
 
-function findPairs(points, radius, cb, grid) {
-  if(points.length === 0) {
-    return
+function createNBodyDataStructure(dimension, num_points) {
+  dimension = (dimension|0) || 2
+  var grid = new Storage(num_points||1024, dimension)
+  
+  function findPairs(points, radius, cb) {
+    var count = points.length|0
+    var cellCount = count<<dimension
+    if(grid.size() < cellCount) {
+      grid.resize(count)
+    }
+    var bucketSize = 4*radius
+    var nc = grid.hashPoints(points, bucketSize, radius)
+    grid.sort(nc)
+    grid.computePairs(nc, bucketSize, radius, cb)
   }
-  var count = points.length|0
-  var dimension = points[0].length|0
-  if(!grid) {
-    grid = allocateGrid(count, dimension)
-  } else if(grid.length < (count<<dimension)) {
-    reserveGrid(grid, count, dimension)
-  }
-  findPairs_impl(points, count, dimension, radius, cb, grid, compareLex)
+  
+  Object.defineProperty(findPairs, "capacity", {
+    get: function() {
+      return grid.size()
+    },
+    set: function(n_capacity) {
+      grid.resize(n_points)
+      return grid.size()
+    }
+  })
+  
+  return findPairs
 }
 
-module.exports = findPairs
-module.exports.allocateStorage = allocateGrid
-module.exports.resizeStorage = resizeGrid
+module.exports = createNBodyDataStructure

README.md

@@ -14,4 +14,4 @@ n-body-pairs
 ```javascript
-//Load the library
-var nbp = require("n-body-pairs")
+//Load the library, allocate initial data structure for searching in 3-dimensions with initial reserve capacity of 1000 points
+var nbp = require("n-body-pairs")(3, 1000)
 
@@ -27,4 +27,4 @@ //Create some points
 
-//Report all pairs of points which are within 1.1 units of eachother
-nbp(points, 1.1, function(i,j,d2) {
+//Report all pairs of points which are within 0.6 units of eachother
+nbp(points, 0.6, function(i,j,d2) {
     console.log("Overlap ("+i+","+j+") Distance=", Math.sqrt(d2), "Positions=", points[i], points[j])
@@ -41,5 +41,13 @@ })
 
-### `nbp(points, radius, callback(a,b,d2)[, storage])`
-Computes all pairwise overlaps
+### `var nbp = require("n-body-pairs")(dimension, capacity)`
+Allocates a data structure for performing n-body neighborhood queries.
 
+* `dimension` is the dimension of the space to search in (default 2)
+* `capacity` is the initial size of the data structure to reserve (default 1000)
+
+**Storage Complexity:** `O(capacity * 2^dimension)`
+
+### `nbp(points, radius, callback(a,b,d2))`
+Computes all pairwise overlaps.  If the data structure does not have sufficient capacity, it is resized.
+
 * `points` is an array of points
@@ -51,40 +59,10 @@ * `radius` is the radius of the overlap query
     + `d2` squared distance between `a` and `b`
-* `storage` an optional storage data structure, created using allocateStorage.  If not specified, it is created upon running the algorithm.
 
 **Time Complexity:** `O(points.length * dimension * 2^dimension * log(points.length) + number of intersections)`
 
-**Space Complexity:** Size of storage is `O(points.length * 2^dimension)`
+### `nbp.capacity`
+Returns the size of the data structure (set to 0 to free memory.  Set to change the reserve capacity of the data structure.
 
-## Storage
-To avoid reallocating the array, you can preallocate storage for the data structure.  Here is an example of how to do this:
-
-```javascript
-var nbp = require("n-body-pairs")
-
-//Reserve storage for 1000 points in 2D
-var storage = nbp.allocateStorage(1000, 2)
-
-//Now call library as usual, but pass storage as extra argument:
-nbp([[1, 0, 0],[0,0,1]], 1.0, function(i,j,d2) {},  storage)
-```
-
-This avoids reallocating the intermediate arrays needed to solve for collisions
-
-### `nbp.allocateStorage(max_points, dimension)`
-Reserves space for an intermediate storage data structure
-
-* `max_points` is the initial capacity of the storage
-* `dimension` is the dimension of the point set
-
-**Returns:** A new storage object for resolving the overlap queries
-
-### `nbp.resizeStorage(storage, max_points, dimension)`
-Resizes the storage data structure
-
-* `storage` is the data structure to resize
-* `max_points` is the new capacity of the storage
-* `dimension` is the dimension of the point set
-
 Credits
 =======
 (c) 2013 Mikola Lysenko. BSD License

test/test.js

@@ -1,2 +0,2 @@
-var nbp = require("../pairs.js")
+var initNBP = require("../pairs.js")
 
@@ -13,6 +13,8 @@ require("tap").test("n-body-pairs", function(t) {
   ]
+  
+  var nbp = initNBP(3)
 
   //Report all pairs of points which are within 1.5 units of eachother
   var pairs = []
-  nbp(points, 1.1, function(i,j,d2) {
+  nbp(points, 0.7, function(i,j,d2) {
     console.log("Overlap ("+i+","+j+") Distance=", Math.sqrt(d2), "Positions=", points[i], points[j])
@@ -19,0 +21,0 @@ pairs.push([Math.min(i,j), Math.max(i,j)])

New alerts

License Policy Violation

License

This package is not allowed per your license policy. Review the package's license to ensure compliance.

Found 1 instance in 1 package

Major refactor

Supply chain risk

Package has recently undergone a major refactor. It may be unstable or indicate significant internal changes. Use caution when updating to versions that include significant changes.

Found 1 instance in 1 package

Fixed alerts

License Policy Violation

License

This package is not allowed per your license policy. Review the package's license to ensure compliance.

Found 1 instance in 1 package

Improved metrics

Total package byte prevSize

12191

increased by69.3%

Lines of code

353

increased by152.14%

Worsened metrics

Number of lines in readme file

65

decreased by-25.29%

Number of medium supply chain risk alerts

1

increased byInfinity%

No dependency changes