geokdbush - npm Package Compare versions

Comparing version 1.1.0 to 2.0.0

bench/bench-geokdbush.js

@@ -1,14 +0,12 @@
-'use strict';
+import cities from 'all-the-cities';
+import KDBush from 'kdbush';
+import * as geokdbush from '../index.js';
 
-var cities = require('all-the-cities');
-var kdbush = require('kdbush');
-var geokdbush = require('../');
-
 console.log('=== geokdbush benchmark ===');
 
-var n = cities.length;
-var k = 1000;
+const n = cities.length;
+const k = 1000;
 
-var randomPoints = [];
-for (var i = 0; i < k; i++) randomPoints.push({
+const randomPoints = [];
+for (let i = 0; i < k; i++) randomPoints.push({
     lon: -180 + 360 * Math.random(),
@@ -19,3 +17,5 @@ lat: -60 + 140 * Math.random()
 console.time(`index ${n} points`);
-var index = kdbush(cities, (p) => p.lon, (p) => p.lat);
+const index = new KDBush(cities.length);
+for (const {loc: {coordinates: [lon, lat]}} of cities) index.add(lon, lat);
+index.finish();
 console.timeEnd(`index ${n} points`);
@@ -36,3 +36,3 @@
 console.time(`${k} random queries of 1 closest`);
-for (i = 0; i < k; i++) geokdbush.around(index, randomPoints[i].lon, randomPoints[i].lat, 1);
+for (let i = 0; i < k; i++) geokdbush.around(index, randomPoints[i].lon, randomPoints[i].lat, 1);
 console.timeEnd(`${k} random queries of 1 closest`);

bench/bench-naive.js

@@ -1,35 +0,35 @@
-'use strict';
+import cities from 'all-the-cities';
 
-var cities = require('all-the-cities');
-
 console.log('=== naive benchmark ===');
 
-var rad = Math.PI / 180;
+const rad = Math.PI / 180;
 
-var n = cities.length;
-var k = 1000;
-var p = {lon: -119.7051, lat: 34.4363};
+const n = cities.length;
+const k = 1000;
+const p = {loc: {coordinates: [-119.7051, 34.4363]}};
 
-var randomPoints = [];
-for (var i = 0; i < k; i++) randomPoints.push({
-    lon: -180 + 360 * Math.random(),
-    lat: -60 + 140 * Math.random()
+const randomPoints = [];
+for (let i = 0; i < k; i++) randomPoints.push({
+    loc: {
+        coordinates: [
+            -180 + 360 * Math.random(),
+            -60 + 140 * Math.random()
+        ]
+    }
 });
 
-var compareDist = (a, b) => a.dist - b.dist;
-
 console.time(`query (sort) all ${n}`);
-var items = cities.map((city) => ({p: city, dist: dist(city, p)}));
-items.sort(compareDist);
+const items = cities.map(city => ({p: city, dist: dist(city, p)}));
+items.sort((a, b) => a.dist - b.dist);
 console.timeEnd(`query (sort) all ${n}`);
 
 console.time(`${k} random queries of 1 closest`);
-for (i = 0; i < k; i++) findClosest(randomPoints[i]);
+for (let i = 0; i < k; i++) findClosest(randomPoints[i]);
 console.timeEnd(`${k} random queries of 1 closest`);
 
 function findClosest(p) {
-    var minDist = Infinity;
-    var closest = null;
-    for (var i = 0; i < cities.length; i++) {
-        var d = dist(p, cities[i]);
+    let minDist = Infinity;
+    let closest = null;
+    for (let i = 0; i < cities.length; i++) {
+        const d = dist(p, cities[i]);
         if (d < minDist) {
@@ -44,5 +44,7 @@ minDist = d;
 function dist(a, b) {
-    var d = Math.sin(a.lat * rad) * Math.sin(b.lat * rad) +
-            Math.cos(a.lat * rad) * Math.cos(b.lat * rad) * Math.cos((a.lon - b.lon) * rad);
+    const [lon1, lat1] = a.loc.coordinates;
+    const [lon2, lat2] = b.loc.coordinates;
+    const d = Math.sin(lat1 * rad) * Math.sin(lat2 * rad) +
+            Math.cos(lat1 * rad) * Math.cos(lat2 * rad) * Math.cos((lon1 - lon2) * rad);
     return 6371 * Math.acos(Math.min(d, 1));
 }

bench/bench-sphere-knn.js

@@ -1,13 +0,13 @@
-'use strict';
 
-var cities = require('all-the-cities');
-var sphereKnn = require('sphere-knn');
 
+import cities from 'all-the-cities';
+import sphereKnn from 'sphere-knn';
+
 console.log('=== sphere-knn benchmark ===');
 
-var n = cities.length;
-var k = 1000;
+const n = cities.length;
+const k = 1000;
 
-var randomPoints = [];
-for (var i = 0; i < k; i++) randomPoints.push({
+const randomPoints = [];
+for (let i = 0; i < k; i++) randomPoints.push({
     lon: -180 + 360 * Math.random(),
@@ -17,4 +17,6 @@ lat: -60 + 140 * Math.random()
 
+const locations = cities.map(c => c.loc.coordinates);
+
 console.time(`index ${cities.length} points`);
-var sphereKnnLookup = sphereKnn(cities);
+const sphereKnnLookup = sphereKnn(locations);
 console.timeEnd(`index ${cities.length} points`);
@@ -35,3 +37,3 @@
 console.time(`${k} random queries of 1 closest`);
-for (i = 0; i < k; i++) sphereKnnLookup(randomPoints[i].lat, randomPoints[i].lon, 1);
+for (let i = 0; i < k; i++) sphereKnnLookup(randomPoints[i].lat, randomPoints[i].lon, 1);
 console.timeEnd(`${k} random queries of 1 closest`);

index.js

@@ -1,27 +0,19 @@
-'use strict';
 
-var tinyqueue = require('tinyqueue');
+import TinyQueue from 'tinyqueue';
 
-exports.around = around;
-exports.distance = distance;
+const earthRadius = 6371;
+const rad = Math.PI / 180;
 
-var earthRadius = 6371;
-var earthCircumference = 40007;
+export function around(index, lng, lat, maxResults = Infinity, maxDistance = Infinity, predicate) {
+    let maxHaverSinDist = 1;
+    const result = [];
 
-var rad = Math.PI / 180;
-
-function around(index, lng, lat, maxResults, maxDistance, predicate) {
-    var result = [];
-
     if (maxResults === undefined) maxResults = Infinity;
-    if (maxDistance === undefined) maxDistance = Infinity;
+    if (maxDistance !== undefined) maxHaverSinDist = haverSin(maxDistance / earthRadius);
 
-    var cosLat = Math.cos(lat * rad);
-    var sinLat = Math.sin(lat * rad);
-
     // a distance-sorted priority queue that will contain both points and kd-tree nodes
-    var q = tinyqueue(null, compareDist);
+    const q = new TinyQueue([], compareDist);
 
     // an object that represents the top kd-tree node (the whole Earth)
-    var node = {
+    let node = {
         left: 0, // left index in the kd-tree array
@@ -37,5 +29,7 @@ right: index.ids.length - 1, // right index
 
+    const cosLat = Math.cos(lat * rad);
+
     while (node) {
-        var right = node.right;
-        var left = node.left;
+        const right = node.right;
+        const left = node.left;
 
@@ -45,9 +39,7 @@ if (right - left <= index.nodeSize) { // leaf node
             // add all points of the leaf node to the queue
-            for (var i = left; i <= right; i++) {
-                var item = index.points[index.ids[i]];
-                if (!predicate || predicate(item)) {
-                    q.push({
-                        item: item,
-                        dist: greatCircleDist(lng, lat, index.coords[2 * i], index.coords[2 * i + 1], cosLat, sinLat)
-                    });
+            for (let i = left; i <= right; i++) {
+                const id = index.ids[i];
+                if (!predicate || predicate(id)) {
+                    const dist = haverSinDist(lng, lat, index.coords[2 * i], index.coords[2 * i + 1], cosLat);
+                    q.push({id, dist});
                 }
@@ -58,21 +50,18 @@ }
 
-            var m = (left + right) >> 1; // middle index
+            const m = (left + right) >> 1; // middle index
+            const midLng = index.coords[2 * m];
+            const midLat = index.coords[2 * m + 1];
 
-            var midLng = index.coords[2 * m];
-            var midLat = index.coords[2 * m + 1];
-
             // add middle point to the queue
-            item = index.points[index.ids[m]];
-            if (!predicate || predicate(item)) {
-                q.push({
-                    item: item,
-                    dist: greatCircleDist(lng, lat, midLng, midLat, cosLat, sinLat)
-                });
+            const id = index.ids[m];
+            if (!predicate || predicate(id)) {
+                const dist = haverSinDist(lng, lat, midLng, midLat, cosLat);
+                q.push({id, dist});
             }
 
-            var nextAxis = (node.axis + 1) % 2;
+            const nextAxis = (node.axis + 1) % 2;
 
             // first half of the node
-            var leftNode = {
-                left: left,
+            const leftNode = {
+                left,
                 right: m - 1,
@@ -87,5 +76,5 @@ axis: nextAxis,
             // second half of the node
-            var rightNode = {
+            const rightNode = {
                 left: m + 1,
-                right: right,
+                right,
                 axis: nextAxis,
@@ -99,4 +88,4 @@ minLng: node.axis === 0 ? midLng : node.minLng,
 
-            leftNode.dist = boxDist(lng, lat, leftNode, cosLat, sinLat);
-            rightNode.dist = boxDist(lng, lat, rightNode, cosLat, sinLat);
+            leftNode.dist = boxDist(lng, lat, cosLat, leftNode);
+            rightNode.dist = boxDist(lng, lat, cosLat, rightNode);
 
@@ -111,6 +100,6 @@ // add child nodes to the queue
         // since each node's distance is a lower bound of distances to its children
-        while (q.length && q.peek().item) {
-            var candidate = q.pop();
-            if (candidate.dist > maxDistance) return result;
-            result.push(candidate.item);
+        while (q.length && q.peek().id != null) {
+            const candidate = q.pop();
+            if (candidate.dist > maxHaverSinDist) return result;
+            result.push(candidate.id);
             if (result.length === maxResults) return result;
@@ -127,32 +116,29 @@ }
 // lower bound for distance from a location to points inside a bounding box
-function boxDist(lng, lat, node, cosLat, sinLat) {
-    var minLng = node.minLng;
-    var maxLng = node.maxLng;
-    var minLat = node.minLat;
-    var maxLat = node.maxLat;
+function boxDist(lng, lat, cosLat, node) {
+    const minLng = node.minLng;
+    const maxLng = node.maxLng;
+    const minLat = node.minLat;
+    const maxLat = node.maxLat;
 
     // query point is between minimum and maximum longitudes
     if (lng >= minLng && lng <= maxLng) {
-        if (lat <= minLat) return earthCircumference * (minLat - lat) / 360; // south
-        if (lat >= maxLat) return earthCircumference * (lat - maxLat) / 360; // north
-        return 0; // inside the bbox
+        if (lat < minLat) return haverSin((lat - minLat) * rad);
+        if (lat > maxLat) return haverSin((lat - maxLat) * rad);
+        return 0;
     }
 
     // query point is west or east of the bounding box;
-    // calculate the extremum for great circle distance from query point to the closest longitude
-    var closestLng = (minLng - lng + 360) % 360 <= (lng - maxLng + 360) % 360 ? minLng : maxLng;
-    var cosLngDelta = Math.cos((closestLng - lng) * rad);
-    var extremumLat = Math.atan(sinLat / (cosLat * cosLngDelta)) / rad;
+    // calculate the extremum for great circle distance from query point to the closest longitude;
+    const haverSinDLng = Math.min(haverSin((lng - minLng) * rad), haverSin((lng - maxLng) * rad));
+    const extremumLat = vertexLat(lat, haverSinDLng);
 
-    // calculate distances to lower and higher bbox corners and extremum (if it's within this range);
-    // one of the three distances will be the lower bound of great circle distance to bbox
-    var d = Math.max(
-        greatCircleDistPart(minLat, cosLat, sinLat, cosLngDelta),
-        greatCircleDistPart(maxLat, cosLat, sinLat, cosLngDelta));
-
+    // if extremum is inside the box, return the distance to it
     if (extremumLat > minLat && extremumLat < maxLat) {
-        d = Math.max(d, greatCircleDistPart(extremumLat, cosLat, sinLat, cosLngDelta));
+        return haverSinDistPartial(haverSinDLng, cosLat, lat, extremumLat);
     }
-
-    return earthRadius * Math.acos(d);
+    // otherwise return the distan e to one of the bbox corners (whichever is closest)
+    return Math.min(
+        haverSinDistPartial(haverSinDLng, cosLat, lat, minLat),
+        haverSinDistPartial(haverSinDLng, cosLat, lat, maxLat)
+    );
 }
@@ -164,17 +150,25 @@
 
-// distance using spherical law of cosines; should be precise enough for our needs
-function greatCircleDist(lng, lat, lng2, lat2, cosLat, sinLat) {
-    var cosLngDelta = Math.cos((lng2 - lng) * rad);
-    return earthRadius * Math.acos(greatCircleDistPart(lat2, cosLat, sinLat, cosLngDelta));
+function haverSin(theta) {
+    const s = Math.sin(theta / 2);
+    return s * s;
 }
 
-// partial greatCircleDist to reduce trigonometric calculations
-function greatCircleDistPart(lat, cosLat, sinLat, cosLngDelta) {
-    var d = sinLat * Math.sin(lat * rad) +
-            cosLat * Math.cos(lat * rad) * cosLngDelta;
-    return Math.min(d, 1);
+function haverSinDistPartial(haverSinDLng, cosLat1, lat1, lat2) {
+    return cosLat1 * Math.cos(lat2 * rad) * haverSinDLng + haverSin((lat1 - lat2) * rad);
 }
 
-function distance(lng, lat, lng2, lat2) {
-    return greatCircleDist(lng, lat, lng2, lat2, Math.cos(lat * rad), Math.sin(lat * rad));
+function haverSinDist(lng1, lat1, lng2, lat2, cosLat1) {
+    const haverSinDLng = haverSin((lng1 - lng2) * rad);
+    return haverSinDistPartial(haverSinDLng, cosLat1, lat1, lat2);
 }
+
+export function distance(lng1, lat1, lng2, lat2) {
+    const h = haverSinDist(lng1, lat1, lng2, lat2, Math.cos(lat1 * rad));
+    return 2 * earthRadius * Math.asin(Math.sqrt(h));
+}
+
+function vertexLat(lat, haverSinDLng) {
+    const cosDLng = 1 - 2 * haverSinDLng;
+    if (cosDLng <= 0) return lat > 0 ? 90 : -90;
+    return Math.atan(Math.tan(lat * rad) / cosDLng) / rad;
+}

package.json

 {
   "name": "geokdbush",
-  "version": "1.1.0",
+  "version": "2.0.0",
+  "type": "module",
   "main": "index.js",
@@ -8,20 +9,21 @@ "author": "Vladimir Agafonkin <[e-mail]>",
   "dependencies": {
-    "tinyqueue": "^1.2.2"
+    "tinyqueue": "^2.0.3"
   },
+  "repository": {
+    "type": "git",
+    "url": "https://github.com/mourner/geokdbush.git"
+  },
   "devDependencies": {
-    "all-the-cities": "2.0.0",
-    "eslint": "^3.17.1",
-    "eslint-config-mourner": "^2.0.1",
-    "kdbush": "^1.0.1",
-    "sphere-knn": "^1.3.1",
-    "tape": "^4.6.3"
+    "all-the-cities": "3.1.0",
+    "eslint": "^9.6.0",
+    "eslint-config-mourner": "^4.0.1",
+    "kdbush": "^4.0.2",
+    "sphere-knn": "^1.4.0",
+    "vptree": "^1.0.0"
   },
-  "eslintConfig": {
-    "extends": "mourner"
-  },
   "scripts": {
     "pretest": "eslint index.js test.js bench",
-    "test": "tape test.js",
-    "bench": "cd bench && node bench-geokdbush && node bench-sphere-knn && node bench-naive"
+    "test": "node test.js",
+    "bench": "cd bench && node bench-geokdbush && node bench-sphere-knn && node bench-naive && node bench-vptree"
   }
 }

README.md

@@ -1,4 +0,4 @@
-## geokdbush [![Build Status](https://travis-ci.org/mourner/geokdbush.svg?branch=master)](https://travis-ci.org/mourner/geokdbush)
+## geokdbush [![Node](https://github.com/mourner/geokdbush/actions/workflows/node.yml/badge.svg)](https://github.com/mourner/geokdbush/actions/workflows/node.yml) [![Simply Awesome](https://img.shields.io/badge/simply-awesome-brightgreen.svg)](https://github.com/mourner/projects)
 
-A geographic extension for [kdbush](https://github.com/mourner/kdbush),
+A geographic extension for [KDBush](https://github.com/mourner/kdbush),
 the fastest static spatial index for points in JavaScript.
@@ -13,8 +13,12 @@
 ```js
-var kdbush = require('kdbush');
-var geokdbush = require('geokdbush');
+import KDBush from 'kdbush';
+import * as geokdbush from 'geokdbush';
 
-var index = kdbush(points, (p) => p.lon, (p) => p.lat);
+const index = new KDBush(points.length);
+for (conts {lon, lat} of points) index.add(lon, lat);
+index.finish();
 
-var nearest = geokdbush.around(index, -119.7051, 34.4363, 1000);
+const nearestIds = geokdbush.around(index, -119.7051, 34.4363, 1000);
+
+const nearest = nearestIds.map(id => points[id]);
 ```
@@ -32,3 +36,3 @@
 - `maxResults`: (optional) maximum number of points to return (`Infinity` by default).
-- `maxDistance`: (optional) maximum distance to search within (`Infinity` by default).
+- `maxDistance`: (optional) maximum distance in kilometers to search within (`Infinity` by default).
 - `filterFn`: (optional) a function to filter the results with.
@@ -44,10 +48,10 @@
 The results below were obtained with `npm run bench`
-(Node v7.7.2, Macbook Pro 15 mid-2012).
+(Node v20, Macbook Pro 2020 M1 Pro).
 
 benchmark | geokdbush | sphere-knn | naive
 --- | ---: | ---: | ---:
-index 138398 points | 69ms | 967ms | n/a
-query 1000 closest | 4ms | 4ms | 155ms
-query 50000 closest | 31ms | 368ms | 155ms
-query all 138398 | 80ms | 29.7s | 155ms
-1000 queries of 1 | 55ms | 165ms | 18.4s
+index 138398 points | 57.6ms | 408ms | n/a
+query 1000 closest | 1.6ms | 1.8ms | 72ms
+query 50000 closest | 14.7ms | 91.5ms | 72ms
+query all 138398 | 33.7ms | 500ms | 72ms
+1000 queries of 1 | 24.7ms | 27.5ms | 11.1s

test.js

@@ -1,59 +0,53 @@
-'use strict';
+import test from 'node:test';
+import assert from 'node:assert/strict';
+import KDBush from 'kdbush';
+import cities from 'all-the-cities';
+import * as geokdbush from './index.js';
 
-var test = require('tape').test;
-var kdbush = require('kdbush');
-var cities = require('all-the-cities');
-var geokdbush = require('./');
+const index = new KDBush(cities.length);
+for (const {loc: {coordinates: [lon, lat]}} of cities) index.add(lon, lat);
+index.finish();
 
-var index = kdbush(cities, (p) => p.lon, (p) => p.lat);
+test('performs search according to maxResults', () => {
+    const points = geokdbush.around(index, -119.7051, 34.4363, 5);
 
-test('performs search according to maxResults', function (t) {
-    var points = geokdbush.around(index, -119.7051, 34.4363, 5);
-
-    t.same(points.map(p => p.name).join(', '), 'Mission Canyon, Santa Barbara, Montecito, Summerland, Goleta');
-
-    t.end();
+    assert.equal(points.map(id => cities[id].name).join(', '), 'Mission Canyon, Santa Barbara, Montecito, Summerland, Goleta');
 });
 
-test('performs search within maxDistance', function (t) {
-    var points = geokdbush.around(index, 30.5, 50.5, Infinity, 20);
+test('performs search within maxDistance', () => {
+    const points = geokdbush.around(index, 30.5, 50.5, Infinity, 20);
 
-    t.same(points.map(p => p.name).join(', '),
-        'Kiev, Vyshhorod, Kotsyubyns’ke, Sofiyivska Borschagivka, Vyshneve, Kriukivschina, Irpin’, Hostomel’, Khotiv');
-
-    t.end();
+    assert.equal(points.map(id => cities[id].name).join(', '),
+        'Kyiv, Vyshhorod, Pohreby, Kotsyubyns’ke, Horenka, Sofiyivska Borschagivka, Novi Petrivtsi, Vyshneve, Kriukivschina, Irpin, Hostomel, Chabany, Khotiv, Pukhivka');
 });
 
-test('performs search using filter function', function (t) {
-    var points = geokdbush.around(index, 30.5, 50.5, 10, Infinity, p => p.population > 1000000);
+test('performs search using filter function', () => {
+    const points = geokdbush.around(index, 30.5, 50.5, 10, Infinity, id => cities[id].population > 200000 && cities[id].country === 'UA');
 
-    t.same(points.map(p => p.name).join(', '),
-        'Kiev, Dnipropetrovsk, Kharkiv, Minsk, Odessa, Donets’k, Warsaw, Bucharest, Moscow, Rostov-na-Donu');
-
-    t.end();
+    assert.equal(points.map(id => cities[id].name).join(', '),
+        'Kyiv, Chernihiv, Zhytomyr, Cherkasy, Vinnytsia, Kropyvnytskyi, Kremenchuk, Khmelnytskyi, Rivne, Poltava');
 });
 
-test('performs exhaustive search in correct order', function (t) {
-    var points = geokdbush.around(index, 30.5, 50.5);
+test('performs exhaustive search in correct order', () => {
+    const points = geokdbush.around(index, 30.5, 50.5);
 
-    var c = {lon: 30.5, lat: 50.5};
-    var sorted = cities
-        .map((item) => ({item: item, dist: geokdbush.distance(c.lon, c.lat, item.lon, item.lat)}))
+    const lon = 30.5;
+    const lat = 50.5;
+    const sorted = cities
+        .map(({loc: {coordinates: [plon, plat]}}, id) => ({id, dist: geokdbush.distance(lon, lat, plon, plat)}))
         .sort((a, b) => a.dist - b.dist);
 
-    for (var i = 0; i < sorted.length; i++) {
-        var dist = geokdbush.distance(points[i].lon, points[i].lat, c.lon, c.lat);
+    for (let i = 0; i < sorted.length; i++) {
+        const [plon, plat] = cities[points[i]].loc.coordinates;
+        const dist = geokdbush.distance(plon, plat, lon, lat);
         if (dist !== sorted[i].dist) {
-            t.fail(points[i].name + ' vs ' + sorted[i].item.name);
+            assert.fail(`${cities[points[i]].name  } vs ${  cities[sorted[i].id].name}`);
             break;
         }
     }
-    t.pass('all points in correct order');
-
-    t.end();
+    // all points in correct order
 });
 
-test('calculates great circle distance', function (t) {
-    t.equal(10131.7396, Math.round(1e4 * geokdbush.distance(30.5, 50.5, -119.7, 34.4)) / 1e4);
-    t.end();
+test('calculates great circle distance', () => {
+    assert.equal(10131.7396, Math.round(1e4 * geokdbush.distance(30.5, 50.5, -119.7, 34.4)) / 1e4);
 });

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

No repository

Supply chain risk

Package does not have a linked source code repository. Without this field, a package will have no reference to the location of the source code use to generate the package.

Found 1 instance in 1 package

Improved metrics

Lines of code

311

increased by9.89%

Number of lines in readme file

55

increased by7.84%

Number of low supply chain risk alerts

0

decreased by-100%

Is type module

Yes

Worsened metrics

Total package byte prevSize

17017

decreased by-78.2%

Number of package files

11

decreased by-15.38%

Number of medium supply chain risk alerts

1

increased byInfinity%

Dependency changes

• + Addedtinyqueue@2.0.3(transitive)

• - Removedtinyqueue@1.2.3(transitive)

• Updatedtinyqueue@^2.0.3