public class QuadTree extends Object
Many additional methods were added to the class both for efficient KNN queries and generalizing to n-dim.
param: minVec vector of the corner of the bounding box with smallest coordinates param: maxVec vector of the corner of the bounding box with smallest coordinates param: distMetric metric, must be Euclidean or squareEuclidean param: maxPerBox threshold for number of points in each box before slitting a box
Modifier and Type | Class and Description |
---|---|
class |
QuadTree.Node |
Constructor and Description |
---|
QuadTree(Vector minVec,
Vector maxVec,
DistanceMetric distMetric,
int maxPerBox) |
Modifier and Type | Method and Description |
---|---|
void |
insert(Vector queryPoint)
Recursively adds an object to the tree
|
void |
printTree()
Prints tree for testing/debugging
|
QuadTree.Node |
root() |
scala.collection.mutable.ListBuffer<Vector> |
searchNeighbors(Vector queryPoint,
double radius)
Finds all objects within a neighborhood of queryPoint of a specified radius
scope is modified from original 2D version in:
http://www.cs.trinity.edu/~mlewis/CSCI1321-F11/Code/src/util/Quadtree.scala
|
scala.collection.mutable.ListBuffer<Vector> |
searchNeighborsSiblingQueue(Vector queryPoint)
Used to zoom in on a region near a test point for a fast KNN query.
|
public QuadTree(Vector minVec, Vector maxVec, DistanceMetric distMetric, int maxPerBox)
public QuadTree.Node root()
public void printTree()
public void insert(Vector queryPoint)
queryPoint
- an object which is addedpublic scala.collection.mutable.ListBuffer<Vector> searchNeighborsSiblingQueue(Vector queryPoint)
queryPoint
- a test point for which the method finds the minimal bounding
box that queryPoint lies in and returns elements in that boxes
siblings' leaf nodespublic scala.collection.mutable.ListBuffer<Vector> searchNeighbors(Vector queryPoint, double radius)
original version only looks in minimal box; for the KNN Query, we look at all nearby boxes. The radius is determined from searchNeighborsSiblingQueue by defining a min-heap on the leaf nodes
queryPoint
- a point which is centerradius
- radius of scopeCopyright © 2014–2018 The Apache Software Foundation. All rights reserved.