kdtree 0.0.2

  • Readme
  • Changelog
  • Example
  • Installing
  • 68

k-d Tree Dart Library #

A basic super fast Dart implementation of the k-dimensional tree data structure. This library is dart port of Javascript implementation: https://github.com/ubilabs/kd-tree-javascript

In computer science, a k-d tree (short for k-dimensional tree) is a space-partitioning data structure for organizing points in a k-dimensional space. k-d trees are a useful data structure for several applications, such as searches involving a multidimensional search key (e.g. range searches and nearest neighbor searches). k-d trees are a special case of binary space partitioning trees.

Usage #

Using library #

// Create a new tree from a list of points, a distance function, and a
// list of dimensions.
var tree = KDTree(points, distance, dimensions);

// Query the nearest *count* neighbours to a point, with an optional
// maximal search distance.
// Result is an array with *count* elements.
// Each element is an array with two components: the searched point and
// the distance to it.
tree.nearest(point, count, [maxDistance]);

// Insert a new point into the tree. Must be consistent with previous
// contents.
tree.insert(point);

// Remove a point from the tree by reference.
tree.remove(point);

// Get an approximation of how unbalanced the tree is.
// The higher this number, the worse query performance will be.
// It indicates how many times worse it is than the optimal tree.
// Minimum is 1. Unreliable for small trees.
tree.balanceFactor();

Example #

import 'package:kdtree/kdtree.dart';

var points = [
  {'x': 1, 'y': 2},
  {'x': 3, 'y': 4},
  {'x': 5, 'y': 6},
  {'x': 7, 'y': 8}
];

var distance = (a, b) {
  return pow(a['x'] - b['x'], 2) + pow(a['y'] - b['y'], 2);
};

var tree = KDTree(points, distance, ['x', 'y']);

var nearest = tree.nearest({'x': 5, 'y': 5}, 2);

print(nearest);

0.0.1 #

  • Initial version

example/main.dart

import 'basic_example.dart';
import 'location/location_example.dart';

void main() {
  print('Basic example: Find one nearest point in list of points');
  runBasicExample();
  print(
      'Location example: Find 30 nearest location to given latitude and longitude from JSON list of locations.');
  runLocationExample(44.815, 20.282);
}

Use this package as a library

1. Depend on it

Add this to your package's pubspec.yaml file:


dependencies:
  kdtree: ^0.0.2

2. Install it

You can install packages from the command line:

with pub:


$ pub get

with Flutter:


$ flutter pub get

Alternatively, your editor might support pub get or flutter pub get. Check the docs for your editor to learn more.

3. Import it

Now in your Dart code, you can use:


import 'package:kdtree/kdtree.dart';
  
Popularity:
Describes how popular the package is relative to other packages. [more]
41
Health:
Code health derived from static analysis. [more]
99
Maintenance:
Reflects how tidy and up-to-date the package is. [more]
90
Overall:
Weighted score of the above. [more]
68
Learn more about scoring.

We analyzed this package on Jan 16, 2020, and provided a score, details, and suggestions below. Analysis was completed with status completed using:

  • Dart: 2.7.0
  • pana: 0.13.4

Health issues and suggestions

Document public APIs. (-1 points)

16 out of 16 API elements have no dartdoc comment.Providing good documentation for libraries, classes, functions, and other API elements improves code readability and helps developers find and use your API.

Maintenance suggestions

Package is pre-v0.1 release. (-10 points)

While nothing is inherently wrong with versions of 0.0.*, it might mean that the author is still experimenting with the general direction of the API.

Dependencies

Package Constraint Resolved Available
Direct dependencies
Dart SDK >=2.0.0 <3.0.0
Dev dependencies
pedantic ^1.8.0
test ^1.6.0