snap-points-2d - npm Package Compare versions

Comparing version 3.2.0 to 4.0.0

license.md

+
+The MIT License (MIT)
+
+Copyright (c) 2013 Mikola Lysenko
+
+Permission is hereby granted, free of charge, to any person obtaining a copy
+of this software and associated documentation files (the "Software"), to deal
+in the Software without restriction, including without limitation the rights
+to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
+copies of the Software, and to permit persons to whom the Software is
+furnished to do so, subject to the following conditions:
+
+The above copyright notice and this permission notice shall be included in
+all copies or substantial portions of the Software.
+
+THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
+IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
+FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
+AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
+LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
+OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
+THE SOFTWARE.

sort.js

+'use strict'
+
+module.exports = global.Float64Array ? nativeSort : sortLevels
+
+
+function nativeSort(levels, points, ids, weights, n) {
+  // pack levels: uint8, x-coord: uint16 and id: uint32 to float64
+  var packed = new Float64Array(n)
+  var packedInt = new Uint32Array(packed.buffer)
+
+  for (var i = 0; i < n; i++) {
+    packedInt[i * 2] = i
+    packedInt[i * 2 + 1] = (0x3ff00000 & (levels[i] << 20) | 0x0000ffff & ((1 - points[i * 2]) * 0xffff))
+  }
+
+  // do native sort
+  packed.sort()
+
+  // unpack data back
+  var sortedLevels = new Uint8Array(n)
+  var sortedWeights = new Uint32Array(n)
+  var sortedIds = new Uint32Array(n)
+  var sortedPoints = new Float64Array(n * 2)
+  for (var i = 0; i < n; i++) {
+    var id = packedInt[(n - i - 1) * 2]
+    sortedLevels[i] = levels[id]
+    sortedWeights[i] = weights[id]
+    sortedIds[i] = ids[id]
+    sortedPoints[i * 2] = points[id * 2]
+    sortedPoints[i * 2 + 1] = points[id * 2 + 1]
+  }
+
+  return {
+    levels: sortedLevels,
+    points: sortedPoints,
+    ids: sortedIds,
+    weights: sortedWeights
+  }
+}
+
+
+var INSERT_SORT_CUTOFF = 32
+
+function sortLevels(data_levels, data_points, data_ids, data_weights, n0) {
+  if (n0 <= 4*INSERT_SORT_CUTOFF) {
+    insertionSort(0, n0 - 1, data_levels, data_points, data_ids, data_weights)
+  } else {
+    quickSort(0, n0 - 1, data_levels, data_points, data_ids, data_weights)
+  }
+
+  return {
+    levels: data_levels,
+    points: data_points,
+    ids: data_ids,
+    weights: data_weights
+  }
+}
+
+function insertionSort(left, right, data_levels, data_points, data_ids, data_weights) {
+  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 a_weight = data_weights[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]
+      data_weights[j]     = data_weights[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
+    data_weights[j]    = a_weight
+  }
+}
+
+function swap(i, j, data_levels, data_points, data_ids, data_weights) {
+  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 a_weight = data_weights[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_weights[i]    = data_weights[j]
+
+  data_levels[j]     = a_level
+  data_points[2*j]   = a_x
+  data_points[2*j+1] = a_y
+  data_ids[j]        = a_id
+  data_weights[j]    = a_weight
+}
+
+function move(i, j, data_levels, data_points, data_ids, data_weights) {
+  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_weights[i]    = data_weights[j]
+}
+
+function rotate(i, j, k, data_levels, data_points, data_ids, data_weights) {
+  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 a_weight = data_weights[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_weights[i]    = data_weights[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_weights[j]    = data_weights[k]
+
+  data_levels[k]     = a_level
+  data_points[2*k]   = a_x
+  data_points[2*k+1] = a_y
+  data_ids[k]        = a_id
+  data_weights[k]    = a_weight
+}
+
+function shufflePivot(
+  i, j,
+  a_level, a_x, a_y, a_id, a_weight,
+  data_levels, data_points, data_ids, data_weights) {
+
+  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_weights[i]    = data_weights[j]
+
+  data_levels[j]     = a_level
+  data_points[2*j]   = a_x
+  data_points[2*j+1] = a_y
+  data_ids[j]        = a_id
+  data_weights[j]    = a_weight
+}
+
+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, data_weights) {
+  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, data_weights)) {
+    tmp = el1
+    el1 = el2
+    el2 = tmp
+  }
+  if(compare(el4, el5, data_levels, data_points, data_ids, data_weights)) {
+    tmp = el4
+    el4 = el5
+    el5 = tmp
+  }
+  if(compare(el1, el3, data_levels, data_points, data_ids, data_weights)) {
+    tmp = el1
+    el1 = el3
+    el3 = tmp
+  }
+  if(compare(el2, el3, data_levels, data_points, data_ids, data_weights)) {
+    tmp = el2
+    el2 = el3
+    el3 = tmp
+  }
+  if(compare(el1, el4, data_levels, data_points, data_ids, data_weights)) {
+    tmp = el1
+    el1 = el4
+    el4 = tmp
+  }
+  if(compare(el3, el4, data_levels, data_points, data_ids, data_weights)) {
+    tmp = el3
+    el3 = el4
+    el4 = tmp
+  }
+  if(compare(el2, el5, data_levels, data_points, data_ids, data_weights)) {
+    tmp = el2
+    el2 = el5
+    el5 = tmp
+  }
+  if(compare(el2, el3, data_levels, data_points, data_ids, data_weights)) {
+    tmp = el2
+    el2 = el3
+    el3 = tmp
+  }
+  if(compare(el4, el5, data_levels, data_points, data_ids, data_weights)) {
+    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 pivot1_weight = data_weights[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 pivot2_weight = data_weights[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
+
+  var weight_x = data_weights[ptr0]
+  var weight_y = data_weights[ptr2]
+  var weight_z = data_weights[ptr4]
+  data_weights[ptr5] = weight_x
+  data_weights[ptr6] = weight_y
+  data_weights[ptr7] = weight_z
+
+  move(index2, left,  data_levels, data_points, data_ids, data_weights)
+  move(index4, right, data_levels, data_points, data_ids, data_weights)
+  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, data_weights)
+      }
+      ++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, data_weights)
+              ++less;
+              --great;
+            } else {
+              swap(k, great, data_levels, data_points, data_ids, data_weights)
+              --great;
+            }
+            break;
+          }
+        }
+      }
+    }
+  }
+  shufflePivot(left, less-1, pivot1_level, pivot1_x, pivot1_y, pivot1_id, pivot1_weight, data_levels, data_points, data_ids, data_weights)
+  shufflePivot(right, great+1, pivot2_level, pivot2_x, pivot2_y, pivot2_id, pivot2_weight, data_levels, data_points, data_ids, data_weights)
+  if (less - 2 - left <= INSERT_SORT_CUTOFF) {
+    insertionSort(left, less - 2, data_levels, data_points, data_ids, data_weights)
+  } else {
+    quickSort(left, less - 2, data_levels, data_points, data_ids, data_weights)
+  }
+  if (right - (great + 2) <= INSERT_SORT_CUTOFF) {
+    insertionSort(great + 2, right, data_levels, data_points, data_ids, data_weights)
+  } else {
+    quickSort(great + 2, right, data_levels, data_points, data_ids, data_weights)
+  }
+  if (great - less <= INSERT_SORT_CUTOFF) {
+    insertionSort(less, great, data_levels, data_points, data_ids, data_weights)
+  } else {
+    quickSort(less, great, data_levels, data_points, data_ids, data_weights)
+  }
+}

test.js

+'use strict'
+
+var t = require('tape')
+var snap = require('./snap')
+var approxEqual = require('almost-equal')
+
+
+t('snap-points-2d', t => {
+  function verifySnap(srcPoints) {
+    var numPoints = srcPoints.length>>>1
+    var bounds    = []
+
+    var {levels, ids, weights, points} = snap(srcPoints, bounds)
+    var npoints = points
+
+    var sx = bounds[0]
+    var sy = bounds[1]
+    var sw = bounds[2] - bounds[0]
+    var sh = bounds[3] - bounds[1]
+
+    for(var i=0; i < numPoints; ++i) {
+      var id = ids[i]
+      t.ok(approxEqual(sx + sw*npoints[2*i],   srcPoints[2*id], approxEqual.FLT_EPSILON),
+        'id perm ok: ' + id + ' ' +  srcPoints[2*id] + ' = ' + (sx + sw*npoints[2*i]))
+      t.ok(approxEqual(sy + sh*npoints[2*i+1], srcPoints[2*id+1], approxEqual.FLT_EPSILON), 'id perm ok: ' + id + ' ' +  srcPoints[2*id+1] + ' = ' + (sy + sh*npoints[2*i+1]))
+    }
+
+    t.equals(levels[levels.length-1].offset, 0, 'last item')
+    t.equals(levels[0].offset+levels[0].count, numPoints, 'first item')
+
+    for(var i=0; i < levels.length; ++i) {
+      var s = levels[i]
+
+      var r = s.pixelSize
+      var offs  = s.offset
+      var count = s.count
+
+      console.log('level=', i, r, offs, count)
+
+      if(i > 0) {
+        t.equals(offs+count, levels[i-1].offset, 'offset for ' + i)
+        t.ok(r < levels[i-1].pixelSize, 'test scales ok')
+      }
+    k_loop:
+      for(var k=offs-1; k>=0; --k) {
+        var ax = npoints[2*k]
+        var ay = npoints[2*k+1]
+
+        var mind = Infinity
+
+        for(var j=offs; j < offs+count; ++j) {
+          var x = npoints[2*j]
+          var y = npoints[2*j+1]
+
+          mind = Math.min(mind, Math.max(Math.abs(ax-x), Math.abs(ay-y)))
+        }
+
+        t.ok(mind <= 2.0 * r, k + ':' + ax + ',' + ay + ' is not covered - closest pt = ' + mind)
+      }
+    }
+  }
+
+  verifySnap([
+     1, 1,
+     2, 2,
+     3, 3,
+     4, 4,
+     5, 5
+  ])
+
+  verifySnap([
+    0,0,
+    0,0,
+    0,0,
+    0,0
+  ])
+
+  verifySnap([
+    1, 2,
+    2, 5,
+    3, 6,
+    4, -1
+  ])
+
+  var pts = new Array(100)
+  for(var i=0; i < 100; ++i) {
+    pts[i] = Math.random()
+  }
+  verifySnap(pts)
+
+  t.end()
+})
+
+
+t('basics', t => {
+  let {levels, points, ids, weights} = snap([1,1,2,2,3,3,4,4,5,5])
+
+  t.deepEqual(ids, [2, 4, 1, 3, 0])
+  t.deepEqual(points, [ 0.5, 0.5, 1, 1, 0.25, 0.25, 0.75, 0.75, 0, 0 ])
+  t.deepEqual(weights, [1, 1, 2, 2, 5])
+  t.deepEqual(levels, [
+    { count: 1, offset: 4, pixelSize: 2 },
+    { count: 2, offset: 2, pixelSize: 1 },
+    { count: 2, offset: 0, pixelSize: 0.5 }
+  ])
+
+  t.end()
+})
+
+
+t('no arguments', t => {
+  var levels = snap([0,0, 1,1, 2,2])
+
+  t.end()
+})
+
+t('larger bounds', t => {
+  var pos = [0,0, 1,1, 2,2, 3,3, 4,4]
+
+  var {levels} = snap(pos.slice(), [0,0,4,4])
+  t.deepEqual(levels, [
+      {pixelSize: 2, offset: 4, count: 1},
+      {pixelSize: 1, offset: 2, count: 2},
+      {pixelSize: 0.5, offset: 0, count: 2}
+  ])
+
+  var {levels} = snap(pos.slice(), [0,0,40,40])
+
+  t.deepEqual(levels, [
+    {pixelSize: 20, offset: 4, count: 1},
+    {pixelSize: 10, offset: 3, count: 1},
+    {pixelSize: 5, offset: 2, count: 1},
+    {pixelSize: 2.5, offset: 1, count: 1},
+    {pixelSize: 1.25, offset: 0, count: 1}
+  ])
+
+  t.end()
+})
+
+
+t('performance', t => {
+  let N = 1e6
+  let points = new Float64Array(N)
+
+  for (let i = 0; i < N; i++) {
+    points[i] = Math.random()
+  }
+
+  console.time(1)
+    snap(points)
+  console.timeEnd(1)
+
+  t.end()
+})

package.json

 {
   "name": "snap-points-2d",
-  "version": "3.2.0",
+  "version": "4.0.0",
   "description": "snap round 2d points",
   "main": "snap.js",
   "scripts": {
-    "test": "tape test/*.js"
+    "test": "tape test.js"
   },
@@ -29,6 +29,7 @@ "repository": {
   "devDependencies": {
-    "typedarray-pool": "^1.1.0",
     "almost-equal": "^1.0.0",
     "gauss-random": "^1.0.1",
-    "tape": "^4.2.0"
+    "math-float64-bits": "^1.0.1",
+    "tape": "^4.2.0",
+    "typedarray-pool": "^1.1.0"
   },
@@ -35,0 +36,0 @@ "dependencies": {

README.md

@@ -1,3 +0,3 @@
-snap-points-2d
-==============
+# snap-points-2d
+
 Runs iterative snap rounding on a set of 2D coordinates to produce a hierarchical level of detail for optimizing online rendering of huge 2D plots.
@@ -13,20 +13,20 @@
 
-#### `var hlod = require('snap-points-2d')(points, ids, weights, [, bounds])`
+#### `{levels, ids, weights, points} = require('snap-points-2d')(points, bounds?)`
 
 Reorders the `points` hierarchically such that those which are drawn at the same pixel coordinate are grouped together.
 
-* `points` is an input array of 2*n values, which gets reordered
-* `ids` is an output array which gets the reordered index of the points
-* `weights` is an output array of point weights (number of points at the same pixel), which can be used for transparent rendering
-* `bounds` is an optional input array of 4 values giving the bounding box of the points
+##### Inputs
+* `points` is an input array of 2*n coordinate values. It is kept untouched.
+* `bounds` is an optional array of 4 bounding box values of the points.
 
-**Returns** An array of LOD scales.  Each record is an object with the following properties:
+##### Outputs
+* `points` is an output float64 array with reordered an normalized to `bounds` point values.
+* `ids` is an output uint32 array which gets the reordered index of the points.
+* `weights` is an output uint32 array of point weights (number of points at the same pixel), which can be used for transparent rendering.
+* `levels` is an array of LOD scales.  Each record is an object with the following properties:
+	* `pixelSize` the pixel size of this level of detail in data units
+	* `offset` the offset of this lod within the output array
+	* `count` the number of items in the lod
 
-* `pixelSize` the pixel size of this level of detail in data units
-* `offset` the offset of this lod within the output array
-* `count` the number of items in the lod
-
-**Note** the points in `output` are rescaled to the unit box `[0,1]x[0,1]` and the array `points` in the input is shuffled during execution.
-
 # License
 (c) 2015 Mikola Lysenko. MIT License

snap.js

 'use strict'
 
-var sortLevels = require('./lib/sort')
 var getBounds = require('array-bounds')
+var sort = require('./sort')
 
 module.exports = snapPoints
 
-function partition(points, ids, start, end, lox, loy, hix, hiy) {
-  var mid = start
-  for(var i=start; i<end; ++i) {
-    var x  = points[2*i]
-    var y  = points[2*i+1]
-    var s  = ids[i]
-    if(lox <= x && x <= hix &&
-       loy <= y && y <= hiy) {
-      if(i === mid) {
-        mid += 1
-      } else {
-        points[2*i]     = points[2*mid]
-        points[2*i+1]   = points[2*mid+1]
-        ids[i]          = ids[mid]
-        points[2*mid]   = x
-        points[2*mid+1] = y
-        ids[mid]        = s
-        mid += 1
-      }
-    }
+function snapPoints(srcPoints, bounds) {
+  var n = srcPoints.length >>> 1
+  if(n < 1) {
+    return {levels: [], ids: null, weights: null, points: srcPoints}
   }
-  return mid
-}
 
-function SnapInterval(pixelSize, offset, count) {
-  this.pixelSize  = pixelSize
-  this.offset     = offset
-  this.count      = count
-}
+  var points = new Float64Array(n * 2)
 
-function snapPoints(points, ids, weights, bounds) {
-  var n = points.length >>> 1
-  if(n < 1) {
-    return []
-  }
-
-  if (!ids) ids = Array(n)
-  if (!weights) weights = Array(n)
   if (!bounds) bounds = []
 
-  for(var i=0; i<n; ++i) {
+  var ids = new Uint32Array(n)
+  var weights = new Uint32Array(n)
+  var levels = new Uint8Array(n)
+
+  for(var i=0; i < n; ++i) {
     ids[i] = i
@@ -54,3 +28,3 @@ }
   if (!bounds.length || bounds.length < 4 || bounds[0] >= bounds[2] || bounds[1] >= bounds[3]) {
-    var b = getBounds(points, 2)
+    var b = getBounds(srcPoints, 2)
 
@@ -75,3 +49,3 @@ if(b[0] === b[2]) {
 
-  //Calculate diameter
+  // Calculate diameter
   var scaleX = 1.0 / (hix - lox)
@@ -81,6 +55,11 @@ var scaleY = 1.0 / (hiy - loy)
 
+  // normalize values
+  for (var i = 0; i < n; i++) {
+    points[2*i]   = (srcPoints[2*i]   - lox) * scaleX
+    points[2*i+1] = (srcPoints[2*i+1] - loy) * scaleY
+  }
 
-
-  var levels = new Int32Array(n)
+  // Rearrange in quadtree order
   var ptr = 0
+  snapRec(0, 0, 1, 0, n, 0)
 
@@ -107,7 +86,2 @@ function snapRec(x, y, diam, start, end, level) {
         }
-        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)
@@ -118,5 +92,31 @@ offset = nextOffset
   }
-  snapRec(lox, loy, diam, 0, n, 0)
-  sortLevels(levels, points, ids, weights, n)
 
+  function partition(points, ids, start, end, lox, loy, hix, hiy) {
+    var mid = start
+    for(var i=start; i < end; ++i) {
+      var x  = points[2*i]
+      var y  = points[2*i+1]
+      var s  = ids[i]
+      if(lox <= x && x <= hix &&
+         loy <= y && y <= hiy) {
+        if(i === mid) {
+          mid += 1
+        } else {
+          points[2*i]     = points[2*mid]
+          points[2*i+1]   = points[2*mid+1]
+          ids[i]          = ids[mid]
+          points[2*mid]   = x
+          points[2*mid+1] = y
+          ids[mid]        = s
+          mid += 1
+        }
+      }
+    }
+    return mid
+  }
+
+  // sort by levels with accordance to x-coordinate
+  var result = sort(levels, points, ids, weights, n)
+
+  // form levels of details
   var lod         = []
@@ -126,6 +126,3 @@ var lastLevel   = 0
   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]
+    var level = result.levels[ptr]
     if(level === lastLevel) {
@@ -135,7 +132,7 @@ continue
 
-    lod.push(new SnapInterval(
-      diam * Math.pow(0.5, level),
-      ptr+1,
-      prevOffset - (ptr+1)
-    ))
+    lod.push({
+      pixelSize: diam * Math.pow(0.5, level),
+      offset: ptr+1,
+      count: prevOffset - (ptr+1)
+    })
     prevOffset = ptr+1
@@ -146,5 +143,11 @@
 
-  lod.push(new SnapInterval(diam * Math.pow(0.5, level+1), 0, prevOffset))
+  lod.push({
+    pixelSize: diam * Math.pow(0.5, level+1),
+    offset: 0,
+    count: prevOffset
+  })
 
-  return lod
+  result.levels = lod
+
+  return result
 }

lib/sort.js

-'use strict'
-
-module.exports = sortLevels
-
-var INSERT_SORT_CUTOFF = 32
-
-function sortLevels(data_levels, data_points, data_ids, data_weights, n0) {
-  if (n0 <= 4*INSERT_SORT_CUTOFF) {
-    insertionSort(0, n0 - 1, data_levels, data_points, data_ids, data_weights)
-  } else {
-    quickSort(0, n0 - 1, data_levels, data_points, data_ids, data_weights)
-  }
-}
-
-function insertionSort(left, right, data_levels, data_points, data_ids, data_weights) {
-  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 a_weight = data_weights[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]
-      data_weights[j]     = data_weights[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
-    data_weights[j]    = a_weight
-  }
-}
-
-function swap(i, j, data_levels, data_points, data_ids, data_weights) {
-  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 a_weight = data_weights[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_weights[i]    = data_weights[j]
-
-  data_levels[j]     = a_level
-  data_points[2*j]   = a_x
-  data_points[2*j+1] = a_y
-  data_ids[j]        = a_id
-  data_weights[j]    = a_weight
-}
-
-function move(i, j, data_levels, data_points, data_ids, data_weights) {
-  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_weights[i]    = data_weights[j]
-}
-
-function rotate(i, j, k, data_levels, data_points, data_ids, data_weights) {
-  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 a_weight = data_weights[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_weights[i]    = data_weights[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_weights[j]    = data_weights[k]
-
-  data_levels[k]     = a_level
-  data_points[2*k]   = a_x
-  data_points[2*k+1] = a_y
-  data_ids[k]        = a_id
-  data_weights[k]    = a_weight
-}
-
-function shufflePivot(
-  i, j,
-  a_level, a_x, a_y, a_id, a_weight,
-  data_levels, data_points, data_ids, data_weights) {
-
-  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_weights[i]    = data_weights[j]
-
-  data_levels[j]     = a_level
-  data_points[2*j]   = a_x
-  data_points[2*j+1] = a_y
-  data_ids[j]        = a_id
-  data_weights[j]    = a_weight
-}
-
-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, data_weights) {
-  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, data_weights)) {
-    tmp = el1
-    el1 = el2
-    el2 = tmp
-  }
-  if(compare(el4, el5, data_levels, data_points, data_ids, data_weights)) {
-    tmp = el4
-    el4 = el5
-    el5 = tmp
-  }
-  if(compare(el1, el3, data_levels, data_points, data_ids, data_weights)) {
-    tmp = el1
-    el1 = el3
-    el3 = tmp
-  }
-  if(compare(el2, el3, data_levels, data_points, data_ids, data_weights)) {
-    tmp = el2
-    el2 = el3
-    el3 = tmp
-  }
-  if(compare(el1, el4, data_levels, data_points, data_ids, data_weights)) {
-    tmp = el1
-    el1 = el4
-    el4 = tmp
-  }
-  if(compare(el3, el4, data_levels, data_points, data_ids, data_weights)) {
-    tmp = el3
-    el3 = el4
-    el4 = tmp
-  }
-  if(compare(el2, el5, data_levels, data_points, data_ids, data_weights)) {
-    tmp = el2
-    el2 = el5
-    el5 = tmp
-  }
-  if(compare(el2, el3, data_levels, data_points, data_ids, data_weights)) {
-    tmp = el2
-    el2 = el3
-    el3 = tmp
-  }
-  if(compare(el4, el5, data_levels, data_points, data_ids, data_weights)) {
-    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 pivot1_weight = data_weights[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 pivot2_weight = data_weights[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
-
-  var weight_x = data_weights[ptr0]
-  var weight_y = data_weights[ptr2]
-  var weight_z = data_weights[ptr4]
-  data_weights[ptr5] = weight_x
-  data_weights[ptr6] = weight_y
-  data_weights[ptr7] = weight_z
-
-  move(index2, left,  data_levels, data_points, data_ids, data_weights)
-  move(index4, right, data_levels, data_points, data_ids, data_weights)
-  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, data_weights)
-      }
-      ++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, data_weights)
-              ++less;
-              --great;
-            } else {
-              swap(k, great, data_levels, data_points, data_ids, data_weights)
-              --great;
-            }
-            break;
-          }
-        }
-      }
-    }
-  }
-  shufflePivot(left, less-1, pivot1_level, pivot1_x, pivot1_y, pivot1_id, pivot1_weight, data_levels, data_points, data_ids, data_weights)
-  shufflePivot(right, great+1, pivot2_level, pivot2_x, pivot2_y, pivot2_id, pivot2_weight, data_levels, data_points, data_ids, data_weights)
-  if (less - 2 - left <= INSERT_SORT_CUTOFF) {
-    insertionSort(left, less - 2, data_levels, data_points, data_ids, data_weights)
-  } else {
-    quickSort(left, less - 2, data_levels, data_points, data_ids, data_weights)
-  }
-  if (right - (great + 2) <= INSERT_SORT_CUTOFF) {
-    insertionSort(great + 2, right, data_levels, data_points, data_ids, data_weights)
-  } else {
-    quickSort(great + 2, right, data_levels, data_points, data_ids, data_weights)
-  }
-  if (great - less <= INSERT_SORT_CUTOFF) {
-    insertionSort(less, great, data_levels, data_points, data_ids, data_weights)
-  } else {
-    quickSort(less, great, data_levels, data_points, data_ids, data_weights)
-  }
-}

LICENSE

-
-The MIT License (MIT)
-
-Copyright (c) 2013 Mikola Lysenko
-
-Permission is hereby granted, free of charge, to any person obtaining a copy
-of this software and associated documentation files (the "Software"), to deal
-in the Software without restriction, including without limitation the rights
-to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
-copies of the Software, and to permit persons to whom the Software is
-furnished to do so, subject to the following conditions:
-
-The above copyright notice and this permission notice shall be included in
-all copies or substantial portions of the Software.
-
-THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
-IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
-FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
-AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
-LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
-OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
-THE SOFTWARE.

test/test.js

-'use strict'
-
-var tape = require('tape')
-var snap = require('../snap')
-var approxEqual = require('almost-equal')
-
-
-tape('snap-points-2d', function(t) {
-
-  function verifySnap(points) {
-    var numPoints = points.length>>>1
-    var npoints   = points.slice()
-    var ids       = new Array(numPoints)
-    var weights   = new Array(numPoints)
-    var bounds    = []
-
-    var scales = snap(npoints, ids, weights, bounds)
-
-    var sx = bounds[0]
-    var sy = bounds[1]
-    var sw = bounds[2] - bounds[0]
-    var sh = bounds[3] - bounds[1]
-
-    for(var i=0; i<numPoints; ++i) {
-      var id = ids[i]
-      t.ok(approxEqual(sx + sw*npoints[2*i],   points[2*id], approxEqual.FLT_EPSILON),
-        'id perm ok: ' + id + ' ' +  points[2*id] + ' = ' + (sx + sw*npoints[2*i]))
-      t.ok(approxEqual(sy + sh*npoints[2*i+1], points[2*id+1], approxEqual.FLT_EPSILON), 'id perm ok: ' + id + ' ' +  points[2*id+1] + ' = ' + (sy + sh*npoints[2*i+1]))
-    }
-
-    t.equals(scales[scales.length-1].offset, 0, 'last item')
-    t.equals(scales[0].offset+scales[0].count, numPoints, 'first item')
-
-    for(var i=0; i<scales.length; ++i) {
-      var s = scales[i]
-
-      var r = s.pixelSize
-      var offs  = s.offset
-      var count = s.count
-
-      console.log('level=', i, r, offs, count)
-
-      if(i > 0) {
-        t.equals(offs+count, scales[i-1].offset, 'offset for ' + i)
-        t.ok(r < scales[i-1].pixelSize, 'test scales ok')
-      }
-
-k_loop:
-      for(var k=offs-1; k>=0; --k) {
-        var ax = npoints[2*k]
-        var ay = npoints[2*k+1]
-
-        var mind = Infinity
-
-        for(var j=offs; j<offs+count; ++j) {
-          var x = npoints[2*j]
-          var y = npoints[2*j+1]
-
-          mind = Math.min(mind, Math.max(Math.abs(ax-x), Math.abs(ay-y)))
-        }
-
-        t.ok(mind <= 2.0 * r, k + ':' + ax + ',' + ay + ' is not covered - closest pt = ' + mind)
-      }
-    }
-  }
-
-  t.same(snap([], [], []), [])
-
-  verifySnap([
-     1, 1,
-     2, 2,
-     3, 3,
-     4, 4,
-     5, 5])
-
-  verifySnap([
-    0,0,
-    0,0,
-    0,0,
-    0,0])
-
-  verifySnap([
-    1, 2,
-    2, 5,
-    3, 6,
-    4, -1
-  ])
-
-  var pts = new Array(100)
-  for(var i=0; i<100; ++i) {
-    pts[i] = Math.random()
-  }
-  verifySnap(pts)
-
-  t.end()
-})
-
-
-tape('no arguments', function (t) {
-  var levels = snap([0,0, 1,1, 2,2])
-
-  t.end()
-})
-
-tape('larger bounds', function (t) {
-  var pos = [0,0, 1,1, 2,2, 3,3, 4,4]
-
-  var levels = snap(pos.slice(), [], [], [0,0,4,4])
-  t.deepEqual(levels, [
-      {pixelSize: 2, offset: 4, count: 1},
-      {pixelSize: 1, offset: 2, count: 2},
-      {pixelSize: 0.5, offset: 0, count: 2}
-  ])
-
-  var levels2 = snap(pos.slice(), [], [], [0,0,40,40])
-  t.deepEqual(levels2, [
-    {pixelSize: 20, offset: 4, count: 1},
-    {pixelSize: 10, offset: 3, count: 1},
-    {pixelSize: 5, offset: 2, count: 1},
-    {pixelSize: 2.5, offset: 1, count: 1},
-    {pixelSize: 1.25, offset: 0, count: 1}
-  ])
-
-  t.end()
-})

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

New author

Supply chain risk

A new npm collaborator published a version of the package for the first time. New collaborators are usually benign additions to a project, but do indicate a change to the security surface area of a package.

Found 1 instance in 1 package

Fixed alerts

New author

Supply chain risk

A new npm collaborator published a version of the package for the first time. New collaborators are usually benign additions to a project, but do indicate a change to the security surface area of a package.

Found 1 instance in 1 package

Improved metrics

Total package byte prevSize

22027

8.03%

Lines of code

586

11.41%

Worsened metrics

Dev dependency count

5

25%

Number of package files

9

-10%

Number of medium supply chain risk alerts

2

100%

No dependency changes