A Quad Tree is a data structure used for organizing and searching nodes in a two-dimensional space. It is commonly used in various applications such as image processing, geographic information systems, and more.
QuadTree is a tree data structure where each internal node has exactly four children: north-west, north-east, south-west and south-east. They are mainly used to partition a two-dimensional space by recursively subdividing it into four quadrants or regions.
Below is a simple implementation of a QuadTree in Java, along with methods to insert and search points.
```java
public class QuadTree {
private final int MAX_CAPACITY = 4;
private int level = 0;
private List<Point> points;
private QuadTree northWest = null;
private QuadTree northEast = null;
private QuadTree southWest = null;
private QuadTree southEast = null;
private Rectangle boundary;
QuadTree(int level, Rectangle boundary) {
this.level = level;
points = new ArrayList<Point>();
this.boundary = boundary;
}
void insert(Point point) {
if (!boundary.contains(point)) {
return;
}
if (points.size() < MAX_CAPACITY) {
points.add(point);
return;
}
if (northWest == null) {
split();
}
northWest.insert(point);
northEast.insert(point);
southWest.insert(point);
southEast.insert(point);
}
void split() {
int xOffset = boundary.x + (boundary.width / 2);
int yOffset = boundary.y + (boundary.height / 2);
northWest = new QuadTree(level + 1, new Rectangle(boundary.x, boundary.y, boundary.width / 2, boundary.height / 2));
northEast = new QuadTree(level + 1, new Rectangle(xOffset, boundary.y, boundary.width / 2, boundary.height / 2));
southWest = new QuadTree(level + 1, new Rectangle(boundary.x, yOffset, boundary.width / 2, boundary.height / 2));
southEast = new QuadTree(level + 1, new Rectangle(xOffset, yOffset, boundary.width / 2, boundary.height / 2));
}
List<Point> queryRange(Rectangle range) {
List<Point> pointsInRange = new ArrayList<Point>();
if (!boundary.intersects(range)) {
return pointsInRange;
}
for (Point point : points) {
if (range.contains(point)) {
pointsInRange.add(point);
}
}
if (northWest == null) {
return pointsInRange;
}
pointsInRange.addAll(northWest.queryRange(range));
pointsInRange.addAll(northEast.queryRange(range));
pointsInRange.addAll(southWest.queryRange(range));
pointsInRange.addAll(southEast.queryRange(range));
return pointsInRange;
}
}
```
You can use the `queryRange` method to find all points that exist within a given range. The range is a rectangle specified by where it starts (x,y) and its width and height. The `insert` method is used to insert a new point in the QuadTree. Note: This example assumes you have a simple `Point` and `Rectangle` class, you can create these classes as per your needs.
This code will create a QuadTree and insert points into it until it reaches its maximum capacity. At that point, it will split into four smaller trees. The `queryRange` method will return all points that fall within a given rectangle.
No comments:
Post a Comment