geo-tree - npm Package Compare versions

Comparing version 0.1.1 to 0.1.2

package.json

 {
   "name": "geo-tree",
-  "version": "0.1.1",
+  "version": "0.1.2",
   "description": "High performance library for map-related operations",
@@ -5,0 +5,0 @@ "export-symbol": "GeoTree",

README.md

@@ -230,2 +230,3 @@ # Geo-tree library
 * 0.1.0 (2014-09-04): initial version (`insert`, `find` and `forEach` operations)
-* 0.1.0 (2014-09-16): support for m/km/yd/mi radius value for circle-search operation
+* 0.1.1 (2014-09-16): support for m/km/yd/mi radius value for circle-search operation
+* 0.1.2 (2014-10-12): Haversine function for radius verifications

src/geo-tree.js

@@ -18,4 +18,10 @@ // geo-tree implementation (using red-black tree and z-curve)
 
-// WARNING: the conversion will work well only for small distances
-function convertToAngle(lat, val, units) {
+function getValidationFn(center, dist, units) {
+
+  function toDeg(rad) { return rad * 180.0 / Math.PI; }
+  function toRad(deg) { return deg * Math.PI / 180.0; }
+
+  // mean Earth radius (http://en.wikipedia.org/wiki/Earth_radius#Mean_radius)
+  var R = 6371009.0;  // in meters
+  // meter to X
   var conversionTable = [
@@ -27,8 +33,37 @@ { units: 'm', ratio: 1.0 },
   ];
+
   for (var i = 0; i < conversionTable.length; i++) {
     if (conversionTable[i].units === units) { break; }
   }
-  if (conversionTable.length === i) { return val; }
-  var angle = (val * conversionTable[i].ratio) / (6378137.0 * Math.cos(Math.PI * lat / 180.0));
-  return angle * 180.0 / Math.PI;
+
+  // in angle degrees already
+  if (conversionTable.length === i) {
+    var radius2 = dist * dist;
+    return {
+      angle: dist,
+      validate: function(coord) {
+        var dlat = center.lat - coord.lat;
+        var dlng = center.lng - coord.lng;
+        return (dlat * dlat + dlng * dlng <= radius2);
+      }
+    };
+  }
+
+  // distance-based
+  var adjustedDist = dist * conversionTable[i].ratio;  // in meters
+  return {
+    angle: toDeg(adjustedDist / (R * Math.cos(toRad(center.lat)))),
+    validate: function(coord) {
+      // Haversine algo (http://mathforum.org/library/drmath/view/51879.html)
+      var dlat = toRad(center.lat - coord.lat);
+      var dlng = toRad(center.lng - coord.lng);
+      var sin_dlat_2 = Math.sin(dlat/2);
+      var sin_dlng_2 = Math.sin(dlng/2);
+      var cos_ce_lat = Math.cos(toRad(center.lat));
+      var cos_co_lat = Math.cos(toRad(coord.lat));
+      var a = sin_dlat_2 * sin_dlat_2 + cos_ce_lat * cos_co_lat * sin_dlng_2 * sin_dlng_2;
+      var c = 2 * Math.atan2(Math.sqrt(a), Math.sqrt(1-a));
+      return (R * c <= adjustedDist);
+    }
+  };
 }
@@ -77,6 +112,10 @@
 GeoTree.prototype.find = function(arg1, arg2, arg3) {
-  var all, radius;
+  var all, radius, validate;
   all = (0 === arguments.length);
   if (undefined === arg2) { arg2 = arg1; }
-  if ('number' === typeof(arg2)) { radius = convertToAngle(arg1.lat, arg2, arg3); }
+  if ('number' === typeof(arg2)) {
+    var _tmp = getValidationFn(arg1, arg2, arg3);
+    radius = _tmp.angle;
+    validate = _tmp.validate;
+  }
   var minLat, maxLat, minLng, maxLng, minIdx = -Infinity, maxIdx = Infinity;
@@ -118,8 +157,5 @@ if (!all) {
       // circle
-      var radius2 = radius * radius;
       for (i = 0; i < candidates.length; i++) {
         item = candidates[i];
-        lat = arg1.lat - item.lat;
-        lng = arg1.lng - item.lng;
-        if (lat * lat + lng * lng <= radius2) { res.push(item.data); }
+        if (validate(item)) { res.push(item.data); }
       }
@@ -126,0 +162,0 @@ }

test/benchmark.js

@@ -86,1 +86,24 @@ // Usage: node benchmark
 } } }
+
+console.log('\n------------------------------------------------------------\n');
+
+var res;
+ts_start = new Date();
+res = tree.find({lat: 0.0, lng: 0.0}, 5.0);
+ts_end = new Date();
+console.log('find({ lat: 0.0, lng: 0.0 }, 5.0): ' + (ts_end - ts_start) + 'ms, res.length: ' + res.length);
+ts_start = new Date();
+res = tree.find({lat: 0.0, lng: 0.0}, 556.6, 'km');
+ts_end = new Date();
+console.log('find({ lat: 0.0, lng: 0.0 }, 556.6, "km"): ' + (ts_end - ts_start) + 'ms, res.length: ' + res.length);
+
+console.log('\n');
+
+ts_start = new Date();
+res = tree.find({lat: 50.0, lng: 0.0}, 5.0);
+ts_end = new Date();
+console.log('find({ lat: 50.0, lng: 0.0 }, 5.0): ' + (ts_end - ts_start) + 'ms, res.length: ' + res.length);
+ts_start = new Date();
+res = tree.find({lat: 50.0, lng: 0.0}, 556.6, 'km');
+ts_end = new Date();
+console.log('find({ lat: 50.0, lng: 0.0 }, 556.6, "km"): ' + (ts_end - ts_start) + 'ms, res.length: ' + res.length);

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

Minified code

Quality

This package contains minified code. This may be harmless in some cases where minified code is included in packaged libraries, however packages on npm should not minify code.

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

Minified code

Quality

This package contains minified code. This may be harmless in some cases where minified code is included in packaged libraries, however packages on npm should not minify code.

Found 1 instance in 1 package

Improved metrics

Total package byte prevSize

80348

increased by6.74%

Lines of code

1303

increased by7.15%

Number of lines in readme file

232

increased by0.43%

No dependency changes