java实现四叉树(附完整源码)
时间: 2023-10-17 08:10:12 浏览: 35
以下是Java实现四叉树的完整源代码:
```java
import java.util.ArrayList;
import java.util.List;
public class QuadTree {
private final int MAX_OBJECTS = 10;
private final int MAX_LEVELS = 5;
private int level;
private List<Point> objects;
private Rectangle bounds;
private QuadTree[] nodes;
public QuadTree(int level, Rectangle bounds) {
this.level = level;
this.objects = new ArrayList<>();
this.bounds = bounds;
this.nodes = new QuadTree[4];
}
public void clear() {
this.objects.clear();
for (int i = 0; i < nodes.length; i++) {
if (nodes[i] != null) {
nodes[i].clear();
nodes[i] = null;
}
}
}
private void split() {
int subWidth = (int) (bounds.getWidth() / 2);
int subHeight = (int) (bounds.getHeight() / 2);
int x = (int) bounds.getX();
int y = (int) bounds.getY();
nodes[0] = new QuadTree(level + 1, new Rectangle(x + subWidth, y, subWidth, subHeight));
nodes[1] = new QuadTree(level + 1, new Rectangle(x, y, subWidth, subHeight));
nodes[2] = new QuadTree(level + 1, new Rectangle(x, y + subHeight, subWidth, subHeight));
nodes[3] = new QuadTree(level + 1, new Rectangle(x + subWidth, y + subHeight, subWidth, subHeight));
}
private int getIndex(Point point) {
int index = -1;
double verticalMidpoint = bounds.getX() + (bounds.getWidth() / 2);
double horizontalMidpoint = bounds.getY() + (bounds.getHeight() / 2);
boolean topQuadrant = (point.getY() < horizontalMidpoint && point.getY() + point.getHeight() < horizontalMidpoint);
boolean bottomQuadrant = (point.getY() > horizontalMidpoint);
if (point.getX() < verticalMidpoint && point.getX() + point.getWidth() < verticalMidpoint) {
if (topQuadrant) {
index = 1;
} else if (bottomQuadrant) {
index = 2;
}
} else if (point.getX() > verticalMidpoint) {
if (topQuadrant) {
index = 0;
} else if (bottomQuadrant) {
index = 3;
}
}
return index;
}
public void insert(Point point) {
if (nodes[0] != null) {
int index = getIndex(point);
if (index != -1) {
nodes[index].insert(point);
return;
}
}
objects.add(point);
if (objects.size() > MAX_OBJECTS && level < MAX_LEVELS) {
if (nodes[0] == null) {
split();
}
int i = 0;
while (i < objects.size()) {
int index = getIndex(objects.get(i));
if (index != -1) {
nodes[index].insert(objects.remove(i));
} else {
i++;
}
}
}
}
public List<Point> query(Rectangle range) {
List<Point> pointsInRange = new ArrayList<>();
if (!bounds.intersects(range)) {
return pointsInRange;
}
for (Point p : objects) {
if (range.contains(p)) {
pointsInRange.add(p);
}
}
if (nodes[0] != null) {
pointsInRange.addAll(nodes[0].query(range));
pointsInRange.addAll(nodes[1].query(range));
pointsInRange.addAll(nodes[2].query(range));
pointsInRange.addAll(nodes[3].query(range));
}
return pointsInRange;
}
}
```
其中,`Point`和`Rectangle`是自定义的类,分别表示一个点和一个矩形。下面是这两个类的源代码:
```java
public class Point {
private int x;
private int y;
private int width;
private int height;
public Point(int x, int y, int width, int height) {
this.x = x;
this.y = y;
this.width = width;
this.height = height;
}
public int getX() {
return x;
}
public int getY() {
return y;
}
public int getWidth() {
return width;
}
public int getHeight() {
return height;
}
@Override
public String toString() {
return "[" + x + "," + y + "]";
}
}
```
```java
public class Rectangle {
private int x;
private int y;
private int width;
private int height;
public Rectangle(int x, int y, int width, int height) {
this.x = x;
this.y = y;
this.width = width;
this.height = height;
}
public int getX() {
return x;
}
public int getY() {
return y;
}
public int getWidth() {
return width;
}
public int getHeight() {
return height;
}
public boolean contains(Point point) {
return (point.getX() >= x && point.getX() + point.getWidth() <= x + width) &&
(point.getY() >= y && point.getY() + point.getHeight() <= y + height);
}
public boolean intersects(Rectangle range) {
return !(range.getX() > x + width || range.getX() + range.getWidth() < x || range.getY() > y + height || range.getY() + range.getHeight() < y);
}
}
```
四叉树的方法包括:
- `clear()`:清空四叉树中存储的所有对象。
- `split()`:将当前节点分裂为四个子节点。
- `getIndex(Point point)`:返回一个点所在的象限(子节点编号)。
- `insert(Point point)`:将一个点插入到四叉树中。
- `query(Rectangle range)`:查询一个矩形范围内的所有点。
注意:为了方便,上述代码中的矩形范围表示为左上角的坐标和宽度、高度,而不是左上角和右下角的坐标。如果需要使用左上角和右下角的坐标表示,需要相应地修改`Rectangle`类中的代码。
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)