justinethier / node-kdtree Goto Github PK

View Code? Open in Web Editor NEW

58.0 5.0 60.0 116 KB

A node.js add-on for performing efficient Nearest Neighbor searches using libkdtree.

Home Page: http://justinethier.github.com/node-kdtree

License: MIT License

Makefile 0.89% Python 0.52% C 60.99% C++ 26.13% JavaScript 11.47%

c nodejs kd-tree

node-kdtree's Introduction

#node-kdtree

node-kdtree is a node.js addon that defines a wrapper to libkdtree, allowing one to work with KD trees directly in node. A KD tree is a data structure that organizes points in a multi-dimensional space, and in particular is useful for performing efficient nearest neighbor searches.

Dependencies

The kdtree C library is required. In order to install, get the latest version from here and run the following commands:

./configure
make
sudo make install PREFIX=/usr

Installation

The easiest way to install node-kdtree is to use the npm package manager:

npm install kdtree

Usage

###Creating a tree You may create a tree by instantiating a new KDTree object:

var kd = require('kdtree');
var tree = new kd.KDTree(3); // A new tree for 3-dimensional points

When creating a new tree we can specify the dimensions of the data. For example, a three-dimensional tree will contain points of the form (x, y, z). If a dimension is not specified, the tree defaults to three dimensions.

###Adding data to a tree Data may be added to the tree using the insert method:

tree.insert(1, 2, 3);
tree.insert(10, 20, 30);

There must be one argument for each dimension of the data - for example, a three dimensional tree would have three arguments to insert. An optional data parameter may also be specified to store a data value alongside the point data:

tree.insert(39.285785, -76.610262, "USS Constellation");

###Nearest neighbor searches The nearest method is used to find the point in the tree that is closest to a target point. For example:

> tree.nearest(39.273889, -76.738056);
[39.272051, -76.731917, "Bill's Music, Inc."]

nearest will return an array containing closest point, or an empty array if no points were found. As shown above, if the point contains a data value, that value will also be returned at the end of the array.

A nearestRange method is also provided, which allows us to find all of the points within a given range. For example:

> tree.nearestRange(0, 0, 3);
[ [ 1, 1 ],
  [ 0, 2 ],
  [ 2, 0 ],
  [ 1, 0 ],
  [ 0, 1 ],
  [ 0, 0 ] ]

The first arguments to nearestRange are the components of the point to begin searching at. The last argument is the search range.

##API

API documentation

##Credits

node-kdtree is developed by Justin Ethier.

Thanks to John Tsiombikas for developing libkdtree!

Patches are welcome; please send via pull request on github.

node-kdtree's People

Contributors

Stargazers

Watchers

Forkers

uberscientist thehazzard luk- jupiter ptre xadillax imclab antiveeranna benedictchen nowelec hailiang-wang heidric vivihoo03 javajon

node-kdtree's Issues

Performance drop since 0.12

We've found a performance drop in our production code when migrating to node 0.12.
Here is a benchmark that reproduces it:

var kd = require('kdtree');
var Benchmark = require('benchmark');

var tree = new kd.KDTree(2);

tree.insert(48, 2, 'France');
tree.insert(48.856614, 2.352221948, 'Paris');
tree.insert(47.872834, -3.920734, 'Concarneau');

var suite = new Benchmark.Suite();
suite.add('Concarneau', function() {
    tree.nearest(47.8, -3.9)
})
suite.add('Paris', function() {
    tree.nearest(65, 15)
})
.on('cycle', function(event) {
    console.log(String(event.target));
})
.run({ 'async': true });

On node 0.10.24 (tested on 0.10.39 with similar results)

Concarneau x 709,237 ops/sec ±1.78% (88 runs sampled)
Paris x 682,274 ops/sec ±1.51% (89 runs sampled)

On node 0.12.6 (tested on 0.12.0 with similar results)

Concarneau x 421,800 ops/sec ±2.06% (88 runs sampled)
Paris x 424,481 ops/sec ±3.29% (93 runs sampled)

Any idea on the matter?

Fails to install on node 12.11

> [email protected] install /home/lis/work/Elomia/server/node_modules/kdtree
> node-gyp rebuild

make: Entering directory '/home/lis/work/Elomia/server/node_modules/kdtree/build'
  CC(target) Release/obj.target/kdtree/src/lib/kdtree.o
  CXX(target) Release/obj.target/kdtree/src/node-kdtree.o
In file included from ../node_modules/nan/nan.h:190:0,
                 from ../src/node-kdtree.cc:15:
../node_modules/nan/nan_maybe_43_inl.h: In function ‘Nan::Maybe<bool> Nan::ForceSet(v8::Local<v8::Object>, v8::Local<v8::Value>, v8::Local<v8::Value>, v8::PropertyAttribute)’:
../node_modules/nan/nan_maybe_43_inl.h:88:15: error: ‘class v8::Object’ has no member named ‘ForceSet’
   return obj->ForceSet(GetCurrentContext(), key, value, attribs);
               ^~~~~~~~
In file included from ../node_modules/nan/nan_converters.h:59:0,
                 from ../node_modules/nan/nan.h:195,
                 from ../src/node-kdtree.cc:15:
../node_modules/nan/nan_converters_43_inl.h: In static member function ‘static Nan::imp::ToFactoryBase<v8::Boolean>::return_t Nan::imp::ToFactory<v8::Boolean>::convert(v8::Local<v8::Value>)’:
../node_modules/nan/nan_converters_43_inl.h:15:45: warning: ‘v8::MaybeLocal<v8::Boolean> v8::Value::ToBoolean(v8::Local<v8::Context>) const’ is deprecated: ToBoolean can never throw. Use Local version. [-Wdeprecated-declarations]
   return val->To ## TYPE(GetCurrentContext());                                 \
                                             ^
../node_modules/nan/nan_converters_43_inl.h:18:1: note: in expansion of macro ‘X’
 X(Boolean)
 ^
In file included from /home/lis/.cache/node-gyp/12.11.0/include/node/v8-internal.h:14:0,
                 from /home/lis/.cache/node-gyp/12.11.0/include/node/v8.h:25,
                 from ../src/node-kdtree.cc:9:
/home/lis/.cache/node-gyp/12.11.0/include/node/v8.h:2568:59: note: declared here
                 V8_WARN_UNUSED_RESULT MaybeLocal<Boolean> ToBoolean(
                                                           ^
/home/lis/.cache/node-gyp/12.11.0/include/node/v8config.h:311:3: note: in definition of macro ‘V8_DEPRECATED’
   declarator __attribute__((deprecated(message)))
   ^~~~~~~~~~
In file included from ../node_modules/nan/nan_converters.h:59:0,
                 from ../node_modules/nan/nan.h:195,
                 from ../src/node-kdtree.cc:15:
../node_modules/nan/nan_converters_43_inl.h: In static member function ‘static Nan::imp::ValueFactoryBase<bool>::return_t Nan::imp::ToFactory<bool>::convert(v8::Local<v8::Value>)’:
../node_modules/nan/nan_converters_43_inl.h:31:48: warning: ‘v8::Maybe<bool> v8::Value::BooleanValue(v8::Local<v8::Context>) const’ is deprecated: BooleanValue can never throw. Use Isolate version. [-Wdeprecated-declarations]
   return val->NAME ## Value(GetCurrentContext());                              \
                                                ^
../node_modules/nan/nan_converters_43_inl.h:34:1: note: in expansion of macro ‘X’
 X(bool, Boolean)
 ^
In file included from /home/lis/.cache/node-gyp/12.11.0/include/node/v8-internal.h:14:0,
                 from /home/lis/.cache/node-gyp/12.11.0/include/node/v8.h:25,
                 from ../src/node-kdtree.cc:9:
/home/lis/.cache/node-gyp/12.11.0/include/node/v8.h:2606:51: note: declared here
                 V8_WARN_UNUSED_RESULT Maybe<bool> BooleanValue(
                                                   ^
/home/lis/.cache/node-gyp/12.11.0/include/node/v8config.h:311:3: note: in definition of macro ‘V8_DEPRECATED’
   declarator __attribute__((deprecated(message)))
   ^~~~~~~~~~
In file included from ../node_modules/nan/nan_new.h:189:0,
                 from ../node_modules/nan/nan.h:196,
                 from ../src/node-kdtree.cc:15:
../node_modules/nan/nan_implementation_12_inl.h: In static member function ‘static Nan::imp::FactoryBase<v8::Function>::return_t Nan::imp::Factory<v8::Function>::New(Nan::FunctionCallback, v8::Local<v8::Value>)’:
../node_modules/nan/nan_implementation_12_inl.h:109:32: error: no matching function for call to ‘v8::Function::New(v8::Isolate*&, void (&)(const v8::FunctionCallbackInfo<v8::Value>&), v8::Local<v8::Object>&)’
                           , obj));
                                ^
In file included from ../src/node-kdtree.cc:9:0:
/home/lis/.cache/node-gyp/12.11.0/include/node/v8.h:4170:31: note: candidate: static v8::MaybeLocal<v8::Function> v8::Function::New(v8::Local<v8::Context>, v8::FunctionCallback, v8::Local<v8::Value>, int, v8::ConstructorBehavior, v8::SideEffectType)
   static MaybeLocal<Function> New(
                               ^~~
/home/lis/.cache/node-gyp/12.11.0/include/node/v8.h:4170:31: note:   no known conversion for argument 1 from ‘v8::Isolate*’ to ‘v8::Local<v8::Context>’
In file included from ../node_modules/nan/nan_new.h:189:0,
                 from ../node_modules/nan/nan.h:196,
                 from ../src/node-kdtree.cc:15:
../node_modules/nan/nan_implementation_12_inl.h: In static member function ‘static Nan::imp::FactoryBase<v8::StringObject>::return_t Nan::imp::Factory<v8::StringObject>::New(v8::Local<v8::String>)’:
../node_modules/nan/nan_implementation_12_inl.h:345:37: error: no matching function for call to ‘v8::StringObject::New(v8::Local<v8::String>&)’
   return v8::StringObject::New(value).As<v8::StringObject>();
                                     ^
In file included from ../src/node-kdtree.cc:9:0:
/home/lis/.cache/node-gyp/12.11.0/include/node/v8.h:5426:23: note: candidate: static v8::Local<v8::Value> v8::StringObject::New(v8::Isolate*, v8::Local<v8::String>)
   static Local<Value> New(Isolate* isolate, Local<String> value);
                       ^~~
/home/lis/.cache/node-gyp/12.11.0/include/node/v8.h:5426:23: note:   candidate expects 2 arguments, 1 provided
In file included from ../node_modules/nan/nan_new.h:189:0,
                 from ../node_modules/nan/nan.h:196,
                 from ../src/node-kdtree.cc:15:
../node_modules/nan/nan_implementation_12_inl.h:345:58: error: expected primary-expression before ‘>’ token
   return v8::StringObject::New(value).As<v8::StringObject>();
                                                          ^
../node_modules/nan/nan_implementation_12_inl.h:345:60: error: expected primary-expression before ‘)’ token
   return v8::StringObject::New(value).As<v8::StringObject>();
                                                            ^
In file included from ../src/node-kdtree.cc:15:0:
../node_modules/nan/nan.h: In function ‘v8::Local<v8::Value> Nan::MakeCallback(v8::Local<v8::Object>, v8::Local<v8::Function>, int, v8::Local<v8::Value>*)’:
../node_modules/nan/nan.h:817:60: warning: ‘v8::Local<v8::Value> node::MakeCallback(v8::Isolate*, v8::Local<v8::Object>, v8::Local<v8::Function>, int, v8::Local<v8::Value>*)’ is deprecated: Use MakeCallback(..., async_context) [-Wdeprecated-declarations]
         v8::Isolate::GetCurrent(), target, func, argc, argv);
                                                            ^
In file included from ../src/node-kdtree.cc:10:0:
/home/lis/.cache/node-gyp/12.11.0/include/node/node.h:174:50: note: declared here
                 NODE_EXTERN v8::Local<v8::Value> MakeCallback(
                                                  ^
/home/lis/.cache/node-gyp/12.11.0/include/node/node.h:93:42: note: in definition of macro ‘NODE_DEPRECATED’
     __attribute__((deprecated(message))) declarator
                                          ^~~~~~~~~~
In file included from ../src/node-kdtree.cc:15:0:
../node_modules/nan/nan.h: In function ‘v8::Local<v8::Value> Nan::MakeCallback(v8::Local<v8::Object>, v8::Local<v8::String>, int, v8::Local<v8::Value>*)’:
../node_modules/nan/nan.h:831:62: warning: ‘v8::Local<v8::Value> node::MakeCallback(v8::Isolate*, v8::Local<v8::Object>, v8::Local<v8::String>, int, v8::Local<v8::Value>*)’ is deprecated: Use MakeCallback(..., async_context) [-Wdeprecated-declarations]
         v8::Isolate::GetCurrent(), target, symbol, argc, argv);
                                                              ^
In file included from ../src/node-kdtree.cc:10:0:
/home/lis/.cache/node-gyp/12.11.0/include/node/node.h:167:50: note: declared here
                 NODE_EXTERN v8::Local<v8::Value> MakeCallback(
                                                  ^
/home/lis/.cache/node-gyp/12.11.0/include/node/node.h:93:42: note: in definition of macro ‘NODE_DEPRECATED’
     __attribute__((deprecated(message))) declarator
                                          ^~~~~~~~~~
In file included from ../src/node-kdtree.cc:15:0:
../node_modules/nan/nan.h: In function ‘v8::Local<v8::Value> Nan::MakeCallback(v8::Local<v8::Object>, const char*, int, v8::Local<v8::Value>*)’:
../node_modules/nan/nan.h:845:62: warning: ‘v8::Local<v8::Value> node::MakeCallback(v8::Isolate*, v8::Local<v8::Object>, const char*, int, v8::Local<v8::Value>*)’ is deprecated: Use MakeCallback(..., async_context) [-Wdeprecated-declarations]
         v8::Isolate::GetCurrent(), target, method, argc, argv);
                                                              ^
In file included from ../src/node-kdtree.cc:10:0:
/home/lis/.cache/node-gyp/12.11.0/include/node/node.h:160:50: note: declared here
                 NODE_EXTERN v8::Local<v8::Value> MakeCallback(
                                                  ^
/home/lis/.cache/node-gyp/12.11.0/include/node/node.h:93:42: note: in definition of macro ‘NODE_DEPRECATED’
     __attribute__((deprecated(message))) declarator
                                          ^~~~~~~~~~
In file included from ../src/node-kdtree.cc:15:0:
../node_modules/nan/nan.h: In constructor ‘Nan::Utf8String::Utf8String(v8::Local<v8::Value>)’:
../node_modules/nan/nan.h:890:53: error: no matching function for call to ‘v8::Value::ToString()’
       v8::Local<v8::String> string = from->ToString();
                                                     ^
In file included from ../src/node-kdtree.cc:9:0:
/home/lis/.cache/node-gyp/12.11.0/include/node/v8.h:2572:44: note: candidate: v8::MaybeLocal<v8::String> v8::Value::ToString(v8::Local<v8::Context>) const
   V8_WARN_UNUSED_RESULT MaybeLocal<String> ToString(
                                            ^~~~~~~~
/home/lis/.cache/node-gyp/12.11.0/include/node/v8.h:2572:44: note:   candidate expects 1 argument, 0 provided
In file included from /home/lis/.cache/node-gyp/12.11.0/include/node/v8-internal.h:14:0,
                 from /home/lis/.cache/node-gyp/12.11.0/include/node/v8.h:25,
                 from ../src/node-kdtree.cc:9:
/home/lis/.cache/node-gyp/12.11.0/include/node/v8.h:2588:31: note: candidate: v8::Local<v8::String> v8::Value::ToString(v8::Isolate*) const
                 Local<String> ToString(Isolate* isolate) const);
                               ^
/home/lis/.cache/node-gyp/12.11.0/include/node/v8config.h:311:3: note: in definition of macro ‘V8_DEPRECATED’
   declarator __attribute__((deprecated(message)))
   ^~~~~~~~~~
/home/lis/.cache/node-gyp/12.11.0/include/node/v8.h:2588:31: note:   candidate expects 1 argument, 0 provided
                 Local<String> ToString(Isolate* isolate) const);
                               ^
/home/lis/.cache/node-gyp/12.11.0/include/node/v8config.h:311:3: note: in definition of macro ‘V8_DEPRECATED’
   declarator __attribute__((deprecated(message)))
   ^~~~~~~~~~
In file included from ../src/node-kdtree.cc:15:0:
../node_modules/nan/nan.h:900:74: error: no matching function for call to ‘v8::String::WriteUtf8(char*&, int, int, const int&)’
         length_ = string->WriteUtf8(str_, static_cast<int>(len), 0, flags);
                                                                          ^
In file included from ../src/node-kdtree.cc:9:0:
/home/lis/.cache/node-gyp/12.11.0/include/node/v8.h:2782:7: note: candidate: int v8::String::WriteUtf8(v8::Isolate*, char*, int, int*, int) const
   int WriteUtf8(Isolate* isolate, char* buffer, int length = -1,
       ^~~~~~~~~
/home/lis/.cache/node-gyp/12.11.0/include/node/v8.h:2782:7: note:   no known conversion for argument 1 from ‘char*’ to ‘v8::Isolate*’
In file included from ../src/node-kdtree.cc:15:0:
../node_modules/nan/nan.h: In member function ‘v8::Local<v8::Value> Nan::Callback::Call_(v8::Isolate*, v8::Local<v8::Object>, int, v8::Local<v8::Value>*) const’:
../node_modules/nan/nan.h:1453:5: warning: ‘v8::Local<v8::Value> node::MakeCallback(v8::Isolate*, v8::Local<v8::Object>, v8::Local<v8::Function>, int, v8::Local<v8::Value>*)’ is deprecated: Use MakeCallback(..., async_context) [-Wdeprecated-declarations]
     ));
     ^
In file included from ../src/node-kdtree.cc:10:0:
/home/lis/.cache/node-gyp/12.11.0/include/node/node.h:174:50: note: declared here
                 NODE_EXTERN v8::Local<v8::Value> MakeCallback(
                                                  ^
/home/lis/.cache/node-gyp/12.11.0/include/node/node.h:93:42: note: in definition of macro ‘NODE_DEPRECATED’
     __attribute__((deprecated(message))) declarator
                                          ^~~~~~~~~~
In file included from ../src/node-kdtree.cc:15:0:
../node_modules/nan/nan.h: In member function ‘void Nan::AsyncWorker::SaveToPersistent(const char*, const v8::Local<v8::Value>&)’:
../node_modules/nan/nan.h:1507:64: warning: ‘bool v8::Object::Set(v8::Local<v8::Value>, v8::Local<v8::Value>)’ is deprecated: Use maybe version [-Wdeprecated-declarations]
     New(persistentHandle)->Set(New(key).ToLocalChecked(), value);
                                                                ^
In file included from /home/lis/.cache/node-gyp/12.11.0/include/node/v8-internal.h:14:0,
                 from /home/lis/.cache/node-gyp/12.11.0/include/node/v8.h:25,
                 from ../src/node-kdtree.cc:9:
/home/lis/.cache/node-gyp/12.11.0/include/node/v8.h:3403:22: note: declared here
                 bool Set(Local<Value> key, Local<Value> value));
                      ^
/home/lis/.cache/node-gyp/12.11.0/include/node/v8config.h:311:3: note: in definition of macro ‘V8_DEPRECATED’
   declarator __attribute__((deprecated(message)))
   ^~~~~~~~~~
In file included from ../src/node-kdtree.cc:15:0:
../node_modules/nan/nan.h: In member function ‘void Nan::AsyncWorker::SaveToPersistent(const v8::Local<v8::String>&, const v8::Local<v8::Value>&)’:
../node_modules/nan/nan.h:1513:42: warning: ‘bool v8::Object::Set(v8::Local<v8::Value>, v8::Local<v8::Value>)’ is deprecated: Use maybe version [-Wdeprecated-declarations]
     New(persistentHandle)->Set(key, value);
                                          ^
In file included from /home/lis/.cache/node-gyp/12.11.0/include/node/v8-internal.h:14:0,
                 from /home/lis/.cache/node-gyp/12.11.0/include/node/v8.h:25,
                 from ../src/node-kdtree.cc:9:
/home/lis/.cache/node-gyp/12.11.0/include/node/v8.h:3403:22: note: declared here
                 bool Set(Local<Value> key, Local<Value> value));
                      ^
/home/lis/.cache/node-gyp/12.11.0/include/node/v8config.h:311:3: note: in definition of macro ‘V8_DEPRECATED’
   declarator __attribute__((deprecated(message)))
   ^~~~~~~~~~
In file included from ../src/node-kdtree.cc:15:0:
../node_modules/nan/nan.h: In member function ‘void Nan::AsyncWorker::SaveToPersistent(uint32_t, const v8::Local<v8::Value>&)’:
../node_modules/nan/nan.h:1519:44: warning: ‘bool v8::Object::Set(uint32_t, v8::Local<v8::Value>)’ is deprecated: Use maybe version [-Wdeprecated-declarations]
     New(persistentHandle)->Set(index, value);
                                            ^
In file included from /home/lis/.cache/node-gyp/12.11.0/include/node/v8-internal.h:14:0,
                 from /home/lis/.cache/node-gyp/12.11.0/include/node/v8.h:25,
                 from ../src/node-kdtree.cc:9:
/home/lis/.cache/node-gyp/12.11.0/include/node/v8.h:3412:22: note: declared here
                 bool Set(uint32_t index, Local<Value> value));
                      ^
/home/lis/.cache/node-gyp/12.11.0/include/node/v8config.h:311:3: note: in definition of macro ‘V8_DEPRECATED’
   declarator __attribute__((deprecated(message)))
   ^~~~~~~~~~
In file included from ../src/node-kdtree.cc:15:0:
../node_modules/nan/nan.h: In member function ‘v8::Local<v8::Value> Nan::AsyncWorker::GetFromPersistent(const char*) const’:
../node_modules/nan/nan.h:1525:61: warning: ‘v8::Local<v8::Value> v8::Object::Get(v8::Local<v8::Value>)’ is deprecated: Use maybe version [-Wdeprecated-declarations]
         New(persistentHandle)->Get(New(key).ToLocalChecked()));
                                                             ^
In file included from /home/lis/.cache/node-gyp/12.11.0/include/node/v8-internal.h:14:0,
                 from /home/lis/.cache/node-gyp/12.11.0/include/node/v8.h:25,
                 from ../src/node-kdtree.cc:9:
/home/lis/.cache/node-gyp/12.11.0/include/node/v8.h:3457:51: note: declared here
   V8_DEPRECATED("Use maybe version", Local<Value> Get(Local<Value> key));
                                                   ^
/home/lis/.cache/node-gyp/12.11.0/include/node/v8config.h:311:3: note: in definition of macro ‘V8_DEPRECATED’
   declarator __attribute__((deprecated(message)))
   ^~~~~~~~~~
In file included from ../src/node-kdtree.cc:15:0:
../node_modules/nan/nan.h: In member function ‘v8::Local<v8::Value> Nan::AsyncWorker::GetFromPersistent(const v8::Local<v8::String>&) const’:
../node_modules/nan/nan.h:1531:55: warning: ‘v8::Local<v8::Value> v8::Object::Get(v8::Local<v8::Value>)’ is deprecated: Use maybe version [-Wdeprecated-declarations]
     return scope.Escape(New(persistentHandle)->Get(key));
                                                       ^
In file included from /home/lis/.cache/node-gyp/12.11.0/include/node/v8-internal.h:14:0,
                 from /home/lis/.cache/node-gyp/12.11.0/include/node/v8.h:25,
                 from ../src/node-kdtree.cc:9:
/home/lis/.cache/node-gyp/12.11.0/include/node/v8.h:3457:51: note: declared here
   V8_DEPRECATED("Use maybe version", Local<Value> Get(Local<Value> key));
                                                   ^
/home/lis/.cache/node-gyp/12.11.0/include/node/v8config.h:311:3: note: in definition of macro ‘V8_DEPRECATED’
   declarator __attribute__((deprecated(message)))
   ^~~~~~~~~~
In file included from ../src/node-kdtree.cc:15:0:
../node_modules/nan/nan.h: In member function ‘v8::Local<v8::Value> Nan::AsyncWorker::GetFromPersistent(uint32_t) const’:
../node_modules/nan/nan.h:1536:57: warning: ‘v8::Local<v8::Value> v8::Object::Get(uint32_t)’ is deprecated: Use maybe version [-Wdeprecated-declarations]
     return scope.Escape(New(persistentHandle)->Get(index));
                                                         ^
In file included from /home/lis/.cache/node-gyp/12.11.0/include/node/v8-internal.h:14:0,
                 from /home/lis/.cache/node-gyp/12.11.0/include/node/v8.h:25,
                 from ../src/node-kdtree.cc:9:
/home/lis/.cache/node-gyp/12.11.0/include/node/v8.h:3461:51: note: declared here
   V8_DEPRECATED("Use maybe version", Local<Value> Get(uint32_t index));
                                                   ^
/home/lis/.cache/node-gyp/12.11.0/include/node/v8config.h:311:3: note: in definition of macro ‘V8_DEPRECATED’
   declarator __attribute__((deprecated(message)))
   ^~~~~~~~~~
In file included from /usr/include/c++/7/cassert:44:0,
                 from /home/lis/.cache/node-gyp/12.11.0/include/node/node_object_wrap.h:26,
                 from ../node_modules/nan/nan.h:49,
                 from ../src/node-kdtree.cc:15:
../node_modules/nan/nan_object_wrap.h: In destructor ‘virtual Nan::ObjectWrap::~ObjectWrap()’:
../node_modules/nan/nan_object_wrap.h:24:25: error: ‘class Nan::Persistent<v8::Object>’ has no member named ‘IsNearDeath’
     assert(persistent().IsNearDeath());
                         ^
In file included from ../node_modules/nan/nan.h:2190:0,
                 from ../src/node-kdtree.cc:15:
../node_modules/nan/nan_object_wrap.h: In member function ‘void Nan::ObjectWrap::MakeWeak()’:
../node_modules/nan/nan_object_wrap.h:67:34: warning: ‘void v8::PersistentBase<T>::MarkIndependent() [with T = v8::Object]’ is deprecated: Weak objects are always considered independent. Use TracedGlobal when trying to use EmbedderHeapTracer. Use a strong handle when trying to keep an object alive. [-Wdeprecated-declarations]
     persistent().MarkIndependent();
                                  ^
In file included from /home/lis/.cache/node-gyp/12.11.0/include/node/v8-internal.h:14:0,
                 from /home/lis/.cache/node-gyp/12.11.0/include/node/v8.h:25,
                 from ../src/node-kdtree.cc:9:
/home/lis/.cache/node-gyp/12.11.0/include/node/v8.h:567:22: note: declared here
       V8_INLINE void MarkIndependent());
                      ^
/home/lis/.cache/node-gyp/12.11.0/include/node/v8config.h:311:3: note: in definition of macro ‘V8_DEPRECATED’
   declarator __attribute__((deprecated(message)))
   ^~~~~~~~~~
In file included from /usr/include/c++/7/cassert:44:0,
                 from /home/lis/.cache/node-gyp/12.11.0/include/node/node_object_wrap.h:26,
                 from ../node_modules/nan/nan.h:49,
                 from ../src/node-kdtree.cc:15:
../node_modules/nan/nan_object_wrap.h: In static member function ‘static void Nan::ObjectWrap::WeakCallback(const v8::WeakCallbackInfo<Nan::ObjectWrap>&)’:
../node_modules/nan/nan_object_wrap.h:124:26: error: ‘class Nan::Persistent<v8::Object>’ has no member named ‘IsNearDeath’
     assert(wrap->handle_.IsNearDeath());
                          ^
../src/node-kdtree.cc: At global scope:
../src/node-kdtree.cc:39:21: error: ‘v8::Handle’ has not been declared
     Initialize (v8::Handle<v8::Object> exports){
                     ^~~~~~
../src/node-kdtree.cc:39:27: error: expected ‘,’ or ‘...’ before ‘<’ token
     Initialize (v8::Handle<v8::Object> exports){
                           ^
../src/node-kdtree.cc: In static member function ‘static void KDTree::Initialize(int)’:
../src/node-kdtree.cc:54:9: error: ‘exports’ was not declared in this scope
         exports->Set(Nan::New("KDTree").ToLocalChecked(), t->GetFunction());
         ^~~~~~~
../src/node-kdtree.cc:54:74: error: no matching function for call to ‘v8::FunctionTemplate::GetFunction()’
         exports->Set(Nan::New("KDTree").ToLocalChecked(), t->GetFunction());
                                                                          ^
In file included from ../src/node-kdtree.cc:9:0:
/home/lis/.cache/node-gyp/12.11.0/include/node/v8.h:5995:46: note: candidate: v8::MaybeLocal<v8::Function> v8::FunctionTemplate::GetFunction(v8::Local<v8::Context>)
   V8_WARN_UNUSED_RESULT MaybeLocal<Function> GetFunction(
                                              ^~~~~~~~~~~
/home/lis/.cache/node-gyp/12.11.0/include/node/v8.h:5995:46: note:   candidate expects 1 argument, 0 provided
../src/node-kdtree.cc: In member function ‘v8::Local<v8::Value> KDTree::Nearest(const double*, int)’:
../src/node-kdtree.cc:108:55: warning: ‘bool v8::Object::Set(uint32_t, v8::Local<v8::Value>)’ is deprecated: Use maybe version [-Wdeprecated-declarations]
           rv->Set(rpos, Nan::New<Number>(respos[rpos]));
                                                       ^
In file included from /home/lis/.cache/node-gyp/12.11.0/include/node/v8-internal.h:14:0,
                 from /home/lis/.cache/node-gyp/12.11.0/include/node/v8.h:25,
                 from ../src/node-kdtree.cc:9:
/home/lis/.cache/node-gyp/12.11.0/include/node/v8.h:3412:22: note: declared here
                 bool Set(uint32_t index, Local<Value> value));
                      ^
/home/lis/.cache/node-gyp/12.11.0/include/node/v8config.h:311:3: note: in definition of macro ‘V8_DEPRECATED’
   declarator __attribute__((deprecated(message)))
   ^~~~~~~~~~
../src/node-kdtree.cc:115:30: warning: ‘bool v8::Object::Set(uint32_t, v8::Local<v8::Value>)’ is deprecated: Use maybe version [-Wdeprecated-declarations]
           rv->Set(dim_, value);
                              ^
In file included from /home/lis/.cache/node-gyp/12.11.0/include/node/v8-internal.h:14:0,
                 from /home/lis/.cache/node-gyp/12.11.0/include/node/v8.h:25,
                 from ../src/node-kdtree.cc:9:
/home/lis/.cache/node-gyp/12.11.0/include/node/v8.h:3412:22: note: declared here
                 bool Set(uint32_t index, Local<Value> value));
                      ^
/home/lis/.cache/node-gyp/12.11.0/include/node/v8config.h:311:3: note: in definition of macro ‘V8_DEPRECATED’
   declarator __attribute__((deprecated(message)))
   ^~~~~~~~~~
../src/node-kdtree.cc: In member function ‘v8::Local<v8::Value> KDTree::NearestRange(const double*, int, double)’:
../src/node-kdtree.cc:156:59: warning: ‘bool v8::Object::Set(uint32_t, v8::Local<v8::Value>)’ is deprecated: Use maybe version [-Wdeprecated-declarations]
           rvItem->Set(rpos, Nan::New<Number>(respos[rpos]));
                                                           ^
In file included from /home/lis/.cache/node-gyp/12.11.0/include/node/v8-internal.h:14:0,
                 from /home/lis/.cache/node-gyp/12.11.0/include/node/v8.h:25,
                 from ../src/node-kdtree.cc:9:
/home/lis/.cache/node-gyp/12.11.0/include/node/v8.h:3412:22: note: declared here
                 bool Set(uint32_t index, Local<Value> value));
                      ^
/home/lis/.cache/node-gyp/12.11.0/include/node/v8config.h:311:3: note: in definition of macro ‘V8_DEPRECATED’
   declarator __attribute__((deprecated(message)))
   ^~~~~~~~~~
../src/node-kdtree.cc:163:34: warning: ‘bool v8::Object::Set(uint32_t, v8::Local<v8::Value>)’ is deprecated: Use maybe version [-Wdeprecated-declarations]
           rvItem->Set(dim_, value);
                                  ^
In file included from /home/lis/.cache/node-gyp/12.11.0/include/node/v8-internal.h:14:0,
                 from /home/lis/.cache/node-gyp/12.11.0/include/node/v8.h:25,
                 from ../src/node-kdtree.cc:9:
/home/lis/.cache/node-gyp/12.11.0/include/node/v8.h:3412:22: note: declared here
                 bool Set(uint32_t index, Local<Value> value));
                      ^
/home/lis/.cache/node-gyp/12.11.0/include/node/v8config.h:311:3: note: in definition of macro ‘V8_DEPRECATED’
   declarator __attribute__((deprecated(message)))
   ^~~~~~~~~~
../src/node-kdtree.cc:166:28: warning: ‘bool v8::Object::Set(uint32_t, v8::Local<v8::Value>)’ is deprecated: Use maybe version [-Wdeprecated-declarations]
         rv->Set(i++, rvItem);
                            ^
In file included from /home/lis/.cache/node-gyp/12.11.0/include/node/v8-internal.h:14:0,
                 from /home/lis/.cache/node-gyp/12.11.0/include/node/v8.h:25,
                 from ../src/node-kdtree.cc:9:
/home/lis/.cache/node-gyp/12.11.0/include/node/v8.h:3412:22: note: declared here
                 bool Set(uint32_t index, Local<Value> value));
                      ^
/home/lis/.cache/node-gyp/12.11.0/include/node/v8config.h:311:3: note: in definition of macro ‘V8_DEPRECATED’
   declarator __attribute__((deprecated(message)))
   ^~~~~~~~~~
../src/node-kdtree.cc: In static member function ‘static Nan::NAN_METHOD_RETURN_TYPE KDTree::Insert(Nan::NAN_METHOD_ARGS_TYPE)’:
../src/node-kdtree.cc:197:39: error: no matching function for call to ‘v8::Value::NumberValue()’
         pos[i] = info[i]->NumberValue();
                                       ^
In file included from ../src/node-kdtree.cc:9:0:
/home/lis/.cache/node-gyp/12.11.0/include/node/v8.h:2608:39: note: candidate: v8::Maybe<double> v8::Value::NumberValue(v8::Local<v8::Context>) const
   V8_WARN_UNUSED_RESULT Maybe<double> NumberValue(Local<Context> context) const;
                                       ^~~~~~~~~~~
/home/lis/.cache/node-gyp/12.11.0/include/node/v8.h:2608:39: note:   candidate expects 1 argument, 0 provided
../src/node-kdtree.cc: In static member function ‘static v8::Local<v8::Value> KDTree::_Nearest(Nan::NAN_METHOD_ARGS_TYPE)’:
../src/node-kdtree.cc:214:39: error: no matching function for call to ‘v8::Value::NumberValue()’
         pos[i] = info[i]->NumberValue();
                                       ^
In file included from ../src/node-kdtree.cc:9:0:
/home/lis/.cache/node-gyp/12.11.0/include/node/v8.h:2608:39: note: candidate: v8::Maybe<double> v8::Value::NumberValue(v8::Local<v8::Context>) const
   V8_WARN_UNUSED_RESULT Maybe<double> NumberValue(Local<Context> context) const;
                                       ^~~~~~~~~~~
/home/lis/.cache/node-gyp/12.11.0/include/node/v8.h:2608:39: note:   candidate expects 1 argument, 0 provided
../src/node-kdtree.cc: In static member function ‘static Nan::NAN_METHOD_RETURN_TYPE KDTree::NearestPoint(Nan::NAN_METHOD_ARGS_TYPE)’:
../src/node-kdtree.cc:238:7: error: ‘Handle’ was not declared in this scope
       Handle<Array> nearest = KDTree::_Nearest(info).As<Array>();
       ^~~~~~
../src/node-kdtree.cc:238:7: note: suggested alternative: ‘handle’
       Handle<Array> nearest = KDTree::_Nearest(info).As<Array>();
       ^~~~~~
       handle
../src/node-kdtree.cc:238:19: error: expected primary-expression before ‘>’ token
       Handle<Array> nearest = KDTree::_Nearest(info).As<Array>();
                   ^
../src/node-kdtree.cc:238:21: error: ‘nearest’ was not declared in this scope
       Handle<Array> nearest = KDTree::_Nearest(info).As<Array>();
                     ^~~~~~~
../src/node-kdtree.cc:238:21: note: suggested alternative: ‘Nearest’
       Handle<Array> nearest = KDTree::_Nearest(info).As<Array>();
                     ^~~~~~~
                     Nearest
../src/node-kdtree.cc: In static member function ‘static Nan::NAN_METHOD_RETURN_TYPE KDTree::NearestValue(Nan::NAN_METHOD_ARGS_TYPE)’:
../src/node-kdtree.cc:265:7: error: ‘Handle’ was not declared in this scope
       Handle<Array> nearest = KDTree::_Nearest(info).As<Array>();
       ^~~~~~
../src/node-kdtree.cc:265:7: note: suggested alternative: ‘handle’
       Handle<Array> nearest = KDTree::_Nearest(info).As<Array>();
       ^~~~~~
       handle
../src/node-kdtree.cc:265:19: error: expected primary-expression before ‘>’ token
       Handle<Array> nearest = KDTree::_Nearest(info).As<Array>();
                   ^
../src/node-kdtree.cc:265:21: error: ‘nearest’ was not declared in this scope
       Handle<Array> nearest = KDTree::_Nearest(info).As<Array>();
                     ^~~~~~~
../src/node-kdtree.cc:265:21: note: suggested alternative: ‘Nearest’
       Handle<Array> nearest = KDTree::_Nearest(info).As<Array>();
                     ^~~~~~~
                     Nearest
../src/node-kdtree.cc: In static member function ‘static Nan::NAN_METHOD_RETURN_TYPE KDTree::NearestRange(Nan::NAN_METHOD_ARGS_TYPE)’:
../src/node-kdtree.cc:287:41: error: no matching function for call to ‘v8::Value::NumberValue()’
           pos[i] = info[i]->NumberValue();
                                         ^
In file included from ../src/node-kdtree.cc:9:0:
/home/lis/.cache/node-gyp/12.11.0/include/node/v8.h:2608:39: note: candidate: v8::Maybe<double> v8::Value::NumberValue(v8::Local<v8::Context>) const
   V8_WARN_UNUSED_RESULT Maybe<double> NumberValue(Local<Context> context) const;
                                       ^~~~~~~~~~~
/home/lis/.cache/node-gyp/12.11.0/include/node/v8.h:2608:39: note:   candidate expects 1 argument, 0 provided
../src/node-kdtree.cc:290:96: error: no matching function for call to ‘v8::Value::NumberValue()’
         result = kd->NearestRange(pos, info.Length() - 1, info[info.Length() - 1]->NumberValue());
                                                                                                ^
In file included from ../src/node-kdtree.cc:9:0:
/home/lis/.cache/node-gyp/12.11.0/include/node/v8.h:2608:39: note: candidate: v8::Maybe<double> v8::Value::NumberValue(v8::Local<v8::Context>) const
   V8_WARN_UNUSED_RESULT Maybe<double> NumberValue(Local<Context> context) const;
                                       ^~~~~~~~~~~
/home/lis/.cache/node-gyp/12.11.0/include/node/v8.h:2608:39: note:   candidate expects 1 argument, 0 provided
../src/node-kdtree.cc: In static member function ‘static Nan::NAN_METHOD_RETURN_TYPE KDTree::New(Nan::NAN_METHOD_ARGS_TYPE)’:
../src/node-kdtree.cc:303:43: error: no matching function for call to ‘v8::Value::Int32Value()’
           dimension = info[0]->Int32Value();
                                           ^
In file included from ../src/node-kdtree.cc:9:0:
/home/lis/.cache/node-gyp/12.11.0/include/node/v8.h:2613:40: note: candidate: v8::Maybe<int> v8::Value::Int32Value(v8::Local<v8::Context>) const
   V8_WARN_UNUSED_RESULT Maybe<int32_t> Int32Value(Local<Context> context) const;
                                        ^~~~~~~~~~
/home/lis/.cache/node-gyp/12.11.0/include/node/v8.h:2613:40: note:   candidate expects 1 argument, 0 provided
kdtree.target.mk:112: recipe for target 'Release/obj.target/kdtree/src/node-kdtree.o' failed
make: *** [Release/obj.target/kdtree/src/node-kdtree.o] Error 1
make: Leaving directory '/home/lis/work/Elomia/server/node_modules/kdtree/build'
gyp ERR! build error 
gyp ERR! stack Error: `make` failed with exit code: 2
gyp ERR! stack     at ChildProcess.onExit (/home/lis/.nvm/versions/node/v12.11.0/lib/node_modules/npm/node_modules/node-gyp/lib/build.js:196:23)
gyp ERR! stack     at ChildProcess.emit (events.js:210:5)
gyp ERR! stack     at Process.ChildProcess._handle.onexit (internal/child_process.js:272:12)
gyp ERR! System Linux 4.13.0-46-generic
gyp ERR! command "/home/lis/.nvm/versions/node/v12.11.0/bin/node" "/home/lis/.nvm/versions/node/v12.11.0/lib/node_modules/npm/node_modules/node-gyp/bin/node-gyp.js" "rebuild"
gyp ERR! cwd /home/lis/work/Elomia/server/node_modules/kdtree
gyp ERR! node -v v12.11.0
gyp ERR! node-gyp -v v5.0.3
gyp ERR! not ok 
npm WARN [email protected] No description
npm WARN [email protected] No repository field.

npm ERR! code ELIFECYCLE
npm ERR! errno 1
npm ERR! [email protected] install: `node-gyp rebuild`
npm ERR! Exit status 1
npm ERR! 
npm ERR! Failed at the [email protected] install script.
npm ERR! This is probably not a problem with npm. There is likely additional logging output above.

npm ERR! A complete log of this run can be found in:
npm ERR!     /home/lis/.npm/_logs/2020-01-01T11_52_21_061Z-debug.log

installation warnings, and running errors

Dear Justin,
I'm having some problem running this amazing package. Please could you help?

I'm using an up to date version of node, and have updated all npm packages [and npm itself]. I've also installed the google c-based kdtree as suggested .

%>node -v
v0.10.26

I then install kd-tree
%>npm install kdtree

[email protected] install /Users/hoyleb/Desktop/Dropbox/node/node_modules/kdtree

%> node-gyp rebuild

CC(target) Release/obj.target/kdtree/src/lib/kdtree.o
CXX(target) Release/obj.target/kdtree/src/node-kdtree.o
../src/node-kdtree.cc:241:29: warning: comparison of integers of different signs: 'uint32_t' (aka 'unsigned int') and 'int'
[-Wsign-compare]
nearest->Length() >= dim) { // Points present
~~~~~~~~~~~~~~~~~ ^ ~~~
../src/node-kdtree.cc:268:29: warning: comparison of integers of different signs: 'uint32_t' (aka 'unsigned int') and 'int'
[-Wsign-compare]
nearest->Length() == (dim + 1)){ // Value present
~~~~~~~~~~~~~~~~~ ^ ~~~~~~~
2 warnings generated.
SOLINK_MODULE(target) Release/kdtree.node
SOLINK_MODULE(target) Release/kdtree.node: Finished
[email protected] node_modules/kdtree

Then I start node, and try to require kdtree and get this error
%>node

var kd = require('kdtree');
Error: Symbol kdtree_module not found.
at Module.load (module.js:356:32)
at Function.Module._load (module.js:312:12)
at Module.require (module.js:364:17)
at require (module.js:380:17)
at repl:1:10
at REPLServer.self.eval (repl.js:110:21)
at repl.js:249:20
at REPLServer.self.eval (repl.js:122:7)
at Interface. (repl.js:239:12)
at Interface.EventEmitter.emit (events.js:95:17)

This may be a red-herring, but I notice that the version of ./src/node-kdtree.cc is different from that in this repo. I have tried copying that file, and then that dir/ to the node_module/kdtree but it doesn't work.

Warm regards,

ben.

Issue with node 0.8

looks like node-waf isn't part of node, now they're using node-gyp, my knowledge of c is very basic to modify this package :(

Support for Node.js v0.11.14

I assume kdtree is not supported on node v0.11 since I get this error: http://sprunge.us/jPCH

Can you look into it? thank you

Change the distance computation to handle geo

Is there a way to configure the method used to compute the distance between points so that it can be used with latitude and longitude (and handle the curvature of the Earth)?

We were used to have something like that (for another kdtree implementation):

distance: function(obj1, obj2) {
  var a = 0.5 - Math.cos((obj2.latitude - obj1.latitude) * Math.PI / 180)/2 +
    Math.cos(obj1.latitude * Math.PI / 180) * Math.cos(obj2.latitude * Math.PI / 180) *
    (1 - Math.cos((obj2.longitude - obj1.longitude) * Math.PI / 180))/2;

  return 12742 * Math.asin(Math.sqrt(a));
}

feature k-nearest?

Hey,

is there the possibility obtaining the 2 closest points?
If not, is it possible to remove a point from the kdtree so I could perform the tree.nearest query twice (without getting the same point twice).

Thanks

here is npm debug log: npm-debug.txt

Thanks

Recommend Projects

React

A declarative, efficient, and flexible JavaScript library for building user interfaces.
Vue.js

🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
Typescript

TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
TensorFlow

An Open Source Machine Learning Framework for Everyone
Django

The Web framework for perfectionists with deadlines.
Laravel

A PHP framework for web artisans
D3

Bring data to life with SVG, Canvas and HTML. 📊📈🎉

Recommend Topics

javascript

JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
web

Some thing interesting about web. New door for the world.
server

A server is a program made to process requests and deliver data to clients.
Machine learning

Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
Visualization

Some thing interesting about visualization, use data art
Game

Some thing interesting about game, make everyone happy.

Recommend Org

Facebook

We are working to build community through open source technology. NB: members must have two-factor auth.
Microsoft

Open source projects and samples from Microsoft.
Google

Google ❤️ Open Source for everyone.
Alibaba

Alibaba Open Source for everyone
D3

Data-Driven Documents codes.
Tencent

China tencent open source team.