snap-points-2d - npm Package Compare versions

Comparing version 1.0.1 to 2.0.0

bench/bench-dfs.js

+var gaussRandom = require('gauss-random')
+var snapPoints = require('../snap-dfs')
+
+var NUM_POINTS = (process.argv[2])|0
+
+console.log('building qt for', NUM_POINTS, 'points')
+
+var points  = new Float32Array(2*NUM_POINTS)
+var levelQT = new Float32Array(2*NUM_POINTS)
+var ids     = new Int32Array(NUM_POINTS)
+
+for(var i=0; i<2*NUM_POINTS; ++i) {
+  points[i] = gaussRandom()
+}
+
+var timeStart = Date.now()
+var levels = snapPoints(points, ids)
+console.log(Date.now() - timeStart)
+console.log(levels)

bench/bench-evil.js

+var gaussRandom = require('gauss-random')
+var snapPoints = require('../snap-dfs')
+
+var NUM_POINTS = (process.argv[2])|0
+
+console.log('building qt for', NUM_POINTS, 'points')
+
+var points  = new Float32Array(2*NUM_POINTS)
+var levelQT = new Float32Array(2*NUM_POINTS)
+var ids     = new Int32Array(NUM_POINTS)
+
+for(var i=0; i<2*NUM_POINTS; ++i) {
+  points[i] = i * Math.pow(2,-1024)
+}
+
+var timeStart = Date.now()
+var levels = snapPoints(points, levelQT, ids)
+console.log(Date.now() - timeStart)
+
+console.log(levels)

bench/bench.js

+var gaussRandom = require('gauss-random')
+var snapPoints = require('../snap')
+
+var NUM_POINTS = (process.argv[2])|0
+
+console.log('building qt for', NUM_POINTS, 'points')
+
+var points  = new Float32Array(2*NUM_POINTS)
+var levelQT = new Float32Array(2*NUM_POINTS)
+var ids     = new Int32Array(NUM_POINTS)
+
+for(var i=0; i<2*NUM_POINTS; ++i) {
+  points[i] = gaussRandom()
+}
+
+var timeStart = Date.now()
+var levels = snapPoints(points, levelQT, ids)
+console.log(Date.now() - timeStart)
+
+console.log(levels)

lib/sort.js

+'use strict'
+
+module.exports = sortLevels
+
+var INSERT_SORT_CUTOFF = 32
+
+function sortLevels(data_levels, data_points, data_ids, n0) {
+  if (n0 <= 4*INSERT_SORT_CUTOFF) {
+    insertionSort(0, n0 - 1, data_levels, data_points, data_ids)
+  } else {
+    quickSort(0, n0 - 1, data_levels, data_points, data_ids)
+  }
+}
+
+function insertionSort(left, right, data_levels, data_points, data_ids) {
+  for(var i=left+1; i<=right; ++i) {
+    var a_level = data_levels[i]
+    var a_x     = data_points[2*i]
+    var a_y     = data_points[2*i+1]
+    var a_id    = data_ids[i]
+
+    var j = i
+    while(j > left) {
+      var b_level = data_levels[j-1]
+      var b_x     = data_points[2*(j-1)]
+      if(((b_level - a_level) || (a_x - b_x)) >= 0) {
+        break
+      }
+      data_levels[j]      = b_level
+      data_points[2*j]    = b_x
+      data_points[2*j+1]  = data_points[2*j-1]
+      data_ids[j]         = data_ids[j-1]
+      j -= 1
+    }
+
+    data_levels[j]     = a_level
+    data_points[2*j]   = a_x
+    data_points[2*j+1] = a_y
+    data_ids[j]        = a_id
+  }
+}
+
+function swap(i, j, data_levels, data_points, data_ids) {
+  var a_level = data_levels[i]
+  var a_x     = data_points[2*i]
+  var a_y     = data_points[2*i+1]
+  var a_id    = data_ids[i]
+
+  data_levels[i]     = data_levels[j]
+  data_points[2*i]   = data_points[2*j]
+  data_points[2*i+1] = data_points[2*j+1]
+  data_ids[i]        = data_ids[j]
+
+  data_levels[j]     = a_level
+  data_points[2*j]   = a_x
+  data_points[2*j+1] = a_y
+  data_ids[j]        = a_id
+}
+
+function move(i, j, data_levels, data_points, data_ids) {
+  data_levels[i]     = data_levels[j]
+  data_points[2*i]   = data_points[2*j]
+  data_points[2*i+1] = data_points[2*j+1]
+  data_ids[i]        = data_ids[j]
+}
+
+function rotate(i, j, k, data_levels, data_points, data_ids) {
+  var a_level = data_levels[i]
+  var a_x     = data_points[2*i]
+  var a_y     = data_points[2*i+1]
+  var a_id    = data_ids[i]
+
+  data_levels[i]     = data_levels[j]
+  data_points[2*i]   = data_points[2*j]
+  data_points[2*i+1] = data_points[2*j+1]
+  data_ids[i]        = data_ids[j]
+
+  data_levels[j]     = data_levels[k]
+  data_points[2*j]   = data_points[2*k]
+  data_points[2*j+1] = data_points[2*k+1]
+  data_ids[j]        = data_ids[k]
+
+  data_levels[k]     = a_level
+  data_points[2*k]   = a_x
+  data_points[2*k+1] = a_y
+  data_ids[k]        = a_id
+}
+
+function shufflePivot(
+  i, j,
+  a_level, a_x, a_y, a_id,
+  data_levels, data_points, data_ids) {
+
+  data_levels[i]     = data_levels[j]
+  data_points[2*i]   = data_points[2*j]
+  data_points[2*i+1] = data_points[2*j+1]
+  data_ids[i]        = data_ids[j]
+
+  data_levels[j]     = a_level
+  data_points[2*j]   = a_x
+  data_points[2*j+1] = a_y
+  data_ids[j]        = a_id
+}
+
+function compare(i, j, data_levels, data_points, data_ids) {
+  return ((data_levels[i] - data_levels[j]) ||
+          (data_points[2*j] - data_points[2*i]) ||
+          (data_ids[i] - data_ids[j])) < 0
+}
+
+function comparePivot(i, level, x, y, id, data_levels, data_points, data_ids) {
+  return ((level - data_levels[i]) ||
+          (data_points[2*i] - x) ||
+          (id - data_ids[i])) < 0
+}
+
+function quickSort(left, right, data_levels, data_points, data_ids) {
+  var sixth = (right - left + 1) / 6 | 0,
+      index1 = left + sixth,
+      index5 = right - sixth,
+      index3 = left + right >> 1,
+      index2 = index3 - sixth,
+      index4 = index3 + sixth,
+      el1 = index1,
+      el2 = index2,
+      el3 = index3,
+      el4 = index4,
+      el5 = index5,
+      less = left + 1,
+      great = right - 1,
+      tmp = 0
+  if(compare(el1, el2, data_levels, data_points, data_ids)) {
+    tmp = el1
+    el1 = el2
+    el2 = tmp
+  }
+  if(compare(el4, el5, data_levels, data_points, data_ids)) {
+    tmp = el4
+    el4 = el5
+    el5 = tmp
+  }
+  if(compare(el1, el3, data_levels, data_points, data_ids)) {
+    tmp = el1
+    el1 = el3
+    el3 = tmp
+  }
+  if(compare(el2, el3, data_levels, data_points, data_ids)) {
+    tmp = el2
+    el2 = el3
+    el3 = tmp
+  }
+  if(compare(el1, el4, data_levels, data_points, data_ids)) {
+    tmp = el1
+    el1 = el4
+    el4 = tmp
+  }
+  if(compare(el3, el4, data_levels, data_points, data_ids)) {
+    tmp = el3
+    el3 = el4
+    el4 = tmp
+  }
+  if(compare(el2, el5, data_levels, data_points, data_ids)) {
+    tmp = el2
+    el2 = el5
+    el5 = tmp
+  }
+  if(compare(el2, el3, data_levels, data_points, data_ids)) {
+    tmp = el2
+    el2 = el3
+    el3 = tmp
+  }
+  if(compare(el4, el5, data_levels, data_points, data_ids)) {
+    tmp = el4
+    el4 = el5
+    el5 = tmp
+  }
+
+  var pivot1_level  = data_levels[el2]
+  var pivot1_x      = data_points[2*el2]
+  var pivot1_y      = data_points[2*el2+1]
+  var pivot1_id     = data_ids[el2]
+
+  var pivot2_level  = data_levels[el4]
+  var pivot2_x      = data_points[2*el4]
+  var pivot2_y      = data_points[2*el4+1]
+  var pivot2_id     = data_ids[el4]
+
+  var ptr0 = el1
+  var ptr2 = el3
+  var ptr4 = el5
+  var ptr5 = index1
+  var ptr6 = index3
+  var ptr7 = index5
+
+  var level_x = data_levels[ptr0]
+  var level_y = data_levels[ptr2]
+  var level_z = data_levels[ptr4]
+  data_levels[ptr5] = level_x
+  data_levels[ptr6] = level_y
+  data_levels[ptr7] = level_z
+
+  for (var i1 = 0; i1 < 2; ++i1) {
+    var x = data_points[2*ptr0+i1]
+    var y = data_points[2*ptr2+i1]
+    var z = data_points[2*ptr4+i1]
+    data_points[2*ptr5+i1] = x
+    data_points[2*ptr6+i1] = y
+    data_points[2*ptr7+i1] = z
+  }
+
+  var id_x = data_ids[ptr0]
+  var id_y = data_ids[ptr2]
+  var id_z = data_ids[ptr4]
+  data_ids[ptr5] = id_x
+  data_ids[ptr6] = id_y
+  data_ids[ptr7] = id_z
+
+  move(index2, left, data_levels, data_points, data_ids)
+  move(index4, right, data_levels, data_points, data_ids)
+  for (var k = less; k <= great; ++k) {
+    if (comparePivot(k,
+        pivot1_level, pivot1_x, pivot1_y, pivot1_id,
+        data_levels, data_points, data_ids)) {
+      if (k !== less) {
+        swap(k, less, data_levels, data_points, data_ids)
+      }
+      ++less;
+    } else {
+      if (!comparePivot(k,
+          pivot2_level, pivot2_x, pivot2_y, pivot2_id,
+          data_levels, data_points, data_ids)) {
+        while (true) {
+          if (!comparePivot(great,
+              pivot2_level, pivot2_x, pivot2_y, pivot2_id,
+              data_levels, data_points, data_ids)) {
+            if (--great < k) {
+              break;
+            }
+            continue;
+          } else {
+            if (comparePivot(great,
+                pivot1_level, pivot1_x, pivot1_y, pivot1_id,
+                data_levels, data_points, data_ids)) {
+              rotate(k, less, great, data_levels, data_points, data_ids)
+              ++less;
+              --great;
+            } else {
+              swap(k, great, data_levels, data_points, data_ids)
+              --great;
+            }
+            break;
+          }
+        }
+      }
+    }
+  }
+  shufflePivot(left, less-1, pivot1_level, pivot1_x, pivot1_y, pivot1_id, data_levels, data_points, data_ids)
+  shufflePivot(right, great+1, pivot2_level, pivot2_x, pivot2_y, pivot2_id, data_levels, data_points, data_ids)
+  if (less - 2 - left <= INSERT_SORT_CUTOFF) {
+    insertionSort(left, less - 2, data_levels, data_points, data_ids)
+  } else {
+    quickSort(left, less - 2, data_levels, data_points, data_ids)
+  }
+  if (right - (great + 2) <= INSERT_SORT_CUTOFF) {
+    insertionSort(great + 2, right, data_levels, data_points, data_ids)
+  } else {
+    quickSort(great + 2, right, data_levels, data_points, data_ids)
+  }
+  if (great - less <= INSERT_SORT_CUTOFF) {
+    insertionSort(less, great, data_levels, data_points, data_ids)
+  } else {
+    quickSort(less, great, data_levels, data_points, data_ids)
+  }
+}

package.json

 {
   "name": "snap-points-2d",
-  "version": "1.0.1",
+  "version": "2.0.0",
   "description": "snap round 2d points",
@@ -30,3 +30,6 @@ "main": "snap.js",
     "typedarray-pool": "^1.1.0"
+  },
+  "devDependencies": {
+    "gauss-random": "^1.0.1"
   }
 }

README.md

@@ -13,8 +13,7 @@ snap-points-2d
 
-#### `var hlod = require('snap-points-2d')(points, output, outputIds[, bounds])`
+#### `var hlod = require('snap-points-2d')(points, ids, [, bounds])`
 Reorders the points hierarchically such that those which are drawn at the same pixel coordinate are grouped together.
 
 * `points` is an array of 2*n values
-* `output` is the reordered array of points
-* `outputIds` is the index of the reordered points in the input array
+* `ids` is an array which gets the reordered index of the points
 * `bounds` is an optional array of 4 values giving the bounding box of the points
@@ -21,0 +20,0 @@

snap.js

 'use strict'
 
-module.exports = snapPoints
-
 var pool = require('typedarray-pool')
 
-var SUBDIV = 2
+var sortLevels = require('./lib/sort')
 
-function SnapInterval(pixelSize, offset, count) {
-  this.pixelSize  = pixelSize
-  this.offset     = offset
-  this.count      = count
-}
+module.exports = snapPoints
 
@@ -39,11 +33,9 @@ function partition(points, ids, start, end, lox, loy, hix, hiy) {
 
-function VisitRecord(x, y, diam, start, end) {
-  this.x = x
-  this.y = y
-  this.diam = diam
-  this.start = start
-  this.end = end
+function SnapInterval(pixelSize, offset, count) {
+  this.pixelSize  = pixelSize
+  this.offset     = offset
+  this.count      = count
 }
 
-function snapPoints(points, output, outputId, bounds) {
+function snapPoints(points, ids, bounds) {
   var n    = points.length >>> 1
@@ -53,3 +45,3 @@ if(n < 1) {
   }
-  var ids = pool.mallocInt32(n)
+
   var lox =  Infinity, loy =  Infinity
@@ -66,2 +58,4 @@ var hix = -Infinity, hiy = -Infinity
   }
+
+  //Calculate diameter
   var scaleX = 1.0 / (hix - lox)
@@ -78,48 +72,58 @@ var scaleY = 1.0 / (hiy - loy)
 
-  var toVisit = [ new VisitRecord(lox, loy, diam, 0, n) ]
-  var ptr = n-1
-  var qptr = 0
+  var levels = pool.mallocInt32(n)
+  var ptr = 0
 
-  var scales = [ new SnapInterval(diam, n-1, 1) ]
-  var lastScale = diam
-
-  while(qptr < toVisit.length) {
-    var head = toVisit[qptr++]
-    var x = head.x
-    var y = head.y
-    var d = head.diam
-    var start = head.start
-    var end = head.end
-    output[2*ptr]   = (points[2*start]   - lox) * scaleX
-    output[2*ptr+1] = (points[2*start+1] - loy) * scaleY
-    outputId[ptr]   = ids[start]
-    if(d < lastScale) {
-      scales.push(new SnapInterval(d, ptr, n-ptr))
-    }
-    ptr   -= 1
-    start += 1
-    lastScale = d
-    var s = d / SUBDIV
-    for(var i=0; i<=SUBDIV; ++i) {
-      for(var j=0; j<=SUBDIV; ++j) {
-        var x0 = x + s * i
-        var y0 = y + s * j
-        var mid = partition(
-          points,
-          ids,
-          start,
-          end,
-          x0, y0,
-          x + s*(i+1), y + s*(j+1))
-        if(start < mid) {
-          toVisit.push(new VisitRecord(x0, y0, s, start, mid))
-          start = mid
+  function snapRec(x, y, diam, start, end, level) {
+    var diam_2 = diam * 0.5
+    var offset = start + 1
+    var count = end - start
+    levels[ptr++] = level
+    for(var i=0; i<2; ++i) {
+      for(var j=0; j<2; ++j) {
+        var nx = x+i*diam_2
+        var ny = y+j*diam_2
+        var nextOffset = partition(points, ids, offset, end, nx, ny, nx+diam_2, ny+diam_2)
+        if(nextOffset === offset) {
+          continue
         }
+        if(nextOffset - offset >= Math.max(0.9 * count, 32)) {
+          var mid = (end + start)>>>1
+          snapRec(nx, ny, diam_2, offset, mid, level+1)
+          offset = mid
+        }
+        snapRec(nx, ny, diam_2, offset, nextOffset, level+1)
+        offset = nextOffset
       }
     }
   }
-  pool.free(ids)
-  scales.push(new SnapInterval(lastScale, 0, n))
+  snapRec(lox, loy, diam, 0, n, 0)
+  sortLevels(levels, points, ids, n)
 
-  return scales
+  var lod = []
+  var lastLevel = 0
+  var prevOffset = n-1
+  for(var ptr=n-1; ptr>=0; --ptr) {
+    points[2*ptr]   = (points[2*ptr]   - lox) * scaleX
+    points[2*ptr+1] = (points[2*ptr+1] - loy) * scaleY
+
+    var level = levels[ptr]
+    if(level === lastLevel) {
+      continue
+    }
+
+    lod.push(new SnapInterval(
+      diam * Math.pow(0.5, level),
+      ptr + 1,
+      prevOffset - ptr
+    ))
+    prevOffset = ptr
+
+    lastLevel = level
+  }
+  if(prevOffset) {
+    lod.push(new SnapInterval(diam * Math.pow(0.5, level+1), 0, prevOffset))
+  }
+  pool.free(levels)
+
+  return lod
 }

New alerts

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

Improved metrics

Total package byte prevSize

14939

164.08%

Number of package files

9

80%

Lines of code

397

267.59%

Worsened metrics

Dev dependency count

1

Infinity%

Number of lines in readme file

30

-3.23%

Number of medium supply chain risk alerts

1

Infinity%

No dependency changes