四叉树用于空间分区(Java)

Question

我目前正在尝试实现四叉树来划分映射。我在过去一周做了研究，但不太成功。我试着把地图分成不同的矩形，这将是地图的不同区域，这取决于人在哪里。我被困住了，因为某些原因，我的树的深度不能超过3。下面的代码是我的四叉树类。我附加了另外两个类，QuadNode和QuadRectangle。QuadNode是树中的节点，而QuadRectangle是玩家周围的矩形区域。

四叉树:

import java.util.*;
public class QuadTree {

private QuadNode root;
private QuadNode prevNode;
private double[][] points;
private double mapMinX;
private double mapMinY;
private double mapMaxX;
private double mapMaxY;
private int treeDepth;
private List<QuadRectangle> rectangles;
public void insert( double x, double y ){
    QuadRectangle value = new QuadRectangle();
    value.setPoint(x, y);
    if( root == null ){
        //System.out.println("Root");
        QuadNode node = new QuadNode<>( value );
        node.getRect().setLines( mapMinX, mapMinY, mapMaxX, mapMaxY );
        root = node;
    }
    else {
        //System.out.println("New Branch");
        insertRec(root, value);
    }
}
private void insertRec( QuadNode latest, QuadRectangle value ){
    // Check to see if point is in NE -- x > x center AND y > y center
    if ( latest.getRect().getCenterX() < value.getPointX() && latest.getRect().getCenterY() < value.getPointY() ){
        if ( latest.getNE() == null ) {
            QuadNode temp = new QuadNode<>(value);
            temp.getRect().setLines(latest.getRect().getCenterX(), latest.getRect().getCenterY(), latest.getRect().getMaxX(), latest.getRect().getMaxY());
            latest.setNE(temp);
        }
        else {
            insertRec( latest.getNE(), value );
        }
    }
    // Check to see if point is in NW -- x < x center AND y > y center
    else if( latest.getRect().getCenterX() > value.getPointX() && latest.getRect().getCenterY() < value.getPointY() ) {
        if ( latest.getNW() == null ){
            QuadNode temp = new QuadNode<>(value);
            temp.getRect().setLines(latest.getRect().getMinX(), latest.getRect().getCenterY(), latest.getRect().getCenterX(), latest.getRect().getMaxY());
            latest.setNW(temp);
        }
        else {
            insertRec( latest.getNW(), value );
        }
    }
    // Check to see if point is in SE -- x > x center AND y < y center
    else if( latest.getRect().getCenterX() < value.getPointX() && latest.getRect().getCenterY() > value.getPointY() ) {
        if ( latest.getSE() == null ){
            QuadNode temp = new QuadNode<>(value);
            temp.getRect().setLines(latest.getRect().getCenterX(), latest.getRect().getMinY(), latest.getRect().getMaxX(), latest.getRect().getCenterY());
            latest.setSE(temp);
        }
        else {
            insertRec( latest.getSE(), value );
        }
    }
    // Check to see if point is in SW -- x < x center AND y < y center
    else if( latest.getRect().getCenterX() > value.getPointX() && latest.getRect().getCenterY() > value.getPointY() ) {
        if ( latest.getSW() == null ){
            QuadNode temp = new QuadNode<>(value);
            temp.getRect().setLines(latest.getRect().getMinX(), latest.getRect().getMinY(), latest.getRect().getCenterX(), latest.getRect().getCenterY());
            latest.setSW(temp);
        }
        else {
            insertRec( latest.getSW(), value );
        }
    }
}
public QuadTree( double[][] vals, double minX, double minY, double maxX, double maxY ){
    rectangles = new ArrayList<>();
    points = vals.clone();
    mapMinX = minX;
    mapMinY = minY;
    mapMaxX = maxX;
    mapMaxY = maxY;
    //orderPointsCounterClock();
    for( int ii = 0; ii < vals[0].length; ii++){
        insert(vals[0][ii], vals[1][ii]);
    }
    treeDepth = getDepth(root);
    System.out.println(treeDepth);
    addToList(root);

    new DrawQuadTree( vals, rectangles ).setVisible(true);
}
private void orderPointsCounterClock(){
    double originX = (mapMaxX + mapMinX) / 2;
    double originY = (mapMaxY + mapMinY) / 2;
    List<double[]> pointsDistance = new ArrayList<>();
    boolean distFlag = true;
    for( int ii = 0; ii <  points[0].length; ii++){
        double sqX = Math.pow( originX - points[0][ii], 2);
        double sqY = Math.pow( originY - points[1][ii], 2);
        double pointToOriginDist = Math.sqrt( sqX + sqY );
        for(int jj = ii; jj < points[0].length; jj++){
            double tempDist = Math.sqrt( Math.pow( originX - points[0][ii], 2) + Math.pow( originY - points[1][ii], 2) );
            if( tempDist > pointToOriginDist ){
                distFlag = false;
            }
        }
        if( distFlag ){
            pointsDistance.add( new double[]{ points[0][ii], points[1][ii] });
        }
    }
    for( double[] l : pointsDistance ){
        System.out.println( l[0] + " :: " + l[1] );
    }
}
private int getDepth( QuadNode root ){
    if( root == null ){
        return 0;
    }
    else{
        List maxValues = new ArrayList<>();
        maxValues.add( 1 + getDepth( root.getNE() ));
        maxValues.add( 1 + getDepth( root.getNW() ));
        maxValues.add( 1 + getDepth( root.getSE() ));
        maxValues.add( 1 + getDepth( root.getSW() ));
        Collections.sort(maxValues);
        return (int)maxValues.get( maxValues.size() - 1 );
    }
}
public void addToList( QuadNode root ){
    if( root != null ){
        prevNode = root;
        if( !rectangles.contains( prevNode.getRect() )) {
            rectangles.add(prevNode.getRect());
        }
        addToList( root.getNE() );
        addToList( root.getNW() );
        addToList( root.getSE() );
        addToList( root.getSW() );
    }
    else{
        if( !rectangles.contains( prevNode.getRect() )) {
            rectangles.add(prevNode.getRect());
        }
    }
}
}

QuadNode:

public class QuadNode<T> {
private QuadRectangle rect;
private QuadNode NE, NW, SE, SW;
public QuadNode( QuadRectangle value ){
    this.rect = value;
    this.NE = null;
    this.NW = null;
    this.SE = null;
    this.SW = null;
}
public QuadRectangle getRect() {
    return rect;
}
public void setNE(QuadNode NE) {
    this.NE = NE;
}
public void setNW(QuadNode NW) {
    this.NW = NW;
}
public void setSE(QuadNode SE) {
    this.SE = SE;
}
public void setSW(QuadNode SW) {
    this.SW = SW;
}
public QuadNode getNE() {
    return NE;
}
public QuadNode getNW() {
    return NW;
}
public QuadNode getSE() {
    return SE;
}
public QuadNode getSW() {
    return SW;
}
}

QuadRectangle:

public class QuadRectangle {
private Point[] line1;
private Point[] line2;
private Point[] line3;
private Point[] line4;
private double pointX;
private double pointY;
private double centerX;
private double centerY;
public void setOnlyPoint(boolean onlyPoint) {
    this.onlyPoint = onlyPoint;
}
private double minX;
private double minY;
private double maxX;
private double maxY;
private boolean onlyPoint;

public QuadRectangle(){
    line1 = new Point[2];
    line2 = new Point[2];
    line3 = new Point[2];
    line4 = new Point[2];
}
public void setPoint( double x, double y ){
    this.pointX = x;
    this.pointY = y;
}
public void setLines( double minX, double minY, double maxX, double maxY ){
    this.minX = minX;
    this.minY = minY;
    this.maxX = maxX;
    this.maxY = maxY;
    Point tr = new Point();
    tr.setPoint( maxX, maxY );
    Point tl = new Point();
    tl.setPoint( minX, maxY );
    Point bl = new Point();
    bl.setPoint( minX, minY );
    Point br = new Point();
    br.setPoint( maxX, minY );
    line1[0] = tl;
    line1[1] = tr;
    line2[0] = tr;
    line2[1] = br;
    line3[0] = br;
    line3[1] = bl;
    line4[0] = bl;
    line4[1] = tl;
    centerX = (maxX + minX)/2;
    centerY = (maxY + minY)/2;
}
public boolean contains( double x, double y ){
    Point point = new Point();
    point.setPoint(x, y);
    if( line1[0].xCord < point.xCord && line1[1].xCord > point.xCord ){
        if( this.line2[0].yCord > point.yCord && this.line2[1].yCord < point.yCord ){
            return true;
        }
        else{
            return false;
        }
    }
    else{
        return false;
    }
}
public double getPointX(){
    return this.pointX;
}
public double getPointY(){
    return this.pointY;
}
public double getCenterX() {
    return centerX;
}
public double getCenterY() {
    return centerY;
}
public double getMinX() {
    return minX;
}
public double getMinY() {
    return minY;
}
public double getMaxX() {
    return maxX;
}
public double getMaxY() {
    return maxY;
}
public Point[] getLine1() {
    return line1;
}
public Point[] getLine2() {
    return line2;
}
public Point[] getLine3() {
    return line3;
}
public Point[] getLine4() {
    return line4;
}

我为这里的代码量道歉。我已经被困了几天了，我不知道从这里该去哪里。

Answer 1

有许多实现。我刚刚创建了一个，你可以看看，如果它能澄清你的想法:https://github.com/pvto/java-quadtree/blob/master/src/main/java/struct/quadtree/QuadTree.java .

这个想法是在你的QuadNode中进行所有的比较。您可以完全删除QuadRectangle并将其替换为两对坐标(x1,y1)(左上角)和(x2,y2)(右下角)。当你创建你的QuadNode时，你设置x1,y1,x2,y2，然后，永远不要改变他们。

您可以在该QuadNode中仅存储某种类型的一个项目，也可以像我一样存储一个项目列表。如果它创建了子QuadNodes，那么它应该不存储任何项，反之亦然。