This is a Java implementation of Quadtree, a tree data structure useful to store 2D positional data.
initialize the world with a 400 by 400 dimension starting at point (0,0)
//init.
Dimension dimension = new Dimension(400, 400);
Position2D position = new Position2D(0, 0);
QuadTree<Point> KD = new QuadTree<Point>(position, dimension);
//populate with random points.
Random random = new Random();
List<Point> pointList = new LinkedList<>();
for (int i = 0; i < 500; i++) {
Point point = new Point(
random.nextInt((int) (dimension.getWidth()+1)),
random.nextInt((int) (dimension.getHeight()+1)));
//insert in the QuadTree
KD.insert(point);
}
You can query points from the tree using a Boundary
object. Use the default Rectangle
or create one yourself just by implementing the Boundary
interface and overriding the contains(Point2D point)
methode.
Default query using the rectangle class.
//init.
Dimension dimension = new Dimension(400, 400);
Position2D position = new Position2D(0, 0);
QuadTree<Point> KD = new QuadTree<Point>(position, dimension);
...
Rectangle rect = new Rectangle(new Dimension(200,100), new Position2D(100,100));
//query the result is a list of all points within the rectangle.
KD.query(rect);
}
There is also a drawing tool for the QuadTree.
//Create new visual window for the quadtree.
//PointsList = list of all points in the tree.
//seletecPoints = selected Points from the query.
//rect = rectangle boundary.
//KD = the QuadTree.
//dimension = the dimension of the screen/ world space
new Window(pointList, seletecPoints, rect, KD,dimension);
}