kdtree
0.2.0, released 6 years ago by an unverified publisher
A fast Dart implementation of the k-dimensional (k-d) tree data structure.
What it does
Organizes points in a k-dimensional space to enable fast spatial searches, nearest neighbor lookups, and range queries. It allows inserting, removing, and querying points efficiently using a custom distance function.
AI-written summary of version 0.2.0, based on the package's README and metadata. Report an inaccuracy
Use it when
- You need to perform nearest neighbor or range searches on multidimensional spatial data.
- You are working with coordinate data that benefits from space-partitioning trees.
Skip it when
- You only need simple one-dimensional collections or standard lists.
- Your dataset changes constantly and you need heavily optimized self-balancing mechanisms without rebuilding.
Strengths
- Super fast Dart implementation of the k-d tree algorithm.
- Supports nearest neighbor queries with optional maximal search distance.
- Includes JSON serialization and balance factor approximation.
Weaknesses
- Unreliable balance factor for small trees.
- No built-in alternative packages from the catalog to compare against.
Setup
- Kind
- Pure Dart
- Effort
- Low
- Code generation
- No
- Direct dependencies
- 0
import 'package:kdtree/kdtree.dart';
var points = [
{'x': 1, 'y': 2},
{'x': 3, 'y': 4},
];
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': 2, 'y': 3}, 1);Alternatives
Packages that do the same job and could replace kdtree.
- fast_immutable_collections
Fast immutable lists, sets, maps, and multimaps for Dart
91Compare - more
A collection of utility extensions and specialized data structures for Dart.
90Compare - r_tree
An R-tree implementation to index and query two-dimensional data in Dart.
66Compare - ordered_set
Ordered Set that keeps elements sorted and allows duplicates by priority.
82Compare
Works with
Packages commonly used together with kdtree: ones it builds on, ones built on it, and its own family.