A TypeScript implementation of k-d tree specifically for 2-dimensional uses. This was built to provide fast nearest-neighbor searches of sets of latitude/longitude coordinates, but works for any 2D (x, y) coordinates.
| Method | Description |
|---|---|
TwoDTree(points: Point[], private distanceFunction: (p1: Point, p2: Point) => number) |
Constructor used to create a new tree with a given set of points. Accepts a set of points to be added to the initial tree. Also, accepts an optional distance function to be used when performing nearest-neighbor queries. If not provided, a built-in Euclidian Distance function is used. |
add(point: Point) |
Adds a new point to the tree. |
remove(point: Point) |
Removes a point from the tree and replaces it with the best suitor from the remaining subtree. |
rangeSearch(p1: Point, p2: Point): Array<Point> |
Performs an orthogonal range search over a rectangle specified by the points p1 and p2. This search is inclusive and will return points on the boundaries of the rectangle. |
nearestNeighborsSearch(p: Point, distance: number, limit?: number): Array<Point> |
Performs a nearest-neighbor search around a given point p within the radius specified by distance. If provided, limit will cause the method to return only the x closest results, where x is equal to limit. |